We give an elementary and direct proof of the following theorem: A real number is normal to a given integer base if, and only if, its expansion in that base is incompressible by lossless finite-state compressors (these are ...

Abstract: We study some problems related to the synchronization of finite state automata and the Cˇerny’s conjecture. We focus on the synchronization of small sets of states, and more specifically on the synchronization ...

We prove that finite-state transducers with injective behavior, deterministic or not, real-time or not, with no extra memory or a single counter, cannot compress any normal word. We exhaust all combinations of determinism, ...

We consider the previously defined notion of finite-state independence and we focus specifically on normal words. We characterize finite-state independence of normal words in three different ways, using three different ...

Automata Networks are discrete dynamical systems initially introduced by von Neumann [84], Mc-Culloch [50] and Ulam [81] and they have been used to model diverse complex systems such as the study of the evolution and ...

We simplify the known formula for the asymptotic estimate of the number of deterministic and accessible automata with n states over a k-letter alphabet. The proof relies on the theory of Lagrange inversion applied in the ...

In this work we introduce a notion of independence based on finite-state automata: two infinite words are independent if no one helps to compress the other using one-to-one finite-state transducers with auxiliary input. ...