Abstract automata

DEFINITION A finite automaton M. is specified by three sets A, E and E and a state-transition function 0 E x A E, where 

Given an automaton M that starts in state CTi, and any finite string s A, f a, s) will represent the final output state that J 4 will enter after having processed s, one symbol at a time, from left to right. J 4 is said to accept the word s if f ai,s) E the word s is rejected if and only if it is not accepted. Finally, we may define the language C JA) accepted by M as the set of all words s A that are accepted by Ad. A language C is called regular if there is a finite automaton Ad that accepts it. 

The grammars for regular languages can be conveniently specified by finite state transition graphs for the finite automata that recognize them. The vertices of the graph represent the the system states Cj E and the arcs represent the possible input states Uj A. The arrows point to the next state that will result from the initial state when the input on the arc is applied. 

EXAMPLE Consider an automaton M with alphabet A (Ti,02,03,0 and transition rule (j given by 

The state transition graph for this example is given in figure 2.5. 

---

The remainder of the book is divided into eleven largely self-contained chapters. Chapter 2 introduces some basic mathematical formalism that will be used throughout the book, including set theory, information theory, graph theory, groups, rings and field theory, and abstract automata. It concludes with a preliminary mathematical discussion of one and two dimensional CA. 

Abstract automata are machines with internal states, an input tape, and sometimes an auxiliary information storage stack. Automata read symbols from the tape, making transitions from one state to another, while performing other operations on the tape and stack. The simplest example of such an idealized machine is the finite automaton ... 

Although CA are most often assumed to live 011 infinitely large lattices, we can equally well consider lattices that are finite in extent (which is done in practice regardless, since all CA simulations are ultimately restricted by a finite computer memory). If a lattice has N sites, there are clearly a finite number,, of possible global configurations. The global dynamical evolution can then be represented by a finite state transition graph Gc, much like the one considered in the description of an abstract automaton in section 2.1.4. 

Finite automata such as these are the simplest kind of computational model, and are not very powerful. For example, no finite automaton can accept the set of all palindromes over some specified alphabet. They certainly do not wield, in abstract terms, the full computational power of a conventional computer. For that we need a suitable generalization of the these primitive computational models. Despite the literally hundreds of computing models that have been proposed at one time or another since the beginning of computer science, it has been found that each has been essentially equivalent to just one of four fundamental models finite automata, pushdown automata, linear bounded automata and Turing machines. 

An abstract family of deterministic languages (AFDL) is defined in [3] as a family of languages closed under the operations of "marked union", "marked " (marked fcleene closure) and inverse "marked gsm" mapping. It was shown that a fsully of languages is an AFDL if and only if there exists a 1DBA (one-way deterministic balloon automaton) which accepts exactly that family. (The concept of balloon automaton is found in [7]). 

ABSTRACT In dependability studies of dynamic systems it is important to assess the probability of occurrence for the events sequences which describe the system evolution or which are critical for the mission of the system or for the humans and environment safety. In this paper we use the probabilistic languages framework in order to realize the quantitative assessment and we start by modeling the system as a finite state automaton. This is ulterior transformed in a probabilistic automaton using the embedded discrete Time Markov Chain. The determination of the languages afferents at each state of the automaton enable to calculate the probabihty of occurrence for every events sequence that can be subtract from these languages. 

Von Neumann s kinematic model. The system is comprised of a control unit governing the actions of a constructing unit, capable of producing any automaton according to a description provided to it on a linear tape-like memory structure. The constructing unit picks up the parts it needs from an unlimited pool of parts and assembles them into the desired automaton. The project was far from being finished and remained an abstract model when von Neumann died (Stevens, 2009). 

Cellular automata are abstract discrete dynamical systems introduced by Von Neumann in an attempt to model self-replication in biological systems [11]. A cellular automaton consists of a set of nodes, usually arranged on a regular lattice, each of which supports state variables that take on a finite number of possible values. The state variables are synchronously updated at discrete... 

Cellular automata can be constructed as simplified models of reaction-diffusion systems. Often the main features of an apparently very complex dynamics can be captured in a simple rule. The Greenbeig-Hastings rules [13] are an example of simple cellular automaton rules that model excitable media. We term such cellular automaton models classical cellular automata since they are constructed in the spirit of the original cellular automaton models of Von Neumann. There is a laige literature [14] on this topic that deals with the mathematical properties of different abstract cellular automaton rules [15], as well as studies that attempt to model rather detailed features of specific reaction-diffusion equations [16,17]. 

We will present the development methodology of the computerized interlocking module (MEI) and its eharacteristies adapted for the railway environment. We will try to advanee some implemented principles, irmovative in their implementation but eonventional in their problems. In response to the expectations set forth in the preeeding sections, the main idea was to develop an industrial safety automaton having a low-eost, reusable development chain, which behaves like an abstract machine (a factual automaton with zero transition time) in order to allow for subsecpient formal validation. 

---