Издательство North Holland, 1991, -424 pp.
The subject of research in automata theory is a design of mathematical models describing methods of information transformation in digital systems. Automata theory is especially conceed with abstract models of systems working by means of discrete signals, known as digital signals. Special emphasis has been put on digital computers, digital systems of control for technological processes, and digital systems of data transmission. On the other hand, automata theory as one of the branches of general system theory, gives tools needed for formulation and solution of general problems, which can be applied for solving known problems, and also for solving problems in the future. Automata theory is in fact a part of computability theory which covers problems of computer systems, software, activity of nervous systems (neural networks), and processes of live organisms development.
Automaton, in particular a finite automaton, is an abstract mathematical concept, a computability model or a model of some process. In the research in automata theory one uses general algebra and graph theory. Some algebraic concepts have their origin in computer systems. These concepts in their formal forms are analyzed and transformed to new forms more convenient for optimization. Finally, during synthesis process, abstract concepts are converted to digital schema, or a flow diagram to be implemented in software. This denotes that automata theory teaches how conceptually and computationally one can consider problems in computer science growing up with respect to magnitude and complexity. Simultaneously, automata theory underlines elements of creativity, because thinking process is of heuristic nature in this branch of computer science. The development of automata theory in sixties and seventies has been stimulated by two complementary tendencies:
i) design of models closely related to existing hardware and software
ii) definition of appropriate mathematical tools (mathematical languages) by means of which one can describe computational processes.
During this period there was a tremendous increase in the use of digital computers in different branches of manufacturing, as well as in research on utilization methods, analysis and synthesis of digital systems to control technological processes taking into account the scale of integration and functional complexity of digital blocks.
Historically, automata theory is a branch of computer science strongly related to mathematical linguistics, discrete mathematics, and engineering of digital systems. This relationship results from the nature of the automaton concept; i.e. automaton can be understood as the acceptor of languages, abstract algebra, oriented graph, digital signal transducer, and mathematical model of digital systems. These facts indicate the interdisciplinary character of automata theory, and also its cognitive value with respect to modeling of technical processes. In the fifties and the first half of sixties the major emphasis in automata theory was placed on problems related to mathematical linguistics. In the second half of the sixties and seventies the focus was moved to structural automata theory, and also this part of algebraic automata theory conceed with problems of automata analysis and synthesis. In seventies automata theory is strongly influenced by computational analysis. The concept of time-varying automata is developed as a convenient mathematical model for many computational and technological processes.
Significant is the influence of automata theory on the development of foundations of the digital technology, design and utilization of computer hardware, expressed in formulation of many new designing methods implanted into engineer's practice and into academic curricula. This book presents these methods according to their significance taking into consideration especially the last decade of research in structural automata theory, and in time-varying automata.
Basic mathematical concepts
Automata and languages
Finite automata
Minimization of automata
Input subautomata
Automata homomorphisms
Realizations of automata. State assignment
Realizations of automata. Structures of nets
Time-varying automata
Transforms and extensions of automata
Periodic sums of automata
Linear automata
The subject of research in automata theory is a design of mathematical models describing methods of information transformation in digital systems. Automata theory is especially conceed with abstract models of systems working by means of discrete signals, known as digital signals. Special emphasis has been put on digital computers, digital systems of control for technological processes, and digital systems of data transmission. On the other hand, automata theory as one of the branches of general system theory, gives tools needed for formulation and solution of general problems, which can be applied for solving known problems, and also for solving problems in the future. Automata theory is in fact a part of computability theory which covers problems of computer systems, software, activity of nervous systems (neural networks), and processes of live organisms development.
Automaton, in particular a finite automaton, is an abstract mathematical concept, a computability model or a model of some process. In the research in automata theory one uses general algebra and graph theory. Some algebraic concepts have their origin in computer systems. These concepts in their formal forms are analyzed and transformed to new forms more convenient for optimization. Finally, during synthesis process, abstract concepts are converted to digital schema, or a flow diagram to be implemented in software. This denotes that automata theory teaches how conceptually and computationally one can consider problems in computer science growing up with respect to magnitude and complexity. Simultaneously, automata theory underlines elements of creativity, because thinking process is of heuristic nature in this branch of computer science. The development of automata theory in sixties and seventies has been stimulated by two complementary tendencies:
i) design of models closely related to existing hardware and software
ii) definition of appropriate mathematical tools (mathematical languages) by means of which one can describe computational processes.
During this period there was a tremendous increase in the use of digital computers in different branches of manufacturing, as well as in research on utilization methods, analysis and synthesis of digital systems to control technological processes taking into account the scale of integration and functional complexity of digital blocks.
Historically, automata theory is a branch of computer science strongly related to mathematical linguistics, discrete mathematics, and engineering of digital systems. This relationship results from the nature of the automaton concept; i.e. automaton can be understood as the acceptor of languages, abstract algebra, oriented graph, digital signal transducer, and mathematical model of digital systems. These facts indicate the interdisciplinary character of automata theory, and also its cognitive value with respect to modeling of technical processes. In the fifties and the first half of sixties the major emphasis in automata theory was placed on problems related to mathematical linguistics. In the second half of the sixties and seventies the focus was moved to structural automata theory, and also this part of algebraic automata theory conceed with problems of automata analysis and synthesis. In seventies automata theory is strongly influenced by computational analysis. The concept of time-varying automata is developed as a convenient mathematical model for many computational and technological processes.
Significant is the influence of automata theory on the development of foundations of the digital technology, design and utilization of computer hardware, expressed in formulation of many new designing methods implanted into engineer's practice and into academic curricula. This book presents these methods according to their significance taking into consideration especially the last decade of research in structural automata theory, and in time-varying automata.
Basic mathematical concepts
Automata and languages
Finite automata
Minimization of automata
Input subautomata
Automata homomorphisms
Realizations of automata. State assignment
Realizations of automata. Structures of nets
Time-varying automata
Transforms and extensions of automata
Periodic sums of automata
Linear automata