On two algorithmic problems about synchronizing automata (short paper)

DOI10.1007/978-3-319-09698-8_6MaRDI QIDQ2921974zbMATH OpenOpenAlexFDO

Authors Mikhail V. Berlinkov

Publication date 14 October 2014

Published in Developments in Language Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Abstract: Under the assumption $mathcalPeqmathcalNP$, we prove that two natural problems from the theory of synchronizing automata cannot be solved in polynomial time. The first problem is to decide whether a given reachable partial automaton is synchronizing. The second one is, given an $n$-state binary complete synchronizing automaton, to compute its reset threshold within performance ratio less than $dln(n)$ for a specific constant $d>0$.

Recommendations

• Strong inapproximability of the shortest reset word
• 2-Synchronizing Words
• Complexity of checking whether two automata are synchronized by the same language

Cited in

(21)

• Černý's conjecture and the road colouring problem
• Computational complexity of problems for deterministic presentations of sofic shifts
• Some results concerning careful synchronization of partial automata and subset synchronization of DFA's
• Careful synchronization of partial deterministic finite automata
• Preimage problems for deterministic finite automata
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• A QUASI-OPTIMAL TIME FOR SYNCHRONIZING TWO INTERACTING FINITE AUTOMATA
• Approximation of reset thresholds with greedy algorithms
• Finding short synchronizing words for prefix codes
• Complexity of preimage problems for deterministic finite automata
• Complexity of a problem concerning reset words for Eulerian binary automata
• Complexities of some problems related to synchronizing, non-synchronizing and monotonic automata
• Polynomial time decidability of weighted synchronization under partial observability
• Synchronizing automata with coinciding cycles
• The road problem and homomorphisms of directed graphs
• Careful synchronization of one-cluster automata
• Synchronizing strongly connected partial DFAs
• Monoids of upper triangular matrices over the Boolean semiring
• Efficiently computing the minimum rank of a matrix in a monoid of zero-one matrices
• The complexity of reachability problems in strongly connected finite automata
• Synchronization of strongly connected partial DFAs and prefix codes

This page was built for publication: On two algorithmic problems about synchronizing automata (short paper)

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