Multiple ContextFree Tree Grammars: Lexicalization and Characterization
Abstract
Multiple (simple) contextfree tree grammars are investigated, where "simple" means "linear and nondeleting". Every multiple contextfree tree grammar that is finitely ambiguous can be lexicalized; i.e., it can be transformed into an equivalent one (generating the same tree language) in which each rule of the grammar contains a lexical symbol. Due to this transformation, the rank of the nonterminals increases at most by 1, and the multiplicity (or fanout) of the grammar increases at most by the maximal rank of the lexical symbols; in particular, the multiplicity does not increase when all lexical symbols have rank 0. Multiple contextfree tree grammars have the same tree generating power as multicomponent tree adjoining grammars (provided the latter can use a rootmarker). Moreover, every multicomponent tree adjoining grammar that is finitely ambiguous can be lexicalized. Multiple contextfree tree grammars have the same string generating power as multiple contextfree (string) grammars and polynomial time parsing algorithms. A tree language can be generated by a multiple contextfree tree grammar if and only if it is the image of a regular tree language under a deterministic finitecopying macro tree transducer. Multiple contextfree tree grammars can be used as a synchronous translation device.
 Publication:

arXiv eprints
 Pub Date:
 July 2017
 arXiv:
 arXiv:1707.03457
 Bibcode:
 2017arXiv170703457E
 Keywords:

 Computer Science  Formal Languages and Automata Theory;
 Computer Science  Computation and Language;
 68Q45;
 F.4.2;
 F.4.3
 EPrint:
 78 pages, 13 figures