Subset Synchronization and Careful Synchronization of Binary Finite Automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10392113" target="_blank" >RIV/00216208:11320/16:10392113 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1142/S0129054116500167" target="_blank" >https://doi.org/10.1142/S0129054116500167</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1142/S0129054116500167" target="_blank" >10.1142/S0129054116500167</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Subset Synchronization and Careful Synchronization of Binary Finite Automata

Popis výsledku v původním jazyce

We present a strongly exponential lower bound that applies both to the subset synchronization threshold for binary deterministic automata and to the careful synchronization threshold for binary partial automata. In the later form, the result finishes the research initiated by Martyugin (2013). Moreover, we show that both the thresholds remain strongly exponential even if restricted to strongly connected binary automata. In addition, we apply our methods to computational complexity. Existence of a subset reset word is known to be PSPACE-complete; we show that this holds even under the restriction to strongly connected binary automata. The results apply also to the corresponding thresholds in two more general settings: D1- and D3-directable nondeterministic automata and composition sequences over finite domains.

Název v anglickém jazyce

Subset Synchronization and Careful Synchronization of Binary Finite Automata

Popis výsledku anglicky

We present a strongly exponential lower bound that applies both to the subset synchronization threshold for binary deterministic automata and to the careful synchronization threshold for binary partial automata. In the later form, the result finishes the research initiated by Martyugin (2013). Moreover, we show that both the thresholds remain strongly exponential even if restricted to strongly connected binary automata. In addition, we apply our methods to computational complexity. Existence of a subset reset word is known to be PSPACE-complete; we show that this holds even under the restriction to strongly connected binary automata. The results apply also to the corresponding thresholds in two more general settings: D1- and D3-directable nondeterministic automata and composition sequences over finite domains.

Druh

J_imp - Článek v periodiku v databázi Web of Science

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/GA14-10799S" target="_blank" >GA14-10799S: Hyperkrychlové, grafové a hypergrafové struktury</a><br>

Návaznosti

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

Rok uplatnění

2016

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 periodika

International Journal of Foundations of Computer Science

ISSN

0129-0541

e-ISSN

—

Svazek periodika

27

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

SG - Singapurská republika

Počet stran výsledku

21

Strana od-do

557-577

Kód UT WoS článku

000385636700003

EID výsledku v databázi Scopus

2-s2.0-84989898291