SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA

DOI10.1142/S0129054114400139zbMath1320.68112MaRDI QIDQ5173291

Martin Kutrib, Andreas Malcher, Matthias Wendlandt

Publication date: 9 February 2015

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

zbMATH Keywords

descriptional complexityunary languagesmulti-head finite automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (4)

Descriptional complexity of limited automata ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Descriptional complexity of regular languages ⋮ On Simulation Cost of Unary Limited Automata

Cites Work

• State complexity of operations on two-way finite automata over a unary alphabet
• Finite automata and unary languages
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• Space-bounded reducibility among combinatorial problems
• 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.
• Magic numbers in the state hierarchy of finite automata
• Optimal Simulations between Unary Automata
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
• Bounded-reversal multihead finite automata languages
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS

This page was built for publication: SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA