@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",
}