Preimage problems for deterministic finite automata
From MaRDI portal
Publication:2208257
DOI10.1016/j.jcss.2020.08.002zbMath1464.68148arXiv1704.08233OpenAlexW3080435953MaRDI QIDQ2208257
Mikhail V. Berlinkov, Marek Szykuła, Robert Ferens
Publication date: 23 October 2020
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.08233
Related Items (4)
Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Semicomputable points in Euclidean spaces ⋮ Reset complexity and completely reachable automata with simple idempotents
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Černý conjecture for edge-colored digraphs with few junctions
- 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
- On primitivity of sets of matrices
- Synchronization
- Synchronizing finite automata on Eulerian digraphs.
- On completely reachable automata and subset reachability
- 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
- Between primitive and 2-transitive: synchronization and its friends
- On the Probability of Being Synchronizable
- On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata
- Completely Reachable Automata
- The Synchronizing Probability Function of an Automaton
- 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
- Representation theory of finite semigroups, semigroup radicals and formal language theory
- Approximation of Reset Thresholds with Greedy Algorithms
- Complexity of Preimage Problems for Deterministic Finite Automata
- An improvement to a recent upper bound for synchronizing words of finite automata
- SYNCHRONIZING QUASI-EULERIAN AND QUASI-ONE-CLUSTER AUTOMATA
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: Preimage problems for deterministic finite automata
