Stack Tree Automata and Their Relation to Context-Free Grammars with Memory
Summary :
As a generalization of the tree automaton, tree automata with various types of memory are introduced and their relation to context-free grammars with memory is studied. Relations between computation trees of tree automata with memory and derivation trees of context-free grammars with memory are established, and as a consequence, the languages generated by context-free grammars with memory are characterized in terms of the sets of trees recognizable by tree automata with memory. Also various types of traversal of labeled trees recognizable by tree automata with memory are considered.
- Publication
- IEICE TRANSACTIONS on Information Vol.E77-D No.10 pp.1086-1093
- Publication Date
- 1994/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- 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
Etsuro MORIYA, "Stack Tree Automata and Their Relation to Context-Free Grammars with Memory" in IEICE TRANSACTIONS on Information,
vol. E77-D, no. 10, pp. 1086-1093, October 1994, doi: .
Abstract: As a generalization of the tree automaton, tree automata with various types of memory are introduced and their relation to context-free grammars with memory is studied. Relations between computation trees of tree automata with memory and derivation trees of context-free grammars with memory are established, and as a consequence, the languages generated by context-free grammars with memory are characterized in terms of the sets of trees recognizable by tree automata with memory. Also various types of traversal of labeled trees recognizable by tree automata with memory are considered.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_10_1086/_p
Copy
@ARTICLE{e77-d_10_1086,
author={Etsuro MORIYA, },
journal={IEICE TRANSACTIONS on Information},
title={Stack Tree Automata and Their Relation to Context-Free Grammars with Memory},
year={1994},
volume={E77-D},
number={10},
pages={1086-1093},
abstract={As a generalization of the tree automaton, tree automata with various types of memory are introduced and their relation to context-free grammars with memory is studied. Relations between computation trees of tree automata with memory and derivation trees of context-free grammars with memory are established, and as a consequence, the languages generated by context-free grammars with memory are characterized in terms of the sets of trees recognizable by tree automata with memory. Also various types of traversal of labeled trees recognizable by tree automata with memory are considered.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - Stack Tree Automata and Their Relation to Context-Free Grammars with Memory
T2 - IEICE TRANSACTIONS on Information
SP - 1086
EP - 1093
AU - Etsuro MORIYA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 1994
AB - As a generalization of the tree automaton, tree automata with various types of memory are introduced and their relation to context-free grammars with memory is studied. Relations between computation trees of tree automata with memory and derivation trees of context-free grammars with memory are established, and as a consequence, the languages generated by context-free grammars with memory are characterized in terms of the sets of trees recognizable by tree automata with memory. Also various types of traversal of labeled trees recognizable by tree automata with memory are considered.
ER -
English
