IEICE TRANSACTIONS on Information
The Universal Recognition Problems for Parallel Multiple Context-Free Grammars and for Their Subclasses
Summary :
Parallel multiple context-free grammars (pmcfg's) and multiple context-free grammars (mcfg's) were introduced as extensions of context-free grammars to describe the syntax of natural languages. Pmcfg's and mcfg's deal with tuples of strings, and it has been shown that the universal recognition problem for mcfg's is EXP-POLY time-complete where the universal recognition problem is the problem to decide whether G generates w for a given grammar G and string w. In this paper, the universal recognition problems for the class of pmcfg's and for the subclass of pmcfg's with the information-lossless condition are shown to be EXP-POLY time-complete and PSPACE-complete, respectively. It is also shown that the problems for pmcfg's and for mcfg's with a bounded dimension are both
- Publication
- IEICE TRANSACTIONS on Information Vol.E75-D No.4 pp.499-508
- Publication Date
- 1992/07/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
Yuichi KAJI, Ryuichi NAKANISHI, Hiroyuki SEKI, Tadao KASAMI, "The Universal Recognition Problems for Parallel Multiple Context-Free Grammars and for Their Subclasses" in IEICE TRANSACTIONS on Information,
vol. E75-D, no. 4, pp. 499-508, July 1992, doi: .
Abstract: Parallel multiple context-free grammars (pmcfg's) and multiple context-free grammars (mcfg's) were introduced as extensions of context-free grammars to describe the syntax of natural languages. Pmcfg's and mcfg's deal with tuples of strings, and it has been shown that the universal recognition problem for mcfg's is EXP-POLY time-complete where the universal recognition problem is the problem to decide whether G generates w for a given grammar G and string w. In this paper, the universal recognition problems for the class of pmcfg's and for the subclass of pmcfg's with the information-lossless condition are shown to be EXP-POLY time-complete and PSPACE-complete, respectively. It is also shown that the problems for pmcfg's and for mcfg's with a bounded dimension are both
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_4_499/_p
Copy
@ARTICLE{e75-d_4_499,
author={Yuichi KAJI, Ryuichi NAKANISHI, Hiroyuki SEKI, Tadao KASAMI, },
journal={IEICE TRANSACTIONS on Information},
title={The Universal Recognition Problems for Parallel Multiple Context-Free Grammars and for Their Subclasses},
year={1992},
volume={E75-D},
number={4},
pages={499-508},
abstract={Parallel multiple context-free grammars (pmcfg's) and multiple context-free grammars (mcfg's) were introduced as extensions of context-free grammars to describe the syntax of natural languages. Pmcfg's and mcfg's deal with tuples of strings, and it has been shown that the universal recognition problem for mcfg's is EXP-POLY time-complete where the universal recognition problem is the problem to decide whether G generates w for a given grammar G and string w. In this paper, the universal recognition problems for the class of pmcfg's and for the subclass of pmcfg's with the information-lossless condition are shown to be EXP-POLY time-complete and PSPACE-complete, respectively. It is also shown that the problems for pmcfg's and for mcfg's with a bounded dimension are both
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - The Universal Recognition Problems for Parallel Multiple Context-Free Grammars and for Their Subclasses
T2 - IEICE TRANSACTIONS on Information
SP - 499
EP - 508
AU - Yuichi KAJI
AU - Ryuichi NAKANISHI
AU - Hiroyuki SEKI
AU - Tadao KASAMI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - July 1992
AB - Parallel multiple context-free grammars (pmcfg's) and multiple context-free grammars (mcfg's) were introduced as extensions of context-free grammars to describe the syntax of natural languages. Pmcfg's and mcfg's deal with tuples of strings, and it has been shown that the universal recognition problem for mcfg's is EXP-POLY time-complete where the universal recognition problem is the problem to decide whether G generates w for a given grammar G and string w. In this paper, the universal recognition problems for the class of pmcfg's and for the subclass of pmcfg's with the information-lossless condition are shown to be EXP-POLY time-complete and PSPACE-complete, respectively. It is also shown that the problems for pmcfg's and for mcfg's with a bounded dimension are both
ER -
English
