Real-time, pseudo real-time, and linear-time ITA. (English) Zbl 0619.68050

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.


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata
Full Text: DOI


[1] Choffrut, C.; Culik, K., On real-time cellular automata and Trellis automata, Acta inform., 21, 393-407, (1984) · Zbl 0534.68039
[2] Cole, S.N., Real-time computation by n-dimensional iterative arrays of finite-state machines, IEEE trans. comput., C-18, 4, 349-365, (1969) · Zbl 0172.20804
[3] K. Culik II, O.H. Ibarra and S. Yu, Iterative tree arrays with logarithmic depth, Internat. J. Comput. Math., to appear
[4] Culik, K.; Yu, S., Iterative tree automata, Theor. comput. sci., 32, 227-247, (1984) · Zbl 0544.68055
[5] L.J. Guibas and F.M. Liang, Systolic stacks, queues, and counters, Proc. 1982 Conf. on Advanced Research in VLSI, MIT, 155-164
[6] Leiserson, C.E.; Saxe, J.B., Optimizing synchronous systems, (), 23-26
[7] Smith, A.R., Real-time languages recognition by one-dimensional cellular automata, J. comput. system sci., 6, 233-253, (1972) · Zbl 0268.68044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.