Complexity of Preimage Problems for Deterministic Finite Automata
From MaRDI portal
Publication:5005132
DOI10.4230/LIPIcs.MFCS.2018.32OpenAlexW2798896350MaRDI QIDQ5005132
Mikhail V. Berlinkov, Robert Ferens, Marek Szykuła
Publication date: 4 August 2021
Full work available at URL: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2018.html#BerlinkovFS18
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of a problem concerning reset words for Eulerian binary automata
- The Černý conjecture for one-cluster automata with prime length cycle
- Shortest synchronizing strings for Huffman codes
- Synchronizing automata preserving a chain of partial orders
- Synchronization
- Synchronizing finite automata on Eulerian digraphs.
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Synchronizing generalized monotonic automata
- Polynomial complete problems in automata theory
- Algebraic synchronization criterion and computing reset words
- Computing the shortest reset words of synchronizing automata
- On the Probability of Being Synchronizable
- Completely Reachable Automata
- THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE
- On Two Algorithmic Problems about Synchronizing Automata
- Strong Inapproximability of the Shortest Reset Word
- A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
- Synchronizing Strategies under Partial Observability
- Reset Sequences for Monotonic Automata
- Synchronizing Automata and the Černý Conjecture
- The Complexity of Finding Reset Words in Finite Automata
- Approximation of Reset Thresholds with Greedy Algorithms
- SYNCHRONIZING QUASI-EULERIAN AND QUASI-ONE-CLUSTER AUTOMATA
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: Complexity of Preimage Problems for Deterministic Finite Automata
