Iterative tree automata

The iterative tree automaton is introduced as a binary tree-connected network with sequential input and output at the root of the tree. The real and linear time computational power of this type of systolic system as a language acceptor is studied. It is shown that for real-time computations the arity of the tree is essential while this is not the case for linear-time computations. Our main result is that every T(n)-time nondeterministic Turing machine can be simulated by an ITA in (deterministic) cT(n)-time. A number of properties of real-and linear-time ITA are proved.

Authors

• Karel Culik
• Sheng Yu

Keywords

No keywords are indexed for this paper.