THE ABSTRACT THEORY OF AUTOMATA (Q3289362)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3170710
Language Label Description Also known as
default for all languages
No label defined
    English
    THE ABSTRACT THEORY OF AUTOMATA
    scientific article; zbMATH DE number 3170710

      Statements

      THE ABSTRACT THEORY OF AUTOMATA (English)
      0 references
      0 references
      1962
      0 references
      automata
      0 references
      This is one of the most elegant and comprehensive treatments of the abstract theory of automata, i.e. the theory of autos (automata) regarded simply as a set of states and a transfer function; questions of building up autos as networks of basic ones are not considered. The basic idea is to treat the subject algebraically throughout and this results in a very neat presentation of known results and some generalisations and new results. The author distinguishes two types of abstract auto. A Mealy auto is an object \(\mathrm{A}=\mathrm{A}(A, X, Y, \delta, \lambda)\) consisting of 3 non empty sets \(A\) (the states), \(X\) (the input signals), \(Y\) (the output signals) and two functions \(\delta=\delta(a, x)\) from \(A \times X\) to \(A\) (the transfer function), \(\lambda = \lambda(a, x)\) from \(A\times X\) to \(Y\) (the output function); it is called an initial auto if in the set \(A\) a certain element \(a_0\) (initial state) is singled out. This differs from Mealy's original definition in that the difference between initial and non initial autos is emphasized and as yet there is no restriction that \(A, X, Y\) be finite. It is interesting how much of the usual theory goes through without this assumption. A Moore auto is a Mealy auto whose output function can be represented in the form \(\lambda(a, x) = \mu(\delta(a, x))\), i.e. where the output is determined entirely by the next state. The first section is concerned with natural definitions of homomorphism and isomorphism of autos and theorems about these. These include the existence of a minimal auto equivalent to any given auto, and being a homomorphic image of it. Although from the point of view of the transformations they can effect Moore autos are as general as Mealy autos, they lead to distinct notions of homomorphism and equivalence. Section 2 deals with the mapping of the input free semigroup \(F(X)\) onto the output free semigroup \(F(Y)\) which the auto effects. By introducing the notion of a free automaton (always having an infinity of states) he proves that a necessary and sufficient condition for a mapping \(\varphi\) to be an auto mapping is that \(\varphi(p)\) and \(p\) have the same length and that \(\varphi(pq)\) is always of the form \(\varphi(p)r\). Any event (subset of \(F(X)\)) can be represented by an output signal of a (generally infinite) Moore auto. Section 3 deals with the representation of events in finite autos. The connection with regular sets is proved neatly by a method which gives a practicable algorithm for constructing a regular expression for the events represented by the states of a given auto. Conversely a synthesis algorithm is given which leads to one for deciding whether two regular expressions represent the same event. Medvedev's characterisation of representable events is also dealt with, as is Burks and Wang's use of transfer matrices. In section 4 the semigroup of an auto is considered; this is generated by the substitutions (of states) induced by the various input signals. Relations between homomorphisms of autos and of the corresponding semigroups are considered; also auto and semigroup partitions and commutative events. Section 5 deals with various methods of composition of autos e.g. direct sum, product, with simple (strongly connected) and semisimple autos, and.with the completeness of systems of autos (i.e. if an arbitrary auto is isomorphic (homomorphic) to a product of elements of this system). The last section deals with experiments on autos as a means of distinguishing states; Moore's results are extended. A noteworthy and valuable contribution to automata theory.
      0 references

      Identifiers