Generation of Constants and Synchronization of Finite Automata

Arto Salomaa (Turku Centre for Computer Science, Finland)

Abstract:

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.

Keywords: complexity of compositions, functional compositions, functions over a finite domain, synchronization of finite automata

Categories: F.1.1