2023/10/31 by David Casas, Mikhail V. Volkov, Casas, David +1 · 1 citation
Computer Science · #68Q45 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2311.00077
openalex publication_date 2023/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A deterministic finite automaton in which every non-empty set of states occurs as the image of the whole state set under the action of a suitable input word is called completely reachable. It was conjectured that in each completely reachable automaton with n states, every set of k>0 states is the image of a word of length at most n(n-k). We confirm the conjecture for completely reachable automata with two input letters satisfying certain restrictions on the action of the letters.