Dynamics of the Independence Number and Automata Synchronization

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F18%3A00327649" target="_blank" >RIV/68407700:21230/18:00327649 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/chapter/10.1007%2F978-3-319-98654-8_31" target="_blank" >https://link.springer.com/chapter/10.1007%2F978-3-319-98654-8_31</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-98654-8_31" target="_blank" >10.1007/978-3-319-98654-8_31</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Dynamics of the Independence Number and Automata Synchronization

Popis výsledku v původním jazyce

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(n^2log(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 (1/4)n^3+O(n^2) .

Název v anglickém jazyce

Dynamics of the Independence Number and Automata Synchronization

Popis výsledku anglicky

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(n^2log(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 (1/4)n^3+O(n^2) .

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA16-05872S" target="_blank" >GA16-05872S: Pravděpodobnostní grafové modely a hluboké učení</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

International Conference on Developments in Language Theory

ISBN

978-3-319-98653-1

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

379-391

Název nakladatele

Springer International Publishing

Místo vydání

Cham

Místo konání akce

Tokyo

Datum konání akce

10. 9. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—