Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

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

Share/Save/Bookmark

Asveld, Peter R.J. (2006) Generating all permutations by context-free grammars in Chomsky normal form. Theoretical Computer Science, 354 (1). pp. 118-130. ISSN 0304-3975

[img]PDF
Restricted to UT campus only: Request a copy
260Kb
[img]PDF (Author's edition)
188Kb
Abstract:Let Ln be the finite language of all n! strings that are permutations of n different symbols (n1). We consider context-free grammars Gn in Chomsky normal form that generate Ln. In particular we study a few families {Gn}n1, satisfying L(Gn)=Ln for n1, with respect to their descriptional complexity, i.e. we determine the number of nonterminal symbols and the number of production rules of Gn as functions of n.
Item Type:Article
Copyright:© 2005 Elsevier B.V.
Research Group:
Link to this item:http://purl.utwente.nl/publications/55941
Official URL:http://dx.doi.org/10.1016/j.tcs.2005.11.010
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 238004