On Completely Reachable Automata and Subset Reachability

Autor:	Gonze, François, Jungers, Raphaël M.
Rok vydání:	2018
Předmět:	Computer Science - Formal Languages and Automata Theory
Druh dokumentu:	Working Paper
Popis:	This article focuses on subset reachability in synchronizing automata. First, we provide families of synchronizing automata with subsets which cannot be reached with short words. These families do not fulfil Don's Conjecture about subset reachability. Moreover, they show that some subsets need exponentially long words to be reached, and that the restriction of the conjecture to included subsets also does not hold. Second, we analyze completely reachable automata and provide a counterexample to the conjecture of Bondar and Volkov about the so-called $\Gamma_1$-graph. We finally prove an alternative version of this conjecture. Comment: A 12 pages version has been submitted to DLT 2018
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1805.02540 Zobrazit plný text záznamu View this record from Arxiv