Dynamics of the Independence Number and Automata Synchronization
(2018) DLT 2018 — Location: Tokyo, Japan (10.September.2018)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- We study the lengths of synchronizing words produced by the classical greedy compression algorithm. We associate a sequence of graphs with every synchronizing automaton and rely on evolution of the independence number to bound the lengths of produced words. By leveraging graph theoretical results we show that in many cases automata with good extension properties have good compression properties as well. More precisely, we show that the compression algorithm will produce a synchronizing word of length O(n2log(n)) on cyclic, regular and strongly-transitive automata with n states, which is not far from the best possible bound of (n−1)2. Furthermore, we provide a relatively simple proof that every n-state automaton has a synchronizing word of length at most n34+O(n2).
- Affiliations
Citations
Gusev, V., Jungers, R., & Průša, D. (2018). Dynamics of the Independence Number and Automata Synchronization. Developments in Language Theory : Lecture Notes in Computer Science, p. 379-391. https://doi.org/10.1007/978-3-319-98654-8_31