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

DOI10.1016/j.tcs.2008.09.033zbMath1155.68031OpenAlexW2155700996MaRDI QIDQ2378538

Peter R. J. Asveld

Publication date: 8 January 2009

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-greibach-normal-form(5b6305d6-c32b-4c57-8f0a-24908e44194b).html

zbMATH Keywords

permutationcontext-free grammardescriptional complexityGreibach normal formunambiguous grammar

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (3)

Permuting operations on strings and their relation to prime numbers ⋮ Lower bounds for context-free grammars ⋮ Unnamed Item

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• A pushdown automaton or a context-free grammar - which is more economical?
• A frame for general divide-and-conquer recurrences
• The inclusion problem for some subclasses of context-free languages
• Generating all permutations by context-free grammars in Chomsky normal form
• Iteration procedure for determining approximate solutions to non-linear oscillator equations
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• On reducing the number of states in a PDA
• Some classifications of context-free languages
• Two Families of Languages Related to ALGOL

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