On Simulation Cost of Unary Limited Automata
From MaRDI portal
Publication:5500689
DOI10.1007/978-3-319-19225-3_13zbMath1390.68405MaRDI QIDQ5500689
Martin Kutrib, Matthias Wendlandt
Publication date: 7 August 2015
Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-19225-3_13
68Q45: Formal languages and automata
Related Items
Deterministic Stack Transducers, Limited automata and unary languages, Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata, Descriptional complexity of regular languages, Deterministic Stack Transducers, Reversible Limited Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Size complexity of rotating and sweeping automata
- State complexity of operations on two-way finite automata over a unary alphabet
- 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
