On the Generative Powers of Some Extensions of Minimal Linear Grammars
Summary :
This paper concerns the Geffert normal forms for phrase structure grammars. We first generalize them to have a new formulation of minimal linear grammars with cancellation productions, called "cancel minimal linear grammars". Then the generative powers of some classes of those grammars are investigated. It is shown that the class of languages generated by grammars with a unique {AB}-cancellation production properly includes the class of linear languages, while it is included in the class of context-free languages. Furthermore, the corresponding class of languages generated by grammars with a unique {AA}-cancellation production is shown to be a proper subclass of linear languages.
- Publication
- IEICE TRANSACTIONS on Information Vol.E90-D No.6 pp.895-904
- Publication Date
- 2007/06/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e90-d.6.895
- Type of Manuscript
- PAPER
- Category
- Automata and Formal Language Theory
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
Kaoru ONODERA, "On the Generative Powers of Some Extensions of Minimal Linear Grammars" in IEICE TRANSACTIONS on Information,
vol. E90-D, no. 6, pp. 895-904, June 2007, doi: 10.1093/ietisy/e90-d.6.895.
Abstract: This paper concerns the Geffert normal forms for phrase structure grammars. We first generalize them to have a new formulation of minimal linear grammars with cancellation productions, called "cancel minimal linear grammars". Then the generative powers of some classes of those grammars are investigated. It is shown that the class of languages generated by grammars with a unique {AB}-cancellation production properly includes the class of linear languages, while it is included in the class of context-free languages. Furthermore, the corresponding class of languages generated by grammars with a unique {AA}-cancellation production is shown to be a proper subclass of linear languages.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e90-d.6.895/_p
Copy
@ARTICLE{e90-d_6_895,
author={Kaoru ONODERA, },
journal={IEICE TRANSACTIONS on Information},
title={On the Generative Powers of Some Extensions of Minimal Linear Grammars},
year={2007},
volume={E90-D},
number={6},
pages={895-904},
abstract={This paper concerns the Geffert normal forms for phrase structure grammars. We first generalize them to have a new formulation of minimal linear grammars with cancellation productions, called "cancel minimal linear grammars". Then the generative powers of some classes of those grammars are investigated. It is shown that the class of languages generated by grammars with a unique {AB}-cancellation production properly includes the class of linear languages, while it is included in the class of context-free languages. Furthermore, the corresponding class of languages generated by grammars with a unique {AA}-cancellation production is shown to be a proper subclass of linear languages.},
keywords={},
doi={10.1093/ietisy/e90-d.6.895},
ISSN={1745-1361},
month={June},}
Copy
TY - JOUR
TI - On the Generative Powers of Some Extensions of Minimal Linear Grammars
T2 - IEICE TRANSACTIONS on Information
SP - 895
EP - 904
AU - Kaoru ONODERA
PY - 2007
DO - 10.1093/ietisy/e90-d.6.895
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2007
AB - This paper concerns the Geffert normal forms for phrase structure grammars. We first generalize them to have a new formulation of minimal linear grammars with cancellation productions, called "cancel minimal linear grammars". Then the generative powers of some classes of those grammars are investigated. It is shown that the class of languages generated by grammars with a unique {AB}-cancellation production properly includes the class of linear languages, while it is included in the class of context-free languages. Furthermore, the corresponding class of languages generated by grammars with a unique {AA}-cancellation production is shown to be a proper subclass of linear languages.
ER -
English
