Real-time, pseudo real-time, and linear-time ITA (Q1089799)

A k-ary iterative tree automaton (k-ary ITA) is a potentially infinite synchronous network of finite automata structured as k-ary tree with serial input and output at the root of the tree. The computational power of an ITA in real-time, pseudo real-time and linear-time is compared. The pseudo real-time is a new notion and means that every cell of an ITA makes a fixed number of computational steps for each input symbol. It is shown that every linear-time ITA can be simulated either by a pseudo real-time ITA of the same arity or by a real-time ITA of a higher arity. As an example, an ITA implementation of real-time infinite memory is described.