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

DOI10.1016/j.tcs.2005.11.010zbMath1088.68076OpenAlexW2101532935MaRDI QIDQ2368945

Peter R. J. Asveld

Publication date: 28 April 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/generating-all-permutations-by-contextfree-grammars-in-chomsky-normal-form(a88053ef-50dc-47ba-bb0f-7c82cd6ede2b).html

zbMATH Keywords

Descriptional complexityChomsky normal formPermutationContext-free grammarUnambiguous grammar

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

Generating all permutations by context-free grammars in Greibach normal form, Permuting operations on strings and their relation to prime numbers, Languages as hyperplanes: grammatical inference with string kernels, Lower bounds for context-free grammars, Unnamed Item, GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM

Uses Software

• OEIS
• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Context-free complexity of finite languages
• Complexity of normal form grammars
• A lower-bound for the number of productions required for a certain class of languages
• Concise description of finite languages
• A note on a problem in the theory of grammatical complexity
• The state complexities of some basic operations on regular languages
• A frame for general divide-and-conquer recurrences
• The inclusion problem for some subclasses of context-free languages
• Calculation of oscillatory properties of the solutions of two coupled, first order non-linear ordinary differential equations
• Functional Programs for Generating Permutations
• Some classifications of context-free languages
• Two Families of Languages Related to ALGOL