TERM-REWRITING AS A BASIS FOR A UNIFORM 
ARCHITECTURE IN MACHINE TRANSLATION 
Wilhelm WEISWEBER 
Technical University of Berlin 
Institute for Software and Theoretical Computer Science 
Project KIT-FAST, Sekr. FR 5-12 
Franklinstr. 28/29, D-1000 Berlin I0 
E-mail: ww@kit.cs.tu-berlin.de or weisweb@tubvm.cs.tu-berlin.de 
Abstract 
In machine translation (MT) different levels of 
representation can be used to translate a source 
language sentence onto its target language equivalent. 
These levels have to be related to each other. This 
paper describes a declarative formalism on the basis of 
term-rewriting which maps one representation onto an 
equivalent adjacent one. The different levels (e.g. 
represented by derivational trees, feature structures or 
expressions of a knowledge representation language) 
can be represented as terms. The equivalences between 
them are stated as axioms which are directed to form a 
non-confluent and terminating term-rewrite system. A 
courplete and coherent' algorithm has been developexl 
which interprets these systems and is able to handle 
default rules. 
1 Introduction 
In general there are different models of machine 
translation (MT). Regardless of the model used as the 
basis for an MT system, the architecture looks like the 
following (see \[Arnold et at. 86\] and \[Sharp 88\]): 
G: G 2 Gn.: G, 
I I I I 
Ss --} RI -~ R2 --~ ... --} R._: -~ R. --} ST 
sT: IT2 2T3 n-2Tn.l ..IT. .'IT 
The Ri's are representations, e.g. derivational trees (for 
example the syntactic stuetures) or directed acyclic 
graphs (for example f-structures of LFG or KL-ONE 
based conceptual representations), the Gi's are the 
formalisms which generate these representations, e.g. 
context free grammars or signatures, the Ti's are 
mappings from one representation to an equivalent 
adjacent one and S s, S T are the source and target 
language sentences, respectively. 
If the MT system is interlingua based, one of the R: is 
the interlingua and if it is transfer based one of the iTi+l 
is the transfer system. Usnally the first and last 
mappings have different status and are realized by a 
parser and a generator, respectively. 
The MT system of our project KIT-FAST ~ is based on 
a transfer model and i = 4, where RI is the source 
GPSG structure (see \[Gazdar et al. 85\] and \[Busemann/ 
Hauenschild 88\]), R 2 is the source Fanctor-Argument- 
Structure (FAS) 2, R3 is the target FAS and R4 is the 
target GPSG structure. G: to G4 are context-free 
grammars. In the current phase of our project we are 
taking the first steps towards the solution of textual 
phenomena, i.e. the interpretation of anaphorical 
relations (see \[Schmi~ et al. 91\]). In order to achieve 
this, the source FAS is mapped onto a conceptual 
representation for the text content, which is represented 
by the ABox (assertional knowledge) of the KL-ONE 
like representation language BACK. The knowledge 
representation system BACK has been developed by 
our neighbour project KIT-BACK (see lPeltason et al. 
89\]). The representation for the text content is used to 
determine the discourse consistency of possible 
antecedents for anaphoric pronouns. 
Currently sT1 and 4T 1. are realized by a GPSG parser 
and a morphological synthesis component, respective- 
ly. The mappings :T 2 (semantic analysis), 2T3 (trans- 
fer), 3T4 (generation) and the mapping from R 2 (FAS 
representations) onto conceptual representations are 
realized by one algorithm on the basis of term- 
rewriting. The mapping sT1 (parsing) also is intended 
to be implemented with a term-rewrite system. A short 
introduction to term-rewriting is given in section 3. 
it seems reasonable to represent all different R~ with 
the help of one data structure and to specify all iTi+l 
with the help of the ~me formalism (including parsing 
and generation). Some proposals in this direction have 
already been made. Two of these systems, namely 
CAT2 and TFS, and their properties are outlined in 
section 2. The following .sections present an alternative 
approach, which remedies some problems of these 
systems. In Section 4 a term representation, which is 
generated by a signature for a term algebra, is 
introduced with the help of which all R i can be 
represented. The representation of GPSG or FAS 
derivational trees, feature structures and KL-ONE like 
conceptual structures as terms is shown by example. 
The algorithm, i.e. the termination condition and the 
application relations, which are automatically 
computed from the rewrite rules by the examination of 
the interdependencies of the rules with the help of 
KIT = Ktinsdiche lntelligenz und Textverstehen (artificial intelligence and text understanding), FAST = 
functor-argument-structure for translation. The project KIT-FAST constitutes the Berlin component of the 
complementary research of EUROTRA-D. It receives rants by the Federal Minister for Research and 
eehnology. 
The FAS is a semantic representation for sentences which has been developed in the preceding phase of our project. 
Among others it contains functor-argument-relations, information about the thematic stxucturing of sentences 
anti semantic relations (argument roles) and semantic 
features. For a more detailed description see \[Hauercsclfild/Umbach 88\]. \[Busemann/Hauenschild 89\] 
and \[Busemann 90\]. 
ACTES DE COLING-92, Nhr, rrEs, 23-28 AOt\]T 1992 7 7 7 PROC. OF COLING-92, NANTEs, AUG. 23-28, 1992 
superposition, is given in section 5. Section 6 
concludes the paper and gives an outlook for farther 
research. 
2 Other approaches 
Several proposals in the direction of a uniform 
architecture of MT systems have teen made. Within 
the EUROTRA-D project the CAT2 system was 
developed by \[Sharp 88\]. This approach uses deriva- 
tional trees as representations and is characterized by 
the compositionality of the mapping rules according to 
\[Arnold et al. 86\]. The Typed Feature Structure (TFS) 
system as presented in \[Emele/Zajac 89\] and \[Zajac 
89,90,91\] is outlined in subsection 2. It uses typed 
feature structures as representations. 
Another approach, which is similar to Emele and 
Zajac's, is given in \[Russell et al. 91\]. 
2.1 The CAT2 system 
The representations Ri in the CAT2 system are 
derivational trees generated by context-free grammars 
G i which are made up of a pair (Ci, Ai), where C is a 
set of Constructors (structural rules) and A a set of 
Atoms (lexical rules). The mappings from one tree to 
another are called Translators, which are sets of t..rule,s. 
The translators sTt and nTT are realized by a parser and 
a Wee-to-string transducer, respe.ctively. The interpre- 
ter for t-rules processes the input tree top-down by 
matching the input tree with the left-hand side (Ihs) of 
a rule and the subobjects are recursively mapped. On 
the way bottom-up the subtrees are reordered according 
to rite right-hand side (rhs) of the given t-rule. The 
interpreter terminates when the whole input structure 
has been traversed and mapped. The t-rules have the 
form lhs =:> rhs. The Ihs and rhs are structural 
descriptions of the source and target structure, 
respectively, which are expressed by trees of the form 
(node).(subtrees). The nodes are pairs (C, F), where C 
is a distinguished feature and F is a set of feature-value 
pairs. The subtrees of the lhs and rhs can be combined 
with the help of conjunction or disjunction. Each 
subtree can be labeled with a tag $N and can be marked 
as optional or with the Kleene-star operator. When a 
tag, which occurs on the lhs, is missing on the rhs, the 
corresponding subtree is deleted, otherwise it is 
replaced by its mapping (translation). The t-rules 
maintain the partial compositionality 3 of the translator. 
An example of a t-rule for semantic analysis is the 
mapping from the surlace eases of the English verb 
generate onto the corresponding deep eases: 
(s,{}).\[$1 :(np,{cas=nom}), 
(vp,{}).\[(v,{stem=generale}).\[\], 
$2:(np,{cas=acc})\]\] 
(_,(}).\[(process,{lu=generate}), 
(agent,(}).\[$1\], 
(affected,{}).\[$2\]\] 
The advantages of CAT2 are its simplicity and 
The translation of an expression consists of the trans- lation of its subexp*essions (see \[Arnold et al. 86\]). 
efficiency. Furthermore CAT2 is supposed to be 
reversible. The efficiency is a consequence of the 
(partial) compositionality of the translators. This leads 
directly to an efficient slructure-driven 4 interpreter. The 
disadvantage is that it does not allow for directed 
acyclic graphs (DAGs) as representations. Since the 
translators are compositional, the t-rules cannot express 
the fact that the translation of one constituent depends 
on the translation of other constituents. For example if 
a predicate (verb, noun or adjective) is to be translated, 
the translation typically depend.,; on the semantic roles 
and featu~s (selectional restrictions) of its target 
language arguments. 
2.2 The TFS system 
The TFS system uses typed feature structures (TFSes) 
as representations, which can be represented as DAGs. 
TFSes are defined recursively. A TFS is an atomic or 
complex type. An atomic type consists of a type 
symbol and a complex type of a type symbol with a set 
of pairs of features and TFSes (values). The feature 
structures of PATR, LFG or HPSG are examples of 
TFSes. The set of type symbols P, which always 
includes the special type symbols T (top) and 
(bottom), is partially ordered and T _> T _>_ -L holds for 
all T E P. This partial ordering defines a lattice 
structure on P and can be extracted from the definitions 
(axioms). Definitions have the form T = TFSt v ... v 
TFS m :- C, where T is a type symbol, the TFS~ are 
TVSes of type F i (T _> Fi) and C is a conditional 
constraint, which may be omitted and is expressed by a 
logical conjunction of TFSes. The unification of two 
type symbols is their greatest lower bound. A "rewrite 
step "5 on an input TFS is performed by looking for a 
subTFS of type T of the input TFS and a definition of 
the form T = F :- C. In that case the subTFS of the 
input TFS and the TFS F are unified, the conjunction C 
of TFSes is solved and the result of the unification is 
inserted in place of the sub'l~'S, qlae TFS rule for the 
semantic analysis rule of the previous subsection is: 
SYN-S = 
SEM-S\[syn: S\[np: NP\[cas:NOM I X\], 
vp: VP\[v:GENERATE, 
np: NP\[cas:ACC I Y\]\] 
sere: REL\[process: GENERATE, 
agent: X', 
affected: Y'\]\] 
:o SYN-NP\[syn: NP\[cas:NOMt X'\], sere: X'\] 
SYN-NP\[syn: NP\[cas:ACC IY\], sem: Y'\] 
The advantage of TFS is that all different levels, i.e. Ss, 
Rt to R, and ST, are accessible for all mappings iTi+l. 
The disadvantage is that the algorithm for the 
application of definitions is not complete. 
4 'Stxuctuse-driven' means that fire input structure is ~ in a certain suategy (in this case top-down). 
crate-driven processes are normally more efficient than dataqlriven processes, which process the input 
structure according to the rules which manipulate it. 
s This is not 'rewriting' in the sense of this paper, but the input TFS is extended by unification, wlfich is a 
monotonic operation, i.e. it is "blown up" with additional information. 
AcrEs DE COLING-92, NANTES, 23-28 AOfYI" 1992 7 7 8 PROC. Or COLING-92, NANTES, AUG. 23-28, 1992 
Another problem of TFS can arise if the definitions arc 
applied in the wrong order. Let us for example assume 
that a pr~icate has alternative translations depending 
on the selection',d restrictions of its target language 
arguments and the definition which gives the wrong 
translation is applied before the target language 
arguments exist. This would lead to a wrong or no 
translation, even if the correct translation wonld be 
possible. This cat only be avoided if the alternatives 
are specified in one definition with the help of 
disjunction, which, however, may be very inefficient if 
the correct translation is the last alternative. 
3 Term-rewriting 
A term-rewrite system O'RS) 6 is a set of term-rewrite 
rules (TR rules) ~ -4, p with left-hand side (Ills) ~ mid 
right-hand side (rhs) p, in which cospecified variables 
occur. The applicability of a TR rule to all input tenn t 
is checked by superposing t with X. 
Definition: Superposition 
The term h is superposable with the term 12, iff a 
subterin q/u of h attd t 2 are unifiable with minimal 
unifier (or substitution) ~ ~: { }. 
'rite elements of ~ are pairs of substitutions X <- t~, 
where the variable X is substituted by the correspond- 
ing term h. The substitution of variables occurring in 
t/u and ~. according to ~ (notation: (t/n)~ and ~, 
respectively) yields two identical terms ((t/u)~ = Lcr). 
If the term t is superpo~ble with ~L at the subterm t/u 
with the substitution el, the TR rule is applied by 
replacing t/u in t by p~ yielding the target term t' = t\[u 
p~\]. This is called a derivation step (notation: t --> 
t'). 
Originally TRSes are used to prove rite equ',dity of 
terms. In this context file Knuth-Bendix algorithm has 
been developed (.see \[Knuth/ Bendix 70\]), which 
computes the norm.,d form of a given TRS, if the TRS 
is confluent and terminating. 
A TRS is confluent if the application of the rewrite 
rules to an input term yields exactly one target ternl, no 
tnatter in which sequence the rules are applied. 
In order 1o guarantee the termination of TRSes, an 
ordering on the corresponding terms has to be defined 
and at least one minimal term exists. Such an ordering 
guarantees the termination of a derivation .~.xluence h 
-~ t2 -~, ... -~ t~ l --> t,~ if and only if tl > tz > ... > t,4 > 
t~, where tl is the input term, t,~ the "target term and t i -> 
ti+t a derivation step, in which the resulting term t~+ t is 
derived from the original term ti by the application of 
one TR rule. 
In order to prove the temlination of a TRS, 
theoretically all possible derivation seqttences have to 
be checked. Another possibility is to define a total 
ordering on the teruls on the lhs and rhs of the '1~, 
rules, which guarantees that in a derivation step ti -4, 
ti+t the original term ti is reduced according to this 
ordering (ti > ti+t), then the TRS is terminating because 
alier a finite number of derivation steps either a 
minimal term is rcatclted or no qR rule is applicable to 
the resulting temL 
In order to guarantee the termination of TRSes by 
considering each single "lq~ rule, some criteria have to 
be defined for rite terms on the ihs and rhs of each 
single TR rule so that its application reduces file input 
term according to the total ordering. The ordering may 
reduce the size of the inlart term after rite application of 
a rule (a qnantitative ordering, i.e. deleting a subterul 
on tile rhs) or substitute a snbtenn of the intmt term in 
such a way that this substitution is never reversed by 
another rewrite rule (a qualitative ordering, i.e. na 
operator precedence ordering). For the use in MT we 
assume a qualitative ordering (see section 5.5). For 
details about the terufination of TRSes see \[Dershowitz 
82 and 85\]. 
TRSes in normal form are complete attd coherent. They 
can efficiendy be applied to deduce rite normal form of 
an input tenn. In order to prove the equality of two 
terms, their normal forms are deduced and compared 
htr literal equality. 
In order to use TRSes for mappings between a source 
anti a target representation ill MT, the source 
representation Call be viewed as an input term for a 
TRS and the target represenlatiou as its normal form. 
For this reason a term algebra liJr each representation 
R i tins to be dclined which generates the eotlcsponding 
lerms for the given representation. The mapping rules 
ate considered as TR rides. But using TRSes for the 
ntappiugs in MT cauls a problem. Normally analysis, 
transfer attd generation of natural languages in MT 
may have ntore than one result, i.e. TRSes used for 
mappings ill MT usually are not confluent. For this 
reason an interpreter for +lRSes has been developed in 
our project (sec section 5, \[Weisweber 89\] and 
\[Weisweber/Hauensehild 901), which is complete anti 
cohereal and applies terminating ,and non-continent 
TRSes in a very efficient way. 
4 The term representation 
ill order to have one process for the interpretation of 
the mapping roles of file different ,,To+l, all structures 
R,, have Io be represented with the help of one &ata 
stracttwe. The data structure used by the ~IRS 
interpreter consist,'; of terms which represent directed 
acyclic graphs (DAGs) wilh complex categories as 
node labels. Derivational Irces are special instances of 
DAGs in which no m-eutrancy of nodes is allowed and 
the edges leaving one ntv..le arc ortlered. The ternts are 
generated by the fltllowing signatureV: 
Signature for DAGs 
dag: CA7 LIST-) DAG 
list: DAG LIST ~ LIS1 
\[\]: --> LIST 
At present this signatule is fixed for the interpreter, bnt 
if more exlm'essive represenhqtions are necessary for 
In the following a notation according to \[tluet/Oppen 80 I 
is used, which gives a detailed introduction to TRSez. 
Signatures are very simihtr to context-flee roles. The 
operator definitions '()p': $1 ... S,, i -~ S,, can be viewed as the context-tree rule S,, - ) 'op(' S t '.' ...'.' S~4+)'. where the 
sorts S i are interpreted as nt)ll-tellrlina\]s. 
ACRES DE COLlNG-92, NANTES, 23-28 Ao~rr 1992 7 7 9 PROt:. OF COLING+92, NANTES, AUO. 23-28, 1992 
MT, the interpreter can be adapted. The sort CAT, 
which represents complex categories, is also generated 
by a signature which has to be specified for the 
particular representations. 
Scheme for signatures for complex categories 
C: LANG F1 ... Fn --~ CAT 
g-gpsg, g-fas, e-las, e-gpsg, g-atl, ...: -~ LANG 
Vi: .--4 F i 
The C are the main categories (in the sense of the 
distinguished features of \[Sharp 88\]). LANG is a 
special sort which represents the language to which a 
category belongs. With the help of the instances of this 
sort the categories occurring in terms can be 
distinguished to belong to the source or target 
representation. This fact is used to allow the TRS 
interpreter to process the input structure in a flexible 
strategy (see section 5.4) and to guarantee its 
termiantion (see section 5.5). 
The sorts F i represent the features which are associated 
to the main category. The Vi are 0-ary operators 
(constants) which represent the values for the features 
represented by F i (Vi E Fi). Nodes N of a DAG which 
have no oat-going edges (in trees terminal nodes) are 
represented by dag(N,~). 
Example signature for German nominal phrases 
np: LANG PER PLU GEN CAS --> CAT 
g-gpsg: --~ LANG 
1,2,3: ---> PER 
+,-: ~ PLU 
fem,masc,neut: --> GEN 
nom,gen,dat,acc: ~ CAS 
An example of a term for a German nominal phrase is 
np(g-gpsg,3,-,fem,nom). 
The TRS interpreter uses the signature for DAGs to 
traverse the input representation in order to find a 
subterm which is unifmble with the Ihs of a TR rule. 
Our TRS editor uses the signature for DAGs to produce 
terms from a graphical input and to perform consist- 
ency checks on the input. 
In order to show, for example, how conceptual 
structures can be represented as temls, a small 
fragment of the syntax of the ABox tell language 
(ATL) of the knowledge representation system BACK 
(see \[Peltason et at. 89\]), which is used in the 
experimental MT system of our project, is given: 
Context-free rules for a fragment of the ATL: 
(abox-tell) --> (obj-ref) = (atl-conc) I 
(variable) = (atl-conc) 
obj-ref) --> ucl 
atl-conc) ---> (concept) 
I (concept) with (all-role) 
(atl-role) ---> (role) : ((abox-tell)) 
I (atl-role) anOwlth (all-role) 
The non-terminal (concept) represents the concepts 
used in a discourse and (role) represents the semantic 
roles of the arguments of a predicative concept. 
(variable) represents variables which are instantiated 
with a new unique discourse object reference ucl, if 
there is no object reference in the ABox for the given 
concept. 
In order to represent ATL expressions as terms the 
following signature is used: 
Signature for ATL categories: 
equal: LANG OBJ-REF ~ CAT 
with: LANG ROLE ~ CAT 
g-all: --~ LANG 
The ATL expressions are represented by trees and 
since terms represent DAGs, a context-free syntax is 
needed to check whether the target terms of the 
conceptual analysis represent ATL trees or not. The 
context-free syntax of ATL trees is given in the 
following. 
Context-free syntax for ATL trees 
atl(g-atl) --, equal(g-atl,_) with(g-all,_)" 
with(g-atl,_) ~ equal(g-atl,_) with(g-atl,_)" 
equal(g-all,_) ~ (concept) (lexical rules) 
For example the German ATL expression UCl = 
generate with agent : (uc2 = generator) andwith 
affected : (uc3 = sentence) is represented by the 
following ATL term: 
Example for an ATL term 
dag(atl(g-atl), I 
dag(equal(g-atl,ucl), \[ 
dag(generate, \[\])1), 
dag(wit h(g-atl,agent), \[ 
dag(equal(g-atl,uc2), \[ 
dag(generator, \[\])\])\]), 
dag(with(g-atl,affected), \[ 
dag(equal(g-atl,uc3), \[ 
dag(sentence, \[\])\])\])\]) 
At the end of this section we give the TR rule of the 
semantic analysis which corresponds to the rules of 
CAT2 and TFS presented in the sections 2.1 and 2,2, 
respectively: 
dag(s(e-gpsg), \[ 
dag(v-pred(e-fas,nom-acc,active), \[ 
dag(genetate, \[\])\]), 
dag(term(e-fas,nom), X), 
dag(term(e-fas,acc), Y)\]) 
dag(clause(e-fas), \[ 
dag(v-pred(e-fas,ag-at,active), \[ 
dag(generate, \[\])\]), 
dag(term(e-fas,agent), X), 
dag(term(e-fas,affected), Y)\]) 
The TR rule contains the cospecified variables X and 
Y. Additionally some conditions on variable feature 
values can be defined with the help of the operators =, 
¢, < and _> which can be combined with the logical 
operators and or or. 
In order to handle for example the long distance 
dependencies of GPSG or LFG conveniently, the 
expressive power of TR rules has been increased. The 
categories occurring on the lhs and rhs of a rule may be 
labeled with the +-operator, which is similar to the 
Kleene-star operator. The occurrence of the category 
C ÷ means that C is the root node of the corresponding 
subDAG, which may dominate another category C, 
which again may dominate another category C and so 
ACRES DE COLING-92, NANTES, 23-28 AOO'r 1992 7 8 0 PROC. OF COLING-92, NANTES, AUG. 23-28, 1992 
on. This is similar to functional uncertainty in LFG. 
5 Interpretation of TRSes 
As mentioned in section 3, the TRSes for the mappings 
in NIT are not usually confluent. For this reason the 
Knuth-Bendix algorithm cannot be used. In order to 
apply non-confluent TRSes efficiently, the inter- 
dependencies between their TR rules have to be 
determined. The rewrite process is data-driven and in 
order to check each TR rule only once for application, 
an order is computed (subsection l). The rewrite 
process should be complete and coherent. Therefore 
more general TR rules should be checked for 
application after more specific ones and sub~ction 2 
shows an order for some kind of default TR rules. As 
the TRSes are not confluent, the interpreter has to 
control the branching of the derivation sequence. This 
is done with the help of alternative rules (subsection 3). 
The TRS interpreter is outlined in subsection 4. Since 
the rewrite process is data-driven, the termination of 
the interpreter cannot be guaranteed by the interpreter 
itself. Subsection 5 gives an adequate termination 
condition for TRSes used in MT systems. 
In the following subsections, the existence of two TR 
rules (nl, ~.1 --~ Pl) and (n2, 2%-2 --~ P2) in the TRS is 
assumed, where {n~, nz} C: R N (the set of numbers of 
all TR rules), k~, 7% are the left-hand sides (lhs) and Pl, 
p~ are the right-hand sides (rhs) of the TR rules. 
5.1 The application order 
In order to check each TR rule for application only 
once, an order has to be computed. Generally there are 
cycles in the application order and the TR roles of a 
cycle have to be checked more than once. 
Definition: Application order relation >~, 
If pl is superposable with 2% or 
L~ is superposable with p~ 
then n~ >,pp n 2, where >,~ (S R~ × R N. 
The relation >,pp is transitive and n~ :>lpp II2 means that 
TR rule n t has to be applied before rule nz. This 
relation may have cycles n I >~pp .,. >~pp n m >~pp n 1. \[u 
order to compute the cycles of >*w' the transitive 
closure >,+p~ is computed, which may contain an 
equivalence relation >~y~ (>¢y~ is reflexive, symmetric 
and transitive, >¢y~ ~ >~+pp and >~y~ ~ Rc × Pc, where 
Rc ~ RN is the set of numbers of cyclic TR rules). 
Definition: Cycles of >~,t, 
A cycle of >,+~ is an equivalence class \[n\] = {m \]n >~yo 
m} and >~y~ is the greatest equivalence relation in >,~. 
The cycles (equivalence classes) are either equal or 
disjoint and constitute a partition of Re. The efficiency 
of the rewrite process crucially depends on the number 
and size of the cycles. 
5.2 Default TR rules 
In some situations it is useful to have some kind of 
default TR rule. For example if there ate several 
different translations for one source language terminal 
which depend on certain (structural) conditions and 
there is a "default" translation, if none of these 
conditions holds, e.g. if the German verb schwimmen 
has an inanimate argument, it has to be translated into 
the English float and if there is no information 
available, it has to be translated into swim. 
These default TR rules can be computed by 
superposing the lhs of two TR rules and one lhs occurs 
completely in the other lhs. In that case the more 
special TR rule has to be checked for application first 
and the more general one last. 
Definition: Default relation >dcf 
If ~1 is superposable with ~z with substitution ff and 
~-1 and ~ are not identical and 
all variables X of (X ~ t) E ff occur in 2% 
then n I >da n2, where >da ~ RD × Ro. 
The relation >ca is reflexive, anti-symmetric and 
transitive, i.e. a (partial) order relation in R o (the set of 
numbers of default rules) and nl >an n2 means that the 
lhs of role n 1 is more special than the lhs of rule n2 and 
Ul has to be checked for application before n2, even if 
they are part of a cycle. If ~4 and ~ are identical 
without the names for variables, the TR rules are 
alternatives (see next subsection). 
The set R O contains subsets C i ~ Ro, which are called 
chains, because for every x,y ~ Ci either x >da Y or y 
>~ x. Every chain has an infimum (the most special 
TR rule) and a supremum (the most gemerul TR rule). 
5.3 Alternative TR rules 
In order to get alternative solutions the derivation 
sequence has to branch at certain points which can also 
be computed by superposing the lhs of two TR rules. 
This is just the situation, in which the Knuth-Bendix 
algorithm computes a critical pair. 
Definigon: Alternative relation V,,~, 
If ~q is superposable with 2% at subterm ~/u with 
substitution o and 
Pl is not superposable with ~ and 
if ~.l/u = ~.1 then ~qis not unifiable with t32 
then {(n i, ~.lo --> pit), (n~, ~1o -~' ~t\[u ~ p2t~\])} C 
"IRS and n~ v,l ~ n' 2, where v.l t ~ R A X R^. 
The relation v,I, is reflexive, symmetric and transitive, 
i.e. an equivalence relation in R^ (the set of numbers 
of alternative rules), n~ v,lt n~ means that everytimc 
TR rule nl is applicable to an input term, then n½ is 
applicable and vice versa and the derivation sequence 
branches at this point. The additional condition that 
the rhs Pl of one rule is not superposable with the lhs 
Lz of the other is necessary to exclude brunches caused 
by rules in which the subterm ~,l/u is used us structural 
condition. The other condition is needed for the same 
reason in the special case when k~ and Lz are unifiable. 
The rules ni or n~ may already exist in the TRS. In that 
case either the lhs of n~ and n 2 have been identical and 
nl = nl and n~ = n 2 or nl >d~ n2 and n I = nl or n 2 >~ n 1 
and n~ = n2. 
If the rules n~ or n~ are not in the TRS, they are added 
and all other relations are computed. In most cases the 
new lhs is more special than the two other ths and the 
corresponding default relations hold. 
The lhs of the new TR rules n\[ and n~ is the 
"superposition" of lhs of the rules nl and n2. The rhs of 
n i is the rhs of hi, in which the variables are replaced 
according to the substitution o. The rbs of n~ is the lhs 
of n l, in which the subterm ~,jhl is replaced by the rhs 
of n 2, the variables of which are replaced according to 
AcrEs DE COLING-92, NANTES, 23-28 Attar 1992 7 8 1 PROC. OF COLING-92, NANTES. AUG. 23-28, 1992 
the superposition. The efficiency of the rewrite process 
crucially depends on the number and size of the 
equivalence classes of RA. 
5.4 The TRS interpreter 
In order to apply the TR rules in an efficient order, the 
ordered set APP is precomputed: 
APP= RN-Re-Ro-RA 
U {nl\[n\] ~Re} 
LJ {hi n is inflmum of a chain C C: RD} 
k) {n\[\[n\] ~RA} 
The set APP is ordered in the way that the sequence 
does not contradict to >,pp. The interpreter for TRSes 
takes an input term t and checks all TR rules (n, 7~ -~ 
p} in the order of APP. 
If n ~ R c, then all TR rules m ~ \[hi ~ R c trove to be 
checked for application in an arbitrary order as long as 
one rule of the cycle \[n\] is applicable, otherwise if t is 
superposable with ~., then the corresponding TR rule is 
applied else the next TR rule is checked for 
application. 
If the applicable TR rule n is a default rule (n ~ Ro), 
then the TR rules m (n ->ae~ m) of the chain C ~ R o are 
applied in the order of >aa. 
If the applicable TR rale n is an alternative rule (n E 
R^), then all the TR rules m c In\] ~ R^ are applied 
alternatively. Every alternative is a new branch in the 
derivation sequence. 
If a TRS has a normal form, the algorithm interpretes it 
as efficiently as nomlalized TRSes. 
The interpreter strategy of processing the input term, 
which represents a DAG, is flexible, i.e. the TR rule 
writer determines whether to proceed top-down, 
bottom-up, from left to right or vice versa. For example 
if the daughter categories of the lbs of the TR rules are 
target language (TL) categories and the mother catego- 
ry is a source language (SL) category which is to be 
translated into a TL category by the corresponding rule, 
then the interpreter will process the input structure 
bottom-up (see example of the TR rule in section 4). 
5.5 Termination 
For the use in our TRSes a quantitative ordering has 
been defined that guarantees the termination of all the 
TRSes used in our MT system. This ordering uses the 
different vocabularies of the SL and TL terms and 
requires that the number of SL categories occurring in 
the input term has to be reduced. This means that either 
a SL category has to be deleted or it has to be replaced 
by one or more TL categories. The minimal terms are 
all terms in which no SL categories occur. This 
ordering guarantees the termination of that sequence 
because the number of SL categories occurring in the 
input term is finite and after a finite number of 
applications there will be no SL categories left in the 
resulting term or no TR rule is applicable. 
In order to prove the termination ofa TRS, every single 
TR rule has to be checked. The ths and rhs may 
contain occurrences of variables for terms, i.e. for 
(sub)DAGs, sets of (sub)DAGs, categories or feature 
values of categories. If for example a variable for a 
term representing a DAG is occurring once on the lhs 
and doubled on the rhs, then the number of SL 
categories occurring in the input term may be increased 
in the resulting term. For this reason an additional 
condition has to be defined which has to be full'tiled by 
the lhs and rhs of each TR rule. Every variable 
occurring on the rhs has to occur on the ths. The two 
restrictions on 'IR rules allow for checking each rule 
for termination after it has been defined or modified so 
that the termination of the TRS can be guaranteed, 
because in every derivation step the number of SL 
categories is reduced. The derivation ends successfully 
if no SL category occurs in the resulting term and the 
corresponding tree can be generated by the corltext-free 
TL grammar. 
The given termination condition fulfils the three 
constraints for termination (the input representation 
must be built in a well-behaved compositional way, 
recursive input representations have to be considered 
and the input should not be extended) discussed in \[van 
Noord 901. 
If the termination condition should prove to be 
inadequate for the use in MT, qualitative orderings or 
combinations of quantitative and qualitative orderings 
may be defined. Up to now the given quantitative 
ordering has proved to be adequate for the TRSes of 
our MT system. 
6 Conclusion 
The TRS interpreter and aal editor for TRSes are 
implemented in Arity Prolog on an AT compatible PC. 
The editor allows for a graphical input in DAG 
notation, performs consistency checks on TR rules, 
checks the termination condition on TR rules, 
generates the corresponding terms and computes the 
application order by the means of the definitions given 
in section 5. TRSes have successfully been used for 
semantic analysis, transfer, generation and for the 
mapping from sentence semantic representations to 
conceptual representations in the experimental MT 
system of our project. TRSes are to be used to 
implement parsing in the near filturc. First experiments 
iu that direction have been encouraging. 
In the future the possibility of merging all TRSes 
defined for the translation of one language into another 
to form one single TRS is to be investigated. The 
advantage would be that the analysis depth will 
become flexible in the way that if the translation of a 
fragment of the source language syntactic representa- 
tion is unambiguous, it can be directly translated into 
the target language syntactic representatiou, without 
the detour via the semantic representation. This would 
be possible for all levels of representation. 
Another point will be to check the possibility of 
extracting reversible ports from one TRS and to use 
them for the other translation direction. 
The interpreter, which uses the basic unification 
algorithm of \[Eisele/DOrre 86\] to superpose the input 
term with the the lhs of the TR rules, is intended to be 
expanded with disjunction according to \[l)Srre/Eisele 
90\]. 
With these additional features, term-rewriting is a 
powerful, elegant, complete and coherent device to 
describe the relations between all levels of 
representation in machine translation systems. 
ACRES DE COL1NG-92, NANTES, 23-28 AO~r 1992 7 8 2 PROC. OF COLING-92, NANTES, AUG. 23-28. 1992 
7 References 
\[Busemann 90\]: S. Busemann: "Generiernng 
natiirlieher Sprache mit Generalisierteu Phrasen- 
struktar-Grammatiken", KIT-Report 87, Technical 
University of Berlin 1990 
\[Arnold et al. 86\]: D.J. Araold, S. Krauwer, M. Rosner, 
L. de Tombe, G.B. Varile: "The (C,A),T Framework in 
EUROTRA: A Theoretic.ally Committed Notation for 
MT", in: Procs. llth COLING-86, Bonn 1986, pp. 
297-303 
\[Busemann/Hauenschild 88\]: S. Buseinann, Ch. 
Hauenschild: "A Constructive View of GPSG or How 
to Make it Work", in: Procs. 12th COL1NG-88, 
Budapest 1988, pp. 77-82 
\[Busenlann/Hauenschihl 89\]: S. Busemann, Ch. 
Hauenschihl: "From FAS Representations to GPSG 
Structures", in: S. Busemann, Ch. Haueuschild and C. 
Umbach (eds.): "Views of the Syntax/Semantics 
Interface", Procs. of the Workshop "GPSG and 
Semantics", KIT-Report 74, Technical University of 
Berlin 1989, pp. 17 - 43 
\[Dershowitz 82\]: N. Dershowitz: "Orderings for Term- 
Rewriting Systems". Theoretical Computer Science 17 
(1982), North-Holland, pp. 279 - 301 
\[Dershowitz 85\]: N. Dershowi~: "Termination", in: 
G.GOOs. J. Hartmanis (eds.): "Rewriting Techniques 
and Applications", LNCS 202, Dijon, France 1985, pp. 
180 - 224 
\[D6rre/Eisele 90\]: J. I)6rre, A. Eisele: "Feature Logic 
with Disjunctive Unification", in: Procs. 13th 
COLING-90 (Vol. 2), Helsinki 1990, pp. 100-105 
\[Eisele/D6rre 86\]: A. Eisele, J. D0rre: "A Lexical 
Functional Grammar System in Protog", in: Procs. llth 
COLING-86, Bonn 1986, pp. 551-553 
\[EmelefZajac 89\]: M. Emele, R. Zajac, "RETIF: A 
Rewriting System lot Typed Feature Structures", ATR 
Technical Report TR-I-0071 1989 
\[Gazdar et al. 851: G. G~dar, E. Klein, G. Pullum and 
I. Sag: "Generalized Phrase Structure Grammar", 
Oxford, Blackwell 1985 
lHauenschild/Bnsemann 88\]: Ch. Hauen~hild, S. 
Busemann: "A constructive version of GPSG for 
machine translation", in: E. Steiner, P. Schmidt and C. 
Zellinsky-Wibbelt (eds.): "From Syntax to Semantics - 
Insights From Machine Translation", London, Frances 
Pinter 1988, pp. 216-238 
lHauenschild/Umbach 88\]: Ch. Hauenschild, C. 
Umbach: "Funktor-Argument-Stmktur, Die 
satzseman~scheRepr~entations- und Transferebene 
im Projekt KIT-FAST", in: J. Schiltz (ed.): "Workshop 
Semantik und Transfer", EUROTRA-D Working 
Papers No.6, Saarbrilcken 1988, pp. 16-35 
\[HuetK)ppen 80\]: G. Huet, D. Oppen: "Equations and 
Rewrite Rules", in: R.V. Book (ed.): "Formal 
Language Theory, Perspectives and Open Problems", 
Academic Press 1980, pp. 349-405 
\[KnutldBendix 70\]: D. IOmth, P. Bendix: "Simple 
Word Problems ill Universal Algebras", in: J. Le~h 
(ed.): "Computational Problems in Abstract Algebra", 
Pergamon Press 1970, pp. 263-297 
\[Peltasou et al. 751: C. Peltason, A. Schmiedel, C. 
Kindermanu, J. Quan~, "The BACK System 
Revisited", KIT-Report 75, Technical University of 
Berlin 1989 
\]Russell et al. 91\]: G. Russell, A. Ballim, D. Estival, S. 
Warwick-Amstrong, "A Language for the Statement of 
Binary Relations over Feature Structures", in: Preos. of 
the 5th Con|erence of file European Chapter of the 
ACL, Berlin 1991, pp. 287-292 
\[Schmi~ ct al. 91\]: B. Schmitz, S. Preufl, C. 
Hauenschild: "Textrepr'asentatiou und Hintergrand- 
wissen fiir die Anaphernresolutiou im Maschinelleu 
Ubersetzungssystem KIT-FAST", KIT-Report 93, 
Technical University of Berlin 1991 
ISh~u-p 881: R. Sharp, "CAT2 - Implementing a 
Formalism for Multi-Lingu',d MT", in: Procs. of the 
2ud International Conference on Theoretical and 
Methodological Issues in Machine Translation of 
Natural Languages, CMU Pittsburg 1988 
\[vau Noord 90\]: G. vua Noord: "Reversible 
Unification Based Machine Translation", in: Procs. 
13th COLING-90 (Vol. 2), Helsinki 1990, pp. 299-304 
IWeisweber 89\]: W. Weisweber: "Transfer in Machine 
Translation by Non-Confltlent Term-Rewrite Systems", 
in: Pfocs. tff the 13th Gernmn Workshop on Artificial 
Intelligence (GWAI-89), Eringerfeld, September 1989, 
pp. 264 - 269 
\[Weisweber/Hauen~hihl 90\]: W, Weisweber, Ch. 
Hauenschild: "A model of Multi-Level Transfer for 
Machiue Translation and Its Partial Re~dization", KIT- 
Report 77, Technical University of Berliu 1990 and to 
appear in: Procs. of the Seminar "Computers & 
Translation '89", Tbilisi 1989 
\[Zajac 891: R. Zajac, "A Transfer Model Using a Typed 
Feature Structure Rewriting System with Inhuritance", 
in: Plots. of the 271h Annual Meeting of the ACL, 
Vancouver 1989 
\[Zajac 90\]: R. Zajac, "A relational approach to 
translation", in: Procs. of the 3nd International 
Conference on Theoretical and Methodological Issues 
in Machine Translation of Natural Languages, Austin 
1990 
\[Zajac 911: R. Zajac, "A Uniform Architecture for 
Parsing, Generation and Transfer", in: T. Strzalkowski 
(ed.), Procs. of the Workshop on Reversible Grammar 
in Natural Language Processing, Berkeley 1991, pp. 
71-80 
AC1T~ DE COLING-92, NANTJ~, 23-28 Aol)r 1992 7 8 3 PR()c:. OF COLING-92, NAIXrIES. AUG. 23-28, 1992 
