Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form

Peter R.J. Asveld

doi:10.1142/S0129054107005182

Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form

Peter R.J. Asveld

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

For each alphabet Σ_n = {a₁,a₂,…,a_n}, linearly ordered by a₁ < a₂ < ⋯ < a_n, let C_n be the language of circular or cyclic shifts over Σ_n, i.e., C_n = {a₁a₂ ⋯ a_n-1a_n, a₂a₃ ⋯ a_na₁,…,a_na₁ ⋯ a_n-2a_n-1}. We study a few families of context-free grammars G_n (n ≥1) in Greibach normal form such that G_n generates C_n. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals ν(n), the number of rules π(n) and the number of leftmost derivations δ(n) of G_n. As in the case of Chomsky normal form, these ν, π and δ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal w. r. t. all these measures remains open.

Original language	English
Pages (from-to)	1139-1149
Journal	International journal of foundations of computer science
Volume	18
Issue number	6
DOIs	https://doi.org/10.1142/S0129054107005182
Publication status	Published - Dec 2007

Keywords

Context-free grammar
EWI-11338
IR-62000
descriptional complexity
HMI-SLT: Speech and Language Technology
cyclic shift
METIS-242033
unambiguous grammar
circular shift
permutation
Greibach normal form

Access to Document

10.1142/S0129054107005182

Cite this

@article{a2d1911b99394f70bf6b86c0e9348e7c,

title = "Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form",

abstract = "For each alphabet Σn = {a1,a2,…,an}, linearly ordered by a1 < a2 < ⋯ < an, let Cn be the language of circular or cyclic shifts over Σn, i.e., Cn = {a1a2 ⋯ an-1an, a2a3 ⋯ ana1,…,ana1 ⋯ an-2an-1}. We study a few families of context-free grammars Gn (n ≥1) in Greibach normal form such that Gn generates Cn. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals ν(n), the number of rules π(n) and the number of leftmost derivations δ(n) of Gn. As in the case of Chomsky normal form, these ν, π and δ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal w. r. t. all these measures remains open.",

keywords = "Context-free grammar, EWI-11338, IR-62000, descriptional complexity, HMI-SLT: Speech and Language Technology, cyclic shift, METIS-242033, unambiguous grammar, circular shift, permutation, Greibach normal form",

author = "Asveld, {Peter R.J.}",

year = "2007",

month = dec,

doi = "10.1142/S0129054107005182",

language = "English",

volume = "18",

pages = "1139--1149",

journal = "International journal of foundations of computer science",

issn = "0129-0541",

publisher = "World Scientific Press",

number = "6",

}

TY - JOUR

T1 - Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form

AU - Asveld, Peter R.J.

PY - 2007/12

Y1 - 2007/12

N2 - For each alphabet Σn = {a1,a2,…,an}, linearly ordered by a1 < a2 < ⋯ < an, let Cn be the language of circular or cyclic shifts over Σn, i.e., Cn = {a1a2 ⋯ an-1an, a2a3 ⋯ ana1,…,ana1 ⋯ an-2an-1}. We study a few families of context-free grammars Gn (n ≥1) in Greibach normal form such that Gn generates Cn. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals ν(n), the number of rules π(n) and the number of leftmost derivations δ(n) of Gn. As in the case of Chomsky normal form, these ν, π and δ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal w. r. t. all these measures remains open.

AB - For each alphabet Σn = {a1,a2,…,an}, linearly ordered by a1 < a2 < ⋯ < an, let Cn be the language of circular or cyclic shifts over Σn, i.e., Cn = {a1a2 ⋯ an-1an, a2a3 ⋯ ana1,…,ana1 ⋯ an-2an-1}. We study a few families of context-free grammars Gn (n ≥1) in Greibach normal form such that Gn generates Cn. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals ν(n), the number of rules π(n) and the number of leftmost derivations δ(n) of Gn. As in the case of Chomsky normal form, these ν, π and δ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal w. r. t. all these measures remains open.

KW - Context-free grammar

KW - EWI-11338

KW - IR-62000

KW - descriptional complexity

KW - HMI-SLT: Speech and Language Technology

KW - cyclic shift

KW - METIS-242033

KW - unambiguous grammar

KW - circular shift

KW - permutation

KW - Greibach normal form

U2 - 10.1142/S0129054107005182

DO - 10.1142/S0129054107005182

M3 - Article

VL - 18

SP - 1139

EP - 1149

JO - International journal of foundations of computer science

JF - International journal of foundations of computer science

SN - 0129-0541

IS - 6

ER -

Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form

Abstract

Keywords

Access to Document

Fingerprint

Cite this