Descriptional complexity of bounded context-free languages

DOI10.1016/j.ic.2013.03.008zbMath1358.68173OpenAlexW1983646390WikidataQ61677498 ScholiaQ61677498MaRDI QIDQ383365

Andreas Malcher, Giovanni Pighizzini

Publication date: 4 December 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2013.03.008

zbMATH Keywords

automataformal languagesbounded languagesdescriptional complexityfinite-turn pushdown automatarecursive trade-offs

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

Complexity of multi-head finite automata: origins and directions ⋮ Limited automata and unary languages ⋮ Descriptional Complexity of Bounded Regular Languages

Uses Software

• ALGOL 60

Cites Work

• Complexity of normal form grammars
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• On One-Way Cellular Arrays
• Bounded Algol-Like Languages
• Finite-Turn Pushdown Automata
• Two Families of Languages Related to ALGOL
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Descriptional complexity of bounded context-free languages