zbMATH — the first resource for mathematics

The main trands in the theory of homogeneous structures. (English. Russian original) Zbl 0796.68147
Discrete Math. Appl. 1, No. 3, 229-250 (1991); translation from Diskretn. Mat. 1, No. 3, 19-38 (1989).
Summary: This paper contains a survey of the main directions in research on the theory of homogeneous structures, which is one of the most important areas of automaton theory. Homogeneous structures form a discrete mathematical model of an automaton character, describing both temporal- logical and spatial characteristics of processes; they can be considered also as a mathematical model of homogeneous computer systems.
The survey consists of four main sections, the first of which is devoted to problems of analysis of properties of the behavior of autonomous homogeneous structures, the second, to problems of synthesis of autonomous homogeneous structures, the third, to the theory of experiments for homogeneous structures with inputs and outputs and problems of completeness for them, and the fourth, to questions of complexity of computations in homogeneous structures. We present the most important results obtained in the listed directions, and formulate some unsolved problems in the theory of homogeneous structures.
68Q45 Formal languages and automata
68M10 Network design and communication in computer systems
Full Text: DOI