On the Generative Power of Cancel Minimal Linear Grammars with Single Nonterminal Symbol except the Start Symbol

Kaoru FUJIOKA; Hirofumi KATSUNO

doi:10.1587/transinf.E94.D.1945

On the Generative Power of Cancel Minimal Linear Grammars with Single Nonterminal Symbol except the Start Symbol

Kaoru FUJIOKA, Hirofumi KATSUNO

Full Text Views

0

Cite this

Summary :

This paper concerns cancel minimal linear grammars ([5]) that was introduced to generalize Geffert normal forms for phrase structure grammars. We consider the generative power of restricted cancel minimal linear grammars: the grammars have only one nonterminal symbol C except the start symbol S, and their productions consist of context-free type productions, the left-hand side of which is S and the right-hand side contains at most one occurrence of S, and a unique cancellation production C^m ε that replaces the string C^m by the empty string ε. We show that, for any given positive integer m, the class of languages generated by cancel minimal linear grammars with C^m ε, is properly included in the class of linear languages. Conversely, we show that for any linear language L, there exists some positive integer m such that a cancel minimal linear grammar with C^m ε generates L. We also show how the generative power of cancel minimal linear grammars with a unique cancellation production C^m ε vary according to changes of m and restrictions imposed on occurrences of terminal symbols in the right-hand side of productions.

Publication: IEICE TRANSACTIONS on Information Vol.E94-D No.10 pp.1945-1954

Publication Date: 2011/10/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E94.D.1945

Type of Manuscript: PAPER

Category: Fundamentals of Information Systems

Cite this

Copy

Kaoru FUJIOKA, Hirofumi KATSUNO, "On the Generative Power of Cancel Minimal Linear Grammars with Single Nonterminal Symbol except the Start Symbol" in IEICE TRANSACTIONS on Information, vol. E94-D, no. 10, pp. 1945-1954, October 2011, doi: 10.1587/transinf.E94.D.1945.
Abstract: This paper concerns cancel minimal linear grammars ([5]) that was introduced to generalize Geffert normal forms for phrase structure grammars. We consider the generative power of restricted cancel minimal linear grammars: the grammars have only one nonterminal symbol C except the start symbol S, and their productions consist of context-free type productions, the left-hand side of which is S and the right-hand side contains at most one occurrence of S, and a unique cancellation production C^m ε that replaces the string C^m by the empty string ε. We show that, for any given positive integer m, the class of languages generated by cancel minimal linear grammars with C^m ε, is properly included in the class of linear languages. Conversely, we show that for any linear language L, there exists some positive integer m such that a cancel minimal linear grammar with C^m ε generates L. We also show how the generative power of cancel minimal linear grammars with a unique cancellation production C^m ε vary according to changes of m and restrictions imposed on occurrences of terminal symbols in the right-hand side of productions.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.1945/_p

Copy

@ARTICLE{e94-d_10_1945,
author={Kaoru FUJIOKA, Hirofumi KATSUNO, },
journal={IEICE TRANSACTIONS on Information},
title={On the Generative Power of Cancel Minimal Linear Grammars with Single Nonterminal Symbol except the Start Symbol},
year={2011},
volume={E94-D},
number={10},
pages={1945-1954},
abstract={This paper concerns cancel minimal linear grammars ([5]) that was introduced to generalize Geffert normal forms for phrase structure grammars. We consider the generative power of restricted cancel minimal linear grammars: the grammars have only one nonterminal symbol C except the start symbol S, and their productions consist of context-free type productions, the left-hand side of which is S and the right-hand side contains at most one occurrence of S, and a unique cancellation production C^m ε that replaces the string C^m by the empty string ε. We show that, for any given positive integer m, the class of languages generated by cancel minimal linear grammars with C^m ε, is properly included in the class of linear languages. Conversely, we show that for any linear language L, there exists some positive integer m such that a cancel minimal linear grammar with C^m ε generates L. We also show how the generative power of cancel minimal linear grammars with a unique cancellation production C^m ε vary according to changes of m and restrictions imposed on occurrences of terminal symbols in the right-hand side of productions.},
keywords={},
doi={10.1587/transinf.E94.D.1945},
ISSN={1745-1361},
month={October},}

Copy

TY - JOUR
TI - On the Generative Power of Cancel Minimal Linear Grammars with Single Nonterminal Symbol except the Start Symbol
T2 - IEICE TRANSACTIONS on Information
SP - 1945
EP - 1954
AU - Kaoru FUJIOKA
AU - Hirofumi KATSUNO
PY - 2011
DO - 10.1587/transinf.E94.D.1945
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2011
AB - This paper concerns cancel minimal linear grammars ([5]) that was introduced to generalize Geffert normal forms for phrase structure grammars. We consider the generative power of restricted cancel minimal linear grammars: the grammars have only one nonterminal symbol C except the start symbol S, and their productions consist of context-free type productions, the left-hand side of which is S and the right-hand side contains at most one occurrence of S, and a unique cancellation production C^m ε that replaces the string C^m by the empty string ε. We show that, for any given positive integer m, the class of languages generated by cancel minimal linear grammars with C^m ε, is properly included in the class of linear languages. Conversely, we show that for any linear language L, there exists some positive integer m such that a cancel minimal linear grammar with C^m ε generates L. We also show how the generative power of cancel minimal linear grammars with a unique cancellation production C^m ε vary according to changes of m and restrictions imposed on occurrences of terminal symbols in the right-hand side of productions.
ER -