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

(14)

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

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)