Simulations of unary one-way multi-head finite automata

DOI10.1142/S0129054114400139zbMATH Open1320.68112MaRDI QIDQ5173291FDOQ5173291

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)

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

zbMATH Keywords

descriptional complexityunary languagesmulti-head finite automata

Mathematics Subject Classification ID

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

Cites Work

• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Finite automata and unary languages
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
• 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
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• Converting two-way nondeterministic unary automata into simpler automata.
• Complementing unary nondeterministic automata
• State complexity of operations on two-way finite automata over a unary alphabet
• Bounded-reversal multihead finite automata languages
• Space-bounded reducibility among combinatorial problems
• DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES

Cited In (12)

• Title not available (Why is that?)
• 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 simulation cost of unary limited automata
• On the descriptional power of heads, counters, and pebbles
• 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)