Tree Automaton with Tree Memory

Ryuichi NAKANISHI  Izumi HAYAKAWA  Hiroyuki SEKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E81-D   No.2   pp.161-170
Publication Date: 1998/02/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata,Languages and Theory of Computing
Keyword: 
tree automaton,   tree automaton with tree memory,  formal language,  natural language,  unification-based grammar,  

Full Text: PDF>>
Buy this Article



Summary: 
In this paper, we propose an extension of finite state tree automaton, called tree automaton with tree memory (TTA), and also define structure composing TTA (SC-TTA) and backward deterministic TTA (BD-TTA) as subclasses of TTA. We show that the classes of yield languages accepted by TTAs, SC-TTAs and BD-TTAs are equal to the class of recursively enumerable languages, the class of languages generated by tree-to-string finite state translation systems (TSFSTSs) and the class of languages generated by deterministic TSFSTSs, respectively. As a corollary, it is shown that the yield language accepted by an SC-TTA (resp. a BD-TTA) is linear space (resp. polynomial time) recognizable.