Subset synchronization and careful synchronization of binary finite automata

From MaRDI portal

DOI10.1142/S0129054116500167MaRDI QIDQ2833542zbMATH OpenFDO

Authors Vojtěch Vorel

Publication date 18 November 2016

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.3972


zbMATH Keywords

reset wordsynchronizing automaton, Černý conjecturesynchronizing word

Mathematics Subject Classification ID

Formal languages and automata (68Q45)


Abstract: 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.


Review text

A reset word of a finite automaton is an input sequence that brings the automaton to a unique given state, no matter in which state the computation starts. A finite automaton is synchronizing if it has a reset word. The well-known open Černý conjecture claims that any \(n\)-state deterministic synchronizing finite automaton has a reset word of length at most \(\left( n-1\right) ^{2}\). The author investigates two generalizations of this problem. The first one deals with careful (using only the defined transitions) reset words of partial finite automata and the second one with reset words for synchronizing an automaton being in a state belonging to some fixed subset of its states. In both cases it is shown that the lower bound for the length of the reset word for \(n\)-state automata with binary input alphabet is exponential (\(2^{\Omega\left( n\right) }\)). This improves the previous results based on automata with a growing size of the input alphabet.


Recommendations


Cites work


Cited in
(24)








This page was built for publication: Subset synchronization and careful synchronization of binary finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2833542)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Subset_synchronization_and_careful_synchronization_of_binary_finite_automata&oldid=79446413"
Powered by MediaWiki