Tech Reports Home Contact
Technical Report Series
Submit Report
Browse Reports
Information for Authors
Contact Details

Technical Report HW-MACS-TR-0061

TitleOn Stateless Multihead Finite Automata and Multihead Pushdown Automata
AuthorsPierluigi Frisco, Oscar H Ibarra
AbstractA stateless k-head two-way deterministic finite automaton (k-head 2DFA), has only one state, hence the designation stateless. Its transitions depends solely on the symbols currently scanned by its k heads, and in every such transition each head can move one cell left, right, or remain stationary. An input, which is delimited by end markers, is accepted if the machine, when started with all heads on the left end marker, reaches the configuration where all the heads are on the right end marker. The nondeterministic version is denoted by k-head 2NFA. We prove that stateless (k + 1)-head 2DFAs (resp., 2NFAs) are computa- tionally more powerful than k-head 2DFAs (resp., 2NFAs), improving a recent result where it was shown that (k + 4) heads are better than k heads. We also study stateless multihead pushdown automata in their two-way and one-way, deterministic and nonderministic variations and show that for all these varieties, k + 1 heads allow more computational power than k heads. Finally, we give some characterizations of stateless multihead finite and multihead push-down automata.
GroupIntelligent Systems Laboratory


Email Technical Report's Administrator
|MACS Home| Top of the Page

Department of Computer Science, Heriot-Watt University, Riccarton, Edinburgh, EH14 4AS, +44 (0) 131 4514152

Last Updated: 02 September 2003 Copyright Heriot-Watt University, Disclaimer