GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM

DOI10.1142/S0129054107005182zbMath1183.68321OpenAlexW1975671819MaRDI QIDQ3401456

Peter R. J. Asveld

Publication date: 29 January 2010

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054107005182

zbMATH Keywords

permutationcontext-free grammarcyclic shiftdescriptional complexityGreibach normal formcircular shiftunambiguous grammar

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (4)

Generating all permutations by context-free grammars in Greibach normal form ⋮ Permuting operations on strings and their relation to prime numbers ⋮ Lower bounds for context-free grammars ⋮ Language operations with regular expressions of polynomial size

Cites Work

• 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
• Generating all permutations by context-free grammars in Chomsky normal form
• Some classifications of context-free languages
• Unnamed Item

This page was built for publication: GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM