Generating all permutations by context-free grammars in Greibach normal form

P.R.J. Asveld

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)
    26 Downloads (Pure)

    Abstract

    We consider context-free grammars $G_n$ in Greibach normal form and, particularly, in Greibach $m$-form ($m=1,2$) which generates the finite language $L_n$ of all $n!$ strings that are permutations of $n$ different symbols ($n\geq 1$). These grammars are investigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols and the number of production rules of $G_n$ as functions of $n$. As in the case of Chomsky normal form these descriptional complexity measures grow faster than any polynomial function.
    Original languageUndefined
    Article number10.1016/j.tcs.2008.09.033
    Pages (from-to)565-577
    Number of pages13
    JournalTheoretical computer science
    Volume409
    Issue number3
    DOIs
    Publication statusPublished - 2008

    Keywords

    • HMI-SLT: Speech and Language Technology
    • EWI-14210
    • METIS-255194
    • IR-62558

    Cite this