Complexity of preimage problems for deterministic finite automata
From MaRDI portal
Recommendations
- Preimage problems for deterministic finite automata
- scientific article; zbMATH DE number 3982526
- scientific article; zbMATH DE number 822042
- Complexity of problems concerning reset words for some partial cases of automata
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
Cites work
- A quadratic upper bound on the size of a synchronizing word in one-cluster automata
- Approximation of reset thresholds with greedy algorithms
- Completely reachable automata
- Complexity of a problem concerning reset words for Eulerian binary automata
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Computing the shortest reset words of synchronizing automata
- Depth-First Search and Linear Graph Algorithms
- scientific article; zbMATH DE number 7228447 (Why is no real title available?)
- scientific article; zbMATH DE number 3222112 (Why is no real title available?)
- On the probability of being synchronizable
- On two algorithmic problems about synchronizing automata (short paper)
- Polynomial complete problems in automata theory
- Reset Sequences for Monotonic Automata
- Shortest synchronizing strings for Huffman codes
- Strong inapproximability of the shortest reset word
- Subset synchronization of transitive automata
- Synchronization
- Synchronizing Automata and the Černý Conjecture
- Synchronizing automata preserving a chain of partial orders
- Synchronizing finite automata on Eulerian digraphs.
- Synchronizing generalized monotonic automata
- Synchronizing quasi-Eulerian and quasi-one-cluster automata
- Synchronizing strategies under partial observability
- The averaging trick and the Černý conjecture
- The complexity of finding reset words in finite automata
- The Černý conjecture for aperiodic automata
- The Černý conjecture for automata respecting intervals of a directed graph
- The Černý conjecture for one-cluster automata with prime length cycle
Cited in
(6)- Exact complexity of problems of incompletely specified automata
- Preimage problems for deterministic finite automata
- Constrained synchronization and commutativity
- Computing the prefix of an automaton
- scientific article; zbMATH DE number 3982526 (Why is no real title available?)
- scientific article; zbMATH DE number 822042 (Why is no real title available?)
This page was built for publication: Complexity of preimage problems for deterministic finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5005132)
