Finite State Translation Systems and Parallel Multiple Context-Free Grammars

Yuichi KAJI  Hiroyuki SEKI  Tadao KASAMI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E77-D   No.6   pp.619-630
Publication Date: 1994/06/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata, Languages and Theory of Computing
Keyword: 
finite state translation systems,  parallel multiple context-free grammars,  tree automata,  computational complexity,  formal languages,  

Full Text: PDF>>
Buy this Article



Summary: 
Finite state translation systems (fsts') are a widely studied computational model in the area of tree automata theory. In this paper, the string generating capacities of fsts' and their subclasses are studied. First, it is shown that the class of string languages generated by deterministic fsts' equals to that of parallel multiple context-free grammars, which are an extension of context-free grammars. As a corollary, it can be concluded that the recognition problem for a deterministic fsts is solvable in O(ne1)-time, where n is the length of an input word and e is a constant called the degree of the deterministic fsts'. In contrast to the latter fact, it is also shown that nondeterministic monadic fsts' with state-bound 2 can generate an NP-complete language.