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

Peter R.J. Asveld

    Research output: Contribution to journalArticleAcademicpeer-review

    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.
    Original languageEnglish
    Pages (from-to)1139-1149
    JournalInternational journal of foundations of computer science
    Volume18
    Issue number6
    DOIs
    Publication statusPublished - 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

    Fingerprint Dive into the research topics of 'Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form'. Together they form a unique fingerprint.

  • Cite this