Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.

DOI10.1006/jcss.2002.1855zbMath1059.68068OpenAlexW2057559629WikidataQ61677528 ScholiaQ61677528MaRDI QIDQ1872711

Giovanni Pighizzini, Jeffrey O. Shallit, Wang, Ming-wei

Publication date: 14 May 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b3c2089671067248430081472e527cccceeff260

zbMATH Keywords

context-free grammarsformal languagespushdown automatadescriptional complexityspace complexity.

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (21)

Parikh’s Theorem and Descriptional Complexity ⋮ Descriptional complexity of bounded context-free languages ⋮ Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata ⋮ (Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars ⋮ Non-recursive trade-offs between two-dimensional automata and grammars ⋮ Deciding determinism of unary languages ⋮ Two-way machines and de Bruijn words ⋮ Descriptional complexity of limited automata ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ Non-Self-Embedding Grammars and Descriptional Complexity ⋮ SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Pushdown automata and constant height: decidability and bounds ⋮ Deterministic Pushdown Automata and Unary Languages ⋮ Limited automata and unary languages ⋮ Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals ⋮ DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ On Simulation Cost of Unary Limited Automata ⋮ Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata ⋮ Undecidability of the emptiness problem for context-free picture languages

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Plus petit commun multiple des termes consécutifs d'une suite récurrente linéaire. (Least common multiple of consecutive terms of a linear recurrent sequence)
• Finite automata and unary languages
• A pushdown automaton or a context-free grammar - which is more economical?
• Bridging across the \(\log(n)\) space frontier
• Automaticity. I: Properties of a measure of descriptional complexity
• Optimal Simulations between Unary Automata
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
• Sublogarithmic Bounds on Space and Reversals
• Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines
• On Context-Free Languages
• Two Families of Languages Related to ALGOL
• Some Results on Tape-Bounded Turing Machines
• On a Problem of Partitions

This page was built for publication: Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.