THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS

DOI10.1142/S0129054105003406zbMath1090.68058MaRDI QIDQ5704376

Martin Kutrib

Publication date: 14 November 2005

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

zbMATH Keywords

descriptional complexitymultihead finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Related Items

The chop of languages ⋮ One-way reversible multi-head finite automata ⋮ On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata ⋮ Document spanners: from expressive power to decision problems ⋮ Extended regular expressions: succinctness and decidability ⋮ Descriptional complexity of bounded context-free languages ⋮ Expressiveness and static analysis of extended conjunctive regular path queries ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Languages generated by conjunctive query fragments of FC[REG] ⋮ Non-recursive trade-offs between two-dimensional automata and grammars ⋮ OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA ⋮ ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA ⋮ Succinct description of regular languages by weak restarting automata ⋮ SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA ⋮ Syntax checking either way ⋮ SUBLINEARLY SPACE BOUNDED ITERATIVE ARRAYS

Cites Work

• Unnamed Item
• On Goedel speed-up and succinctness of language representations
• Reversal-bounded multipushdown machines
• The Turing degree of the inherent ambiguity problem for context-free languages
• The state complexities of some basic operations on regular languages
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Size/lookahead tradeoff for \(LL(k)\)-grammars
• On the descriptional power of heads, counters, and pebbles
• On the Succinctness of Different Representations of Languages
• A note on the succinctness of descriptions of deterministic languages
• Succinctness of Descriptions of Unambiguous Context-Free Languages
• k + 1 Heads Are Better than k
• State-complexity of finite-state devices, state compressibility and incompressibility
• Deterministic context free languages
• The Unsolvability of the Recognition of Linear Context-Free Languages
• A regularity test for pushdown machines
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES