Modular Real-Time Trellis Automata

Article type: Research Article

Authors: Černý, Anton^a | Gruska, Jozef^b

Affiliations: [a] Department of Theoretical Cybernetics, Komensky University, Mlynská dolina, 824 15 Bratislava, Czechoslovakia | [b] Institute of Technical Cybernetics, Slovak Academy of Sciences, Dúbravska cesta 9, 84237 Bratislava, Czechoslovakia

Abstract: A new type of nonhomogeneous real time trellis automata, the so-called modular trellis automata, is introduced and various results concerning their normal forms, power, simulations, and decision problems are shown. Modular trellis automata are a mathematical abstraction, in the form of a recognizer, of an intuitive notion of an array of simple processors assembled in a simple and modular way. Distribution of processors in a real-time trellis automaton forms a two-dimensional structure called trellis. Basic characterizations and properties of modular trellises are summarized and modularity of various special trellises – regular, product, self-embedding, and self-overlapping – is investigated.

DOI: 10.3233/FI-1986-9302

Journal: Fundamenta Informaticae, vol. 9, no. 3, pp. 253-282, 1986