Multi-head finite automata: characterizations, concepts and open problems

MaRDI QIDQ5145152zbMATH OpenFDO

Authors Markus Holzer, Martin Kutrib, Andreas Malcher

Publication date 20 January 2021

Full work available at URL https://arxiv.org/abs/0906.3051, http://eptcs.web.cse.unsw.edu.au/paper.cgi?CSP08.9

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Complexity of multi-head finite automata: origins and directions
• Some characterizations of multihead finite automata
• Alternating multihead finite automata
• On Stateless Multihead Automata: Hierarchies and the Emptiness Problem
• On stateless multihead automata: hierarchies and the emptiness problem

Cited in

(17)

• Alternating multihead finite automata
• Multihead one-way finite automata
• Refined simulation of multihead automata
• Multi-head finite automata: Data-independent versus data-dependent computations
• Bounded monotone recursion and multihead automata
• On partially blind multihead finite automata.
• Logarithmic space and permutations
• On computational power of partially blind automata
• Finite dP Automata versus Multi-head Finite Automata
• A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
• Some characterizations of multihead finite automata
• scientific article; zbMATH DE number 4106277 (Why is no real title available?)
• scientific article; zbMATH DE number 1015106 (Why is no real title available?)
• scientific article; zbMATH DE number 1361488 (Why is no real title available?)
• Plane-walking automata
• Complexity of multi-head finite automata: origins and directions
• Agafonov's theorem for finite and infinite alphabets and probability distributions different from equidistribution

This page was built for publication: Multi-head finite automata: characterizations, concepts and open problems

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