Generation of Constants and Synchronization of Finite Automata
Arto K. Salomaa · Zenodo (CERN European Organization for Nuclear Research) · 2020
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. Key Words: synchronization of finite automata, functions over a finite domain, functional