IEICE TRANSACTIONS on transactions
Grammatical Characterizations of P and PSPACE
Summary :
The notion of alternating context-free grammar (ACFG for short) was introduced by Moriya in 1989. In this paper, we study the relationships between some complexity classes and the classes of languages generated by restricted types of ACFG's. Two restricted types of ACFG's considered are linear ACFG's and ε-free ACFG's. For an ACFG G, let Lleft (G) denote the language of terminal strings generated by leftmost derivations in G. Let
(1) the class of languages that are log-space many-one reducible to languages in ACFLlinear is equivalent to P, and
(2) the class of languages that are log-space many-one reducible to languages in
- Publication
- IEICE TRANSACTIONS on transactions Vol.E73-E No.9 pp.1540-1548
- Publication Date
- 1990/09/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Automaton, Language 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
Zhi-Zhong CHEN, Seinosuke TODA, "Grammatical Characterizations of P and PSPACE" in IEICE TRANSACTIONS on transactions,
vol. E73-E, no. 9, pp. 1540-1548, September 1990, doi: .
Abstract: The notion of alternating context-free grammar (ACFG for short) was introduced by Moriya in 1989. In this paper, we study the relationships between some complexity classes and the classes of languages generated by restricted types of ACFG's. Two restricted types of ACFG's considered are linear ACFG's and ε-free ACFG's. For an ACFG G, let Lleft (G) denote the language of terminal strings generated by leftmost derivations in G. Let
(1) the class of languages that are log-space many-one reducible to languages in ACFLlinear is equivalent to P, and
(2) the class of languages that are log-space many-one reducible to languages in
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e73-e_9_1540/_p
Copy
@ARTICLE{e73-e_9_1540,
author={Zhi-Zhong CHEN, Seinosuke TODA, },
journal={IEICE TRANSACTIONS on transactions},
title={Grammatical Characterizations of P and PSPACE},
year={1990},
volume={E73-E},
number={9},
pages={1540-1548},
abstract={The notion of alternating context-free grammar (ACFG for short) was introduced by Moriya in 1989. In this paper, we study the relationships between some complexity classes and the classes of languages generated by restricted types of ACFG's. Two restricted types of ACFG's considered are linear ACFG's and ε-free ACFG's. For an ACFG G, let Lleft (G) denote the language of terminal strings generated by leftmost derivations in G. Let
(1) the class of languages that are log-space many-one reducible to languages in ACFLlinear is equivalent to P, and
(2) the class of languages that are log-space many-one reducible to languages in
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Grammatical Characterizations of P and PSPACE
T2 - IEICE TRANSACTIONS on transactions
SP - 1540
EP - 1548
AU - Zhi-Zhong CHEN
AU - Seinosuke TODA
PY - 1990
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E73-E
IS - 9
JA - IEICE TRANSACTIONS on transactions
Y1 - September 1990
AB - The notion of alternating context-free grammar (ACFG for short) was introduced by Moriya in 1989. In this paper, we study the relationships between some complexity classes and the classes of languages generated by restricted types of ACFG's. Two restricted types of ACFG's considered are linear ACFG's and ε-free ACFG's. For an ACFG G, let Lleft (G) denote the language of terminal strings generated by leftmost derivations in G. Let
(1) the class of languages that are log-space many-one reducible to languages in ACFLlinear is equivalent to P, and
(2) the class of languages that are log-space many-one reducible to languages in
ER -
English
