Skip to main content
main-content

Über dieses Buch

Both theoretical and practical considerations motivate the repre­ sentation of objects as certain compositions of simpler ones. In the theory of automata this observation has led to the concepts of pro­ ducts and complete systems of automata. In the general form of the products of automata all the component automata are fed back to one another. With this very broad notion of products, the realization of automata with large numbers of states by means of compositions of basic components is a highly involved process; this increases the possibility of errors. In order to decrease the complexity of feedbacks, a hierarchy of products called lXi-pro­ ducts was introduced some 10 years ago, where i runs over the set of all non-negative integers. In an IXcproduct the index set of the component automata is linearly ordered. The input of each automaton in the product may depend on the states of all automata preceding it, i. e. , all component automata steer all those automata which follow them in the product. Furthermore, at most the next i-I automata (including itself) may be fed back to the input of a given component automaton. Thus for iXcproducts the lengths of feedbacks are at most i. The aim of this monograph is to give a systematic account of iXi-Products. It consists of five chapters, a reference section, and an index. The first chapter contains the necessary concepts and results from universal algebra, automata, and sequential machines.

Inhaltsverzeichnis

Frontmatter

1. Basic Concepts and Preliminaries

Abstract
In this chapter we survey some basic concepts and results from the theories of automata and universal algebras. It is presumed that the reader has a certain routine in the structural theory of automata and universal algebras. Thus, the results of this chapter are stated without proofs. The only exceptions are certain special group theory results and two statements concerning products of automata, the constructive proofs of which will be needed in our later discussions.
Ferenc Gécseg

2. Homomorphic Representations

Abstract
One of the most important tools of representations is homomorphism; while it is not too general, it is powerful enough. In this chapter, after studying certain special questions concerning homomorphic representations by α0- and α1-products, we show that from i = 2 the α i -product is homomorphically equivalent to the general product, while for i = 0, 1, 2 the hierarchy is proper. Afterwards, we determine those automata which are simple in the sense that, whenever they can be represented homomorphically by a product, then a single-factor power of one of its components represents them homomorphically. The chapter ends with a proof of the existence of an algorithm to decide if a given automaton can be represented homomorphically by a product of automata from a fixed finite class.
Ferenc Gécseg

3. Isomorphic Representations

Abstract
We now use a representation stronger than that studied in the previous chapter: we shall deal with isomorphic representations. It will be seen that there is no finite isomorphically complete system with respect to any of the α i -products. Moreover, as regards isomorphic representation the products form a proper hierarchy, and from i = 1 they are equivalent to each other with respect to isomorphic completeness.
Ferenc Gécseg

4. Generalized Products and Simulations

Abstract
In this chapter we allow feedback functions to take their values from the set of input words of the factors. Moreover, the homomorphic and isomorphic representations will be extended in such a way that input words are permitted as counter images of input signals.
Ferenc Gécseg

5. Representation of Automaton Mappings in Finite Length. Infinite Products

Abstract
There is no finite system of automata which is complete with respect to the α0-product. We show the existence of such finite systems if we restrict ourselves to representations of automaton mappings in finite but unbounded lengths. It will also be seen that in this representation the α0-product is as powerful as the general product. This will follow from the result that, for an arbitrary class K of automata, the minimal equational class containing K and closed under the infinite α0-product coincides with the minimal equational class containing K and closed under the infinite general product.
Ferenc Gécseg

Backmatter

Weitere Informationen