Don's conjecture for binary completely reachable automata: an approach and its limitations
| Autor: | Casas, David, Volkov, Mikhail V. |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 14 pages, 7 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|