IEICE TRANSACTIONS on Information
Some EXPTIME Complete Problems on Context-Free Languages
Summary :
Some problems in formal language theory are considered and are shown to be deterministic exponential time complete. They include the problems for a given context-free grammar G, a nondeterministic finite automaton M, a deterministic pushdown automaton MD, of determining whether L(G)
- Publication
- IEICE TRANSACTIONS on Information Vol.E76-D No.3 pp.329-335
- Publication Date
- 1993/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithm and Computational Complexity
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
Takumi KASAI, Shigeki IWATA, "Some EXPTIME Complete Problems on Context-Free Languages" in IEICE TRANSACTIONS on Information,
vol. E76-D, no. 3, pp. 329-335, March 1993, doi: .
Abstract: Some problems in formal language theory are considered and are shown to be deterministic exponential time complete. They include the problems for a given context-free grammar G, a nondeterministic finite automaton M, a deterministic pushdown automaton MD, of determining whether L(G)
URL: https://global.ieice.org/en_transactions/information/10.1587/e76-d_3_329/_p
Copy
@ARTICLE{e76-d_3_329,
author={Takumi KASAI, Shigeki IWATA, },
journal={IEICE TRANSACTIONS on Information},
title={Some EXPTIME Complete Problems on Context-Free Languages},
year={1993},
volume={E76-D},
number={3},
pages={329-335},
abstract={Some problems in formal language theory are considered and are shown to be deterministic exponential time complete. They include the problems for a given context-free grammar G, a nondeterministic finite automaton M, a deterministic pushdown automaton MD, of determining whether L(G)
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - Some EXPTIME Complete Problems on Context-Free Languages
T2 - IEICE TRANSACTIONS on Information
SP - 329
EP - 335
AU - Takumi KASAI
AU - Shigeki IWATA
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E76-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 1993
AB - Some problems in formal language theory are considered and are shown to be deterministic exponential time complete. They include the problems for a given context-free grammar G, a nondeterministic finite automaton M, a deterministic pushdown automaton MD, of determining whether L(G)
ER -
English
