Generation of Constants and Synchronization of Finite Automata
Дата
Авторы
Salomaa,Arto
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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. The depth may vary considerably with the target function. Not much is known about the reachability of some target functions, notably constants. Synchronizability of a finite automaton amounts to the representability of some constant as a composition of the functions defined by the input letters. Properties of n such as primality or being a power of 2 turn out to be important, independently of the semantic interpretation. We present some necessary, as well as some sufficient, conditions for synchronizability. We also discuss a famous conjecture about the length of the shortest synchronizing word, and present some results about universal synchronizing words. 1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen.
Ключевые слова
synchronization of finite automata , functions over a finite domain , functional compositions , complexity of compositions