IEICE TRANSACTIONS on Information
Tree Automaton with Tree Memory
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E81-D No.2 pp.161-170
- Publication Date
- 1998/02/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Automata,Languages and Theory of Computing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ryuichi NAKANISHI, Izumi HAYAKAWA, Hiroyuki SEKI, "Tree Automaton with Tree Memory" in IEICE TRANSACTIONS on Information,
vol. E81-D, no. 2, pp. 161-170, February 1998, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e81-d_2_161/_p
Copy
@ARTICLE{e81-d_2_161,
author={Ryuichi NAKANISHI, Izumi HAYAKAWA, Hiroyuki SEKI, },
journal={IEICE TRANSACTIONS on Information},
title={Tree Automaton with Tree Memory},
year={1998},
volume={E81-D},
number={2},
pages={161-170},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Tree Automaton with Tree Memory
T2 - IEICE TRANSACTIONS on Information
SP - 161
EP - 170
AU - Ryuichi NAKANISHI
AU - Izumi HAYAKAWA
AU - Hiroyuki SEKI
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E81-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 1998
AB - 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.
ER -
English
