Iterative tree automata, alternating Turing machines, and uniform Boolean circuits: relationships and characterization
Abdelaziz Fellah, Sheng Yü · 1992
We consider a class of synchronous parallel machines, called iterative tree automata (ITA) and characterize them in terms of two other parallel machines: alternating Turing machines (ATM) and uniform Boolean circuits (UBC).We show that the computation time of iterative tree automata (a generalization of iterative array automata ) and that of alternating Turing machines are linearly related.That is, there is an integer c >0 such that a language L is accepted by an ITA in time T(n) if and only if it is accepted by an ATM in time cT(n).The simulation of a T(ra)-time bounded ITA by an ATM is indeed stronger than the result given in [10, 17], where it is shown that a T(n)-time bounded ITA can be simulated by an ATM in time 0( T(n)2 ).We are also able to show that every language accepted by a T(n) -time iterative tree automaton or n-dimensional iterative array automaton (n-IAA) can be accepted by a uniform Boolean circuit of depth O(T(ra)).Moreover, a T(n) -time (n-IAA) can be simulated by an ATM in linear time.