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

P.R.J. Asveld

    Research output: Contribution to journalArticleAcademicpeer-review

    9 Citations (Scopus)
    83 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

    @article{a88053ef50dc47babb0f7c82cd6ede2b,
    title = "Generating all permutations by context-free grammars in Chomsky normal form",
    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$.",
    keywords = "MSC-68Q45, MSC-68Q42, EWI-2711, METIS-238004, HMI-SLT: Speech and Language Technology, IR-55941",
    author = "P.R.J. Asveld",
    note = "10.1016/j.tcs.2005.11.010",
    year = "2006",
    doi = "10.1016/j.tcs.2005.11.010",
    language = "Undefined",
    volume = "354",
    pages = "118--130",
    journal = "Theoretical computer science",
    issn = "0304-3975",
    publisher = "Elsevier",
    number = "2/1",

    }

    Generating all permutations by context-free grammars in Chomsky normal form. / Asveld, P.R.J.

    In: Theoretical computer science, Vol. 354, No. 2/1, 2006, p. 118-130.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

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

    AU - Asveld, P.R.J.

    N1 - 10.1016/j.tcs.2005.11.010

    PY - 2006

    Y1 - 2006

    N2 - 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$.

    AB - 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$.

    KW - MSC-68Q45

    KW - MSC-68Q42

    KW - EWI-2711

    KW - METIS-238004

    KW - HMI-SLT: Speech and Language Technology

    KW - IR-55941

    U2 - 10.1016/j.tcs.2005.11.010

    DO - 10.1016/j.tcs.2005.11.010

    M3 - Article

    VL - 354

    SP - 118

    EP - 130

    JO - Theoretical computer science

    JF - Theoretical computer science

    SN - 0304-3975

    IS - 2/1

    ER -