Descriptional complexity of limited automata
From MaRDI portal
Publication:1706157
DOI10.1016/j.ic.2017.09.005zbMath1390.68404OpenAlexW2756180352MaRDI QIDQ1706157
Matthias Wendlandt, Giovanni Pighizzini, Martin Kutrib
Publication date: 21 March 2018
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2434/563015
Related Items
Unnamed Item ⋮ Linear-time limited automata ⋮ Limited automata and unary languages ⋮ Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Size complexity of rotating and sweeping automata
- State complexity of operations on two-way finite automata over a unary alphabet
- A relation between space, return and dual return complexities
- Converting two-way nondeterministic unary automata into simpler automata.
- Complementing unary nondeterministic automata
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Optimal Simulations between Unary Automata
- Limited Automata and Context-Free Languages
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
- On the maximal order in $S_n$ and $S*_n$
- SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA
- LIMITED AUTOMATA AND REGULAR LANGUAGES
- State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet
- Weight-Reducing Hennie Machines and Their Descriptional Complexity
- Computational Complexity of One-Tape Turing Machine Computations
- A generalization of context-free determinism
- Sur l'ordre maximum d'un élément dans le groupe $S_n$ des permutations
- One-tape, off-line Turing machine computations
