The iterative tree automata (ITAs) considered here are systolically operating, tree-structured, potentially infinite networks of finite automata. Information flows both ways between parent and child nodes; in a k-ary ITA, each node has k children. The networks are used as language recognizers, and input words are entered sequentially through the root automaton from which acceptance or rejection is also read. The paper is concerned with ITA-language families of low time complexity. Among these, the pseudo real-time languages are a new notion; pseudo real-time operation means that, between input symbols, the ITA receives a fixed number of internal clock pulses. As one might expect, every pseudo real-time ITA language can also be accepted in real time by increasing the arity of the ITA. A more surprising result is that this also holds for linear-time ITA languages. The final conclusion is that, if no restrictions are placed on arities, all three language families considered coincide. For the hardest part, the notion of an ITA with global broadcasting is introduced. The authors use the Leiserson-Saxe retiming lemma to convert ITAs with global broadcasting into ordinary ITAs [1]. Finally, the authors outline the construction of a real-time ITA memory.

The presentation is informal, and the paper is best read in conjunction with its predecessor by the same authors [2].