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

DOI10.1016/J.TCS.2005.11.010MaRDI QIDQ2368945zbMATH OpenOpenAlexFDO

Authors 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

Chomsky normal formContext-free grammarDescriptional complexityPermutationUnambiguous grammar

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Generating all permutations by context-free grammars in Greibach normal form
• On permutative grammars generating context-free languages
• Generating all circular shifts by context-free grammars in Chomsky normal form
• Context-free grammars for permutations and increasing trees
• Context-free grammars, generating functions and combinatorial arrays
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• Combinatorial generation via permutation languages. I: Fundamentals
• Combinatorial generation via permutation languages
• Some combinatorial arrays generated by context-free grammars
• Random Generation of Combinatorial Structures using Context-Fee Grammars

Cites work

• A frame for general divide-and-conquer recurrences
• A lower-bound for the number of productions required for a certain class of languages
• A note on a problem in the theory of grammatical complexity
• Calculation of oscillatory properties of the solutions of two coupled, first order non-linear ordinary differential equations
• Complexity of normal form grammars
• Concise description of finite languages
• Context-free complexity of finite languages
• Functional Programs for Generating Permutations
• Generating all circular shifts by context-free grammars in Chomsky normal form
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3470037 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• scientific article; zbMATH DE number 2201362 (Why is no real title available?)
• scientific article; zbMATH DE number 3299758 (Why is no real title available?)
• Some classifications of context-free languages
• The inclusion problem for some subclasses of context-free languages
• The state complexities of some basic operations on regular languages
• Two Families of Languages Related to ALGOL

Cited in

(9)

• On permutative grammars generating context-free languages
• Lower bounds for context-free grammars
• Generating all permutations by context-free grammars in Greibach normal form
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• Generating all circular shifts by context-free grammars in Chomsky normal form
• Permuting operations on strings and their relation to prime numbers
• Languages as hyperplanes: grammatical inference with string kernels
• Optimal regular expressions for permutations
• Infinite hierarchy of permutation languages

Describes a project that uses

Uses Software

• OEIS
• ALGOL 60

This page was built for publication: Generating all permutations by context-free grammars in Chomsky normal form

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368945)