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

P.R.J. Asveld

    Research output: Contribution to journalArticleAcademicpeer-review

    10 Citations (Scopus)
    220 Downloads (Pure)

    Abstract

    Let $L_n$ be the finite language of all $n!$ strings that are permutations of $n$ different symbols ($n\geq1$). We consider context-free grammars $G_n$ in Chomsky normal form that generate $L_n$. In particular we study a few families $\{G_n\}_{n\geq1}$, satisfying $L(G_n)=L_n$ for $n\geq1$, 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 function of $n$.
    Original languageUndefined
    Pages (from-to)118-130
    Number of pages13
    JournalTheoretical computer science
    Volume354
    Issue number2/1
    DOIs
    Publication statusPublished - 2006

    Keywords

    • MSC-68Q45
    • MSC-68Q42
    • EWI-2711
    • METIS-238004
    • HMI-SLT: Speech and Language Technology
    • IR-55941

    Cite this