Simulations of unary one-way multi-head finite automata

DOI10.1142/S0129054114400139MaRDI QIDQ5173291zbMATH OpenFDO

Authors 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

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

Recommendations

• Size of unary one-way multi-head finite automata
• Finite automata and unary languages
• States and heads do count for unary multi-head finite automata
• Head and state hierarchies for unary multi-head finite automata
• Optimal simulations between unary automata

Cites work

• A note on semilinear sets and bounded-reversal multihead pushdown automata
• Bounded-reversal multihead finite automata languages
• Complementing unary nondeterministic automata
• Converting two-way nondeterministic unary automata into simpler automata.
• DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
• Finite automata and unary languages
• Magic numbers in the state hierarchy of finite automata
• Optimal simulations between unary automata
• Space-bounded reducibility among combinatorial problems
• State complexity of operations on two-way finite automata over a unary alphabet
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.

Cited in

(12)

• scientific article; zbMATH DE number 1502111 (Why is no real title available?)
• States and heads do count for unary multi-head finite automata
• Descriptional complexity of limited automata
• Size of unary one-way multi-head finite automata
• One-Way Multi-Head Finite Automata with Pebbles But No States
• Investigations on automata and languages over a unary alphabet
• Head and state hierarchies for unary multi-head finite automata
• Optimal simulations between unary automata
• On the descriptional power of heads, counters, and pebbles
• On simulation cost of unary limited automata
• Descriptional complexity of regular languages
• Finite automata and unary languages

This page was built for publication: Simulations of unary one-way multi-head finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5173291)