Uses of C-Graphs in a Prototype for Automatic Translation.

USES OF C-GP.APHS lil A PROTOTYPE FOR ALrFC~ATIC TRNLSLATION, Marco A. CLEMENTE-SALAZAR Centro de Graduados e Investigaci6n, Instltuto Tecnol6gico de Chihuahua, Av. Tecnol6gico No. 2909, 31310 Chihuahua, Chih., MEXICO. ABSTRACT This paper presents a prototype, not com- pletely operational, that is intended to use c-graphs in the translation of assemblers. Firstly, the formalization of the structure and its princi- pal notions (substructures, classes of substruc- tures, order, etc.) are presented. Next section de- scribes the prototype which is based on a Transfor- mational System as well as on a rewriting system of c-graphs which constitutes the nodes of the Trans- formational System. The following part discusses a set of operations on the structure. Finally, the implementation in its present state is shown. 1. INTRODUCTION. In the past [10,11], several kinds of repre- sentation have been used (strings, labelled trees, trees with "decorations", graphs of strings and (semantic) networks). C-graphs had its origin as an alternative in the representation and in the treatment of ambiguities in Automatic Translation. In earlier papers [4,5] this structure is named E-graph but c-graph is better suited since it is a generalized "grafo de cadenas" (graph of strings). This structure combines some advantages of the Q-systems [7] and of the trees of ARIANE-78 [1,2,11], in particular, the use of only one struc- ture for all the translation process (asln the former) and foreseeable decidability and parallel- ism (as in the latter). This paper presents a pro- totype, not completely operational, that uses c-graphs and is intended to translate assemblers to refine the adequacy of this kind of structure in the translation of natural languages. 2. DEFINITIONS C-graph. A c-graph G is a cycle free,labelled graph [1,9] without isolated nodes and with exactly one entry node and one exit node. It is completely determined by a 7-tupie: G=(A,S,p,I,O,E,¢), where A is a set of arcs, S a set of nodes, p a mapping of A into SxS, I the input node, 0 the output node, E a set of labels (c-trees, c-graphs) and E a map- ping of A into E. For the sake of simplicity, arcs and labels will be merged in the representation of G (cf. Fig.1 . Interesting c-graphs are sequential c-graphs (cf. Fig.2a) and bundles (cf. Fig.2b). G= 1 ~ 7 h~...~ e -- v k A={1 ..... 12} ; S={1 ..... 7} ; I={1} ; 0={7} p={ (1,1,2), (2,2,4), (3,4,5), (4,5,7), (5,5,6), (6,6,7), (7,6,7), (8,2,3), (9,3,4), (10,3,5), (11,1,2), (12,1,2)} E={a,b,c,d,e,f,g,h,i ,j,k} E={ (I ,a), (2,b), (3,f), (4,g), (5, i), (6,j), (7,k), (8,c), (9,d), (lO,e), (11,b), (12,h) } Fig.1. A c-graph. GI= ~ i :c J ~o (a) (b) Fig.2. A seq. c-graph (a) and a bundle (b). C-trees. A c-tree or a tree with decorations is an ordered tree, with nodes labelled by a label and a decoration that is itself a decorated tree, possibly empty. Classes of c-graphs. There are three major classes: (1) recursive c-graphs (cf. Fig.3a) where each arc is labelled by a c-graph; (2) simple c-graphs (cf. Fig.l) …

Content truncated to 500 words