@book{5b6305d6c32b4c578f0a24908e44194b,

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

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.",

keywords = "METIS-245784, EWI-11418, HMI-SLT: Speech and Language Technology, IR-64468",

author = "P.R.J. Asveld",

year = "2007",

language = "Undefined",

series = "CTIT Technical Report Series",

publisher = "Centre for Telematics and Information Technology (CTIT)",

number = "FS-07-05/TR-CTIT-07-83",

address = "Netherlands",

}