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

Share/Save/Bookmark

Asveld, Peter R.J. (2008) Generating all permutations by context-free grammars in Greibach normal form. Theoretical Computer Science, 409 (3). pp. 565-577. ISSN 0304-3975

[img] PDF
Restricted to UT campus only
: Request a copy
218kB
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.
Item Type:Article
Copyright:© 2008 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/62558
Official URL:http://dx.doi.org/10.1016/j.tcs.2008.09.033
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 255194