Subset synchronization and careful synchronization of binary finite automata

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.

Recommendations

• Subset synchronization of transitive automata
• Some results concerning careful synchronization of partial automata and subset synchronization of DFA's
• Subset synchronization in monotonic automata
• Careful synchronization of partial deterministic finite automata
• scientific article; zbMATH DE number 1953272
• Careful synchronization of partial automata with restricted alphabets
• Synchronization of finite automata
• Constrained synchronization and subset synchronization problems for weakly acyclic automata
• Synchronization and stability of finite automata
• Synchronizing Automata and the Černý Conjecture

Cites work

• A lower bound for the length of the shortest carefully synchronizing words
• Exact synchronization for finite-state sources
• Improved upper bounds on synchronizing nondeterministic automata
• On the effects of noise and speed on computations
• Professional knowledge matters in mathematics teaching

Cited in

(23)

• On automata recognizing birecurrent sets
• Some results concerning careful synchronization of partial automata and subset synchronization of DFA's
• Synchronizing times for k-sets in automata
• Preimage problems for deterministic finite automata
• On the height of a finite automaton
• Strong inapproximability of the shortest reset word
• Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
• Automatic Refinement of Split Binary Semaphore
• Subset synchronization in monotonic automata
• scientific article; zbMATH DE number 846959 (Why is no real title available?)
• Careful synchronization of partial automata with restricted alphabets
• Subset synchronization of transitive automata
• On incomplete and synchronizing finite sets
• A new lower bound for reset threshold of binary synchronizing automata with sink
• Lower bounds for synchronizing word lengths in partial automata
• Extremal Binary PFAs with Small Number of States
• The road problem and homomorphisms of directed graphs
• Subset mapping problems in solvable automata
• An improved algorithm for finding the shortest synchronizing words
• Careful synchronization of one-cluster automata
• Synchronizing strongly connected partial DFAs
• Constrained synchronization and subset synchronization problems for weakly acyclic automata
• A lower bound for the length of the shortest carefully synchronizing words

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)