IEICE TRANSACTIONS on Information
Linear-Time Recognizable Classes of Tree Languages by Deterministic Linear Pushdown Tree Automata
Summary :
In this paper, we study deterministic linear pushdown tree automata (deterministic L-PDTAs) and some variations. Since recognition of an input tree by a deterministic L-PDTA can be done in linear time, deterministic L-PDTAs are applicable to many kinds of applications. A strict hierarchy will be shown among the classes of tree languages defined by a variety of deterministic L-PDTAs. It will be also shown that deterministic L-PDTAs are weakly equivalent to nondeterministic L-PDTAs.
- Publication
- IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.248-254
- Publication Date
- 2009/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E92.D.248
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
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
Akio FUJIYOSHI, "Linear-Time Recognizable Classes of Tree Languages by Deterministic Linear Pushdown Tree Automata" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 2, pp. 248-254, February 2009, doi: 10.1587/transinf.E92.D.248.
Abstract: In this paper, we study deterministic linear pushdown tree automata (deterministic L-PDTAs) and some variations. Since recognition of an input tree by a deterministic L-PDTA can be done in linear time, deterministic L-PDTAs are applicable to many kinds of applications. A strict hierarchy will be shown among the classes of tree languages defined by a variety of deterministic L-PDTAs. It will be also shown that deterministic L-PDTAs are weakly equivalent to nondeterministic L-PDTAs.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.248/_p
Copy
@ARTICLE{e92-d_2_248,
author={Akio FUJIYOSHI, },
journal={IEICE TRANSACTIONS on Information},
title={Linear-Time Recognizable Classes of Tree Languages by Deterministic Linear Pushdown Tree Automata},
year={2009},
volume={E92-D},
number={2},
pages={248-254},
abstract={In this paper, we study deterministic linear pushdown tree automata (deterministic L-PDTAs) and some variations. Since recognition of an input tree by a deterministic L-PDTA can be done in linear time, deterministic L-PDTAs are applicable to many kinds of applications. A strict hierarchy will be shown among the classes of tree languages defined by a variety of deterministic L-PDTAs. It will be also shown that deterministic L-PDTAs are weakly equivalent to nondeterministic L-PDTAs.},
keywords={},
doi={10.1587/transinf.E92.D.248},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Linear-Time Recognizable Classes of Tree Languages by Deterministic Linear Pushdown Tree Automata
T2 - IEICE TRANSACTIONS on Information
SP - 248
EP - 254
AU - Akio FUJIYOSHI
PY - 2009
DO - 10.1587/transinf.E92.D.248
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2009
AB - In this paper, we study deterministic linear pushdown tree automata (deterministic L-PDTAs) and some variations. Since recognition of an input tree by a deterministic L-PDTA can be done in linear time, deterministic L-PDTAs are applicable to many kinds of applications. A strict hierarchy will be shown among the classes of tree languages defined by a variety of deterministic L-PDTAs. It will be also shown that deterministic L-PDTAs are weakly equivalent to nondeterministic L-PDTAs.
ER -
English
