Slowly synchronizing automata with zero and incomplete sets

Abstract

Using combinatorial properties of incomplete sets in a free monoid we construct a series of n-state deterministic automata with zero whose shortest synchronizing word has length n^2/4+n/2-1.

9 pages, 6 figures

Cited by in corpus (2)

• On the Minimal Uncompletable Word Problem
• On Non-Complete Sets and Restivo's Conjecture