2002 | OriginalPaper | Buchkapitel
Synchronization of Finite Automata: Contributions to an Old Problem
verfasst von : Arto Salomaa
Erschienen in: The Essence of Computation
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In spite of its simple formulation, the problem about the synchronization of a finite deterministic automaton is not yet properly understood. The present paper investigates this and related problems within the general framework of a composition theory for functions over a finite domain N with n elements. The notion of depth introduced in this connection is a good indication of the complexity of a given function, namely, the complexity with respect to the length of composition sequences in terms of functions belonging to a basic set. Our results show that the depth may vary considerably with the target function. We also establish criteria about the reachability of some target functions, notably constants. Properties of n such as primality or being a power of 2 turn out to be important, independently of the semantic interpretation. Most of the questions about depth, as well as about the comparison of different notions of depth, remain open. Our results show that the study of functions of several variables may shed light also to the case where all functions considered are unary.