Generation of constants and synchronization of finite automata
The problem about the synchronization of a finite deterministic automaton is not yet properly understood. The present a er 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 power of 2 turn out to be important, independently of the semantic interpretation. We resent 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 resent some results about universal synchronizing words.
synchronization of finite automata functions over a finite domain functional compositions complexity of compositions