THE ABSTRACT THEORY OF AUTOMATA
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.
- A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
- Representations of (M,R)-systems by categories of automata
- Formalizing the logic design of register components in discrete systems
- Main directions in the development of informatics
- Synthesis of a procedural representation of an automaton specified in the logical language \({\mathfrak L}^*\). II
- An optimal parallel algorithm to convert a regular expression into its Glushkov automaton
- Regular expressions into finite automata
- The validation of SGML content models
- Follow automata.
- Reducing NFAs by invariant equivalences.
- On complete systems of automata
- An efficient null-free procedure for deciding regular language membership
- Characterization of Glushkov automata
- Interleaving isotactics -- an equivalence notion on behaviour abstractions
- Control design for nondeterministic input/output automata
- The inclusion problem for regular expressions
- Construction of fuzzy automata from fuzzy regular expressions
- Derivatives of rational expressions with multiplicity
- Interacting automata
- Representations and test planning methods for complex technical systems
- Boolean function minimization in the class of disjunctive normal forms
- Regular expression searching on compressed text
- Canonical derivatives, partial derivatives and finite automaton constructions.
- Automaton synthesis from a nonformal specification
- Vacuity in practice: temporal antecedent failure
- Finite automata
- Descriptional complexity of regular languages
- From regular expression matching to parsing
- On the uniform distribution of regular expressions
- Manipulation of regular expressions using derivatives: an overview
- How to settle the ReDoS problem: back to the classical automata theory
- Location based automata for expressions with shuffle
- Functional dependencies on extended relations defined by regular languages
- A mesh of automata
- Large scale properties for bounded automata groups.
- On the hierarchy of generalizations of one-unambiguous regular languages
- One-unambiguity of regular expressions with numeric occurrence indicators
- Efficient testing and matching of deterministic regular expressions
- Adding pebbles to weighted automata: easy specification \& efficient evaluation
- Path constraints in semistructured data
- Nonlinear automata over a finite ring
- The word problem for visibly pushdown languages described by grammars
- Reconfigurable-computing technology
- Determination of systems of graphs and the synthesis of finite automata
- Operads, quasiorders, and regular languages
- Acts over semigroups
- Location automata for synchronised shuffle expressions
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- Position automaton construction for regular expressions with intersection
- The degree of irreversibility in deterministic finite automata
- Derivatives of regular expressions and an application
- The complexity of regular(-like) expressions
- Hardware Implementations of Finite Automata and Regular Expressions
- Deciding synchronous Kleene algebra with derivatives
- On the hierarchy of block deterministic languages
- Algorithms for Kleene algebra with converse
- EVALUATION OF THREE IMPLICIT STRUCTURES TO IMPLEMENT NONDETERMINISTIC AUTOMATA FROM REGULAR EXPRESSIONS
- Corrigendum to our paper: How Expressions Can Code for Automata
- Disambiguation in regular expression matching via position automata with augmented transitions
- Construction of tree automata from regular expressions
- Functions without short implicants. II: Construction
- Algebraic interpretation of a microprogram finite-state machine with datapath of transitions
- Derived-term automata for extended weighted rational expressions
- Prefix and Right-Partial Derivative Automata
- Multilevel synthesis of structured programs
- Analysis of behaviour of automata
- Reconstruction of automata by fragments of behaviour
- ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED
- Local design of standardized automata. II
- Efficient weighted expressions conversion
- Construction of Tree Automata from Regular Expressions
- On the Average Size of Glushkov’s Automata
- Hedge Pattern Partial Derivative
- Implementation of State Elimination Using Heuristics
- Regular algebra of functionals of labeled trees
- Functions realizable by one-dimensional iterative systems
- The control problem for a cascade coupling of automata
- Mathematical model of microprogram formation based on optimized structure of the control automaton
- An algorithm to construct the basis of the intersection of finitely generated free groups
- Efficiency of certain algorithms of combinatorial group theory
- Synthesis of multifunction and universal logic elements over residue class rings. I
- Switching functions for a residue-class complementary-code scheme
- Check of linear combination circuits
- Mapping of reduced disjunctive normal forms onto graphs
- Recognition of properties of autonomous structural automata
- Comparative analysis of automata with a common input alphabet
- Translation of sequential program schemes into data-flow schemes
- Monitoring the behavior of semigroup systems
- Functional completeness in the class of speed-independent circuits. I
- Simplified analysis of finite automata
- Realization of monoids on sets
- Algorithms for minimization of finite acyclic automata and pattern matching in terms
- Iterative methods of program analysis: Equalities and inequalities
- The Vienna abstract machine
- Tree pattern matching from regular tree expressions.
- The degree of irreversibility in deterministic finite automata
- Abstract interpretation from Büchi automata
- Optimization of circuits of compositional microprogram control units implemented on FPGA
- Finite-state automata in information technologies
- Glushkov's evidence algorithm
This page was built for publication: THE ABSTRACT THEORY OF AUTOMATA
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3289362)