Automata-based programming is a programming technology.[1] Its defining characteristic is the use of finite state machines to describe program behavior. The transition graphs of state machines are used in all stages of software development (specification, implementation, debugging and documentation). Automata-based programming technology was introduced by Anatoly Shalyto in 1991.[2]Switch-technology[3] was developed to support automata-based programming. Automata-based programming is considered to be rather general purpose program development methodology than just another one finite state machine implementation.
For all that on the basis of data domain analysis the sources of input events, the control system (the system of interacting finite state machines) and the control objects implementing output actions are singled out. These control objects can also form yet another type of input actions that are transmitted through a feedback from control objects back to the finite state machines.
Main features
In recent years great attention has been paid to the development of the technology of programming for embedded systems and real-time systems. These systems have special requirements for the quality of software. One of the best known approaches for this field of tasks is synchronous programming.[4][5]
Simultaneously with the advance of synchronous programming in Europe, an approach to software development for crucial systems called automata-based programming or state-based programming[3] was being created in Russia.
The term event is being used more and more widely in programming; recently it has become one of the most commonly used terms in software development. As opposed to it, the offered approach is based on the term state (State-Driven Architecture). After introduction of the term input action, which could denote an input variable or an event, the term automaton without outputs might be brought in. After adding the term output action, the term “automaton” might be used. It is the finite deterministic automaton.
That is why, the sort of programming, which is based on this term, was called “automata-based programming”. So the process of software creation could be named “automata software design”.[6]
The feature of this approach is that automata used for development are defined with the help of transition graphs. In order to distinguish the nodes of these graphs the term state coding has been introduced. With multivalued state coding a single variable can be used to distinguish states of automaton, the number of states is equal to the number of values this variable can take on. This allowed introducing of the term program observability (that is, the value of the state variable can be checked).
Using the concept of “state” in contrast to the concepts of “events” and “variables”, allows one to understand and to specify the task and its parts (subtasks) more clearly.
Using automata-based programming implies debugging by drawing up the protocols (logging) in terms of automata.[citation needed]
For this approach there is a formal and isomorphic method of transforming from the transition graph to the software source code. So when using high-level programming languages, the simplest way is to use a construct which is similar to the switch construct of the C programming language. That is why the first implementation of automata-based programming was called “Switch-Technology”. Additional information about automata-based programming can be found in the “Switch-technology” article.
Nowadays automata-based programming has been developed in several ways, for different types of task to be solved and for various type of computing devices.
Russian registration certificate was issued for the Automata-based programming core and for the Automata-based programming plug-in for Eclipse IDE.
Logical control
In 1996 Russian Foundation for Basic Research[7] in the context of publishing project #96-01-14066 had supported publishing of a book,[3] in which the offered technology was described in application to the logical control systems.
In such systems there are no events, but input and output actions are binary variables and operating system is working in the scanning mode. Systems of this class are usually to be implemented on programmable logic controllers, which have relatively small amount of memory and programming is to be performed using specialized languages (for example, the language of ladder schemes or functional blocks). Methods of formal source code generation for such languages were developed for the cases in which the specification of the project being developed is represented by a system of transition graphs of interacting automata.[3]
State-based programming
Henceforth automata approach was spread to the event-based (reactive) systems.[8] In such systems all of the limitations mentioned above are taken away. It is obvious from the name of these systems that events are used among the input actions. Output actions could be represented by arbitrary functions. Any real-time operating system could be used as an environment.
The automata implementation of event-based systems was made with the help of the procedural approach to software development,[9][10] hence the name “state-based programming”.
When using this method, output actions are assigned to the arcs, loops or nodes of the transition graphs (in general case mixed Moore-Mealy automata are to be used).[3] This allows representing in a compact form the sequences of actions, which are the reactions to the corresponding input actions.
One of the features of such approach to programming for the reactive systems is that the centralization of program logic is achieved by liquidation of logic in the event handlers and forming of system of interacting automata, which are called from these handlers.[11] Automata in such system can interact by nesting, by ability to call each other and with the help of state numbers interchange.
Another important feature of this approach is that automata in it are used thrice: for specification, for implementation (they remain in the source code) and for drawing up the protocol, which is performed, as said above, in terms of automata. The latter allows to verify the propriety of automata system functioning. Logging is performed automatically on the base of created program; it can be used for debugging of programs with complicated behavior.
Also this approach allows effective documenting of the decisions made during design process, especially those related to formalization of program behavior.[12]
All this allowed to start the Foundation for Open Project Documentation,[13] in the context of which many projects on perfecting of automata-based programming are being developed.
State-based object-oriented programming
The composite approach, based on both object-oriented and automata-based programming paradigms,[14][15] may be rather useful for solving tasks from a very large spectrum. This approach was called “state-based object-oriented programming”.
The main feature of this approach is that, like in Turing machines, controlling (automata) states are explicitly singled out. The number of these states is noticeably fewer than amount of all other objects' states (for example, run-time states).
The term “states space” was introduced in programming. This term means the set of object's controlling states. So this approach provides more understandable behavior in comparison with the case when such space is not singled out explicitly.
The minimal set of documents, which visually and clearly describe structural (static) and behavioral (dynamic) sides of a software project, is described.[16]
From the experience of adaptation of suggested approach[17] one can conclude that application of automata makes programs' behavior clearer as using objects makes programs' structure clearer. Existence of high quality project documentation makes further program refactoring (changing of its structure while retaining its functionality) much easier.[18]
Computational algorithms
Automata approach can be used for computational algorithms implementation. It was shown[19] that arbitrary iterative algorithm can be implemented with the help of construction, that is equivalent to the loop operator do ... while, inside which there is single switch operator that implements automaton.
Automata-based approach is very effective for implementation of some algorithms of discrete mathematics, for example, tree parsing algorithm.[20]
A new state-based approach to creation of algorithms' visualizers was offered. Such visualization software is widely used in the Computer Technologies department of Saint Petersburg State University of Information Technologies, Mechanics and Optics for students teaching in programming and discrete mathematics.[21][22] This approach allows representing of visualizer's logic as a system of interacting finite state machines. This system consists of pairs of automata; each of this pairs contains “forward” and “backward” automata, which provides step-by-step forwards and backwards execution of algorithms respectively.
Collected articles on automata-based programming were published in ITMO University. The bulletin[25] contains 28 articles on different problems of automata-based programming.
In 2009, in St. Petersburg, Russia the first book about automata-based programming was published.[26]
A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.
A regular expression, sometimes referred to as rational expression, is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" or "find and replace" operations on strings, or for input validation. Regular expression techniques are developed in theoretical computer science and formal language theory.
In theoretical computer science and formal language theory, a regular language is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science.
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science with close connections to mathematical logic. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a finite automaton (FA) or finite-state machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states and transitions. As the automaton sees a symbol of input, it makes a transition to another state, according to its transition function, which takes the previous state and current input symbol as its arguments.
A state diagram is used in computer science and related fields to describe the behavior of systems. State diagrams require that the system is composed of a finite number of states. Sometimes, this is indeed the case, while at other times this is a reasonable abstraction. Many forms of state diagrams exist, which differ slightly and have different semantics.
Theoretical computer science is a subfield of computer science and mathematics that focuses on the abstract and mathematical foundations of computation.
In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs. This is in contrast to a Moore machine, whose output values are determined solely by its current state. A Mealy machine is a deterministic finite-state transducer: for each state and input, at most one transition is possible.
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines, Warren McCulloch and Walter Pitts were among the first researchers to introduce a concept similar to finite automata in 1943.
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language. It is important in theory because it establishes that NFAs, despite their additional flexibility, are unable to recognize any language that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.
In automata theory, a hybrid automaton is a mathematical model for precisely describing hybrid systems, for instance systems in which digital computational processes interact with analog physical processes. A hybrid automaton is a finite state machine with a finite set of continuous variables whose values are described by a set of ordinary differential equations. This combined specification of discrete and continuous behaviors enables dynamic systems that comprise both digital and analog components to be modeled and analyzed.
A learning automaton is one type of machine learning algorithm studied since 1970s. Learning automata select their current action based on past experiences from the environment. It will fall into the range of reinforcement learning if the environment is stochastic and a Markov decision process (MDP) is used.
Anatoly Abramovich Shalyto is a Russian scientist, doctor of sciences, and professor. He was awarded by Russian State Government in 2008 for his achievements in education and his development of the technology for Automata-based programming called "Switch-technology." He is also an initiator of the Open Project Documentation Initiative.
Automata-based programming is a programming paradigm in which the program or part of it is thought of as a model of a finite-state machine (FSM) or any other formal automaton. Sometimes a potentially infinite set of possible states is introduced, and such a set can have a complicated structure, not just an enumeration.
Quantum dot cellular automata are a proposed improvement on conventional computer design (CMOS), which have been devised in analogy to conventional models of cellular automata introduced by John von Neumann.
In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's theorem, which provides algorithms for evaluating monadic second-order formulas over graphs of bounded treewidth. It is also of fundamental importance in automata theory, where the Büchi–Elgot–Trakhtenbrot theorem gives a logical characterization of the regular languages.
Real-time Control System (RCS) is a reference model architecture, suitable for many software-intensive, real-time computing control problem domains. It defines the types of functions needed in a real-time intelligent control system, and how these functions relate to each other.
In automata theory, a branch of theoretical computer science, an ω-automaton is a variation of a finite automaton that runs on infinite, rather than finite, strings as input. Since ω-automata do not stop, they have a variety of acceptance conditions rather than simply a set of accepting states.
Input/output automata provide a formal model, applicable in describing most types of an asynchronous concurrent system. On its own, the I/O automaton model contains a very basic structure that enables it to model various types of distributed systems. To describe specific types of asynchronous systems, additional structure must be added to this basic model. The model presents an explicit method for describing and reasoning about system components such as processes and message channels that interact with one another, operating at arbitrary relative speeds. The I/O automata were first introduced by Nancy A. Lynch and Mark R. Tuttle in "Hierarchical correctness proofs for distributed algorithms", 1987.
In computational learning theory, induction of regular languages refers to the task of learning a formal description of a regular language from a given set of example strings. Although E. Mark Gold has shown that not every regular language can be learned this way, approaches have been investigated for a variety of subclasses. They are sketched in this article. For learning of more general grammars, see Grammar induction.
Korneev, G.A.; Shamgunov, N.N.; Shalyto, A.A. (2004). Обход деревьев на основе автоматного подхода[Automata-based tree traversing]. Компьютерные инструменты в образовании (in Russian). 3: 32–37.
Korneev, G.A.; Shalyto, A.A. (2005). Построение визуализаторов алгортмов дискретной математики[Constructing of visualizers of algorithms of discrete mathematics](PDF). Научно-технический вестник СПбГУ ИТМО (in Russian). 23: 118–129.
Nepeyvoda, N.N. (2005). Стили и методы программирования[Styles and methods of programming] (in Russian). Internet University of Information Technologies.
Polikarpova, N. I.; Shalyto, A. A. (2009). Автоматное программирование[Automata-based programming](PDF) (in Russian). Saint Petersburg: Piter.
Shalyto, A.A. (1991). Программная реализация управляющих автоматов[Programmatic implementation of control automata]. Журнал «Судостроительная промышленность. Серия «Автоматика и телемеханика» (in Russian). 13: 41–42.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
