Synchronizing finite automata on Eulerian digraphs.
From MaRDI portal
Publication:1401241
DOI10.1016/S0304-3975(02)00405-XzbMath1045.68082OpenAlexW2140147014WikidataQ55982182 ScholiaQ55982182MaRDI QIDQ1401241
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00405-x
Related Items
Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach, Shortest synchronizing strings for Huffman codes, Synchronizing automata preserving a chain of partial orders, Strongly connected synchronizing automata and the language of minimal reset words, The Černý conjecture and 1-contracting automata, Unnamed Item, A vector space approach to the road coloring problem, A lower bound for the length of the shortest carefully synchronizing words, ON A CONJECTURE BY CARPI AND D'ALESSANDRO, THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE, The Synchronization Problem for Locally Strongly Transitive Automata, Bounds on Non-surjective Cellular Automata, Synchronizing Automata on Quasi-Eulerian Digraph, Synchronizing Automata of Bounded Rank, Some results concerning careful synchronization of partial automata and subset synchronization of DFA's, Synchronizing times for \(k\)-sets in automata, Synchronizing automata with a letter of deficiency 2, Strong Inapproximability of the Shortest Reset Word, Synchronizing Automata with Extremal Properties, Constant amortized time enumeration of Eulerian trails, Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees, Synchronizing automata with coinciding cycles, On primitivity of sets of matrices, The road problem and homomorphisms of directed graphs, Unnamed Item, The generalized road coloring problem and periodic digraphs, Complexity of problems concerning reset words for cyclic and Eulerian automata, Preimage problems for deterministic finite automata, The Synchronization Problem for Strongly Transitive Automata, A quadratic algorithm for road coloring, On the Interplay Between Černý and Babai’s Conjectures, Synchronizing Automata and the Černý Conjecture, Complexity of Preimage Problems for Deterministic Finite Automata, SYNCHRONIZING QUASI-EULERIAN AND QUASI-ONE-CLUSTER AUTOMATA, A series of slowly synchronizing automata with a zero state over a small alphabet, A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices, A Unified Method to Decentralized State Detection and Fault Diagnosis/prediction of Discrete-event Systems, A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number, Černý's conjecture and group representation theory, Shortest Synchronizing Strings for Huffman Codes, The Černý conjecture for one-cluster automata with prime length cycle, Synchronizing groups and automata, Algebraic synchronization criterion and computing reset words, Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata, On the Synchronizing Probability Function and the Triple Rendezvous Time, Representation theory of finite semigroups, semigroup radicals and formal language theory, Genetic Algorithm for Synchronization, Approximating Minimum Reset Sequences, Simplicity of augmentation submodules for transformation monoids, On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata, Synchronizing finite automata with short reset words, Synchronization problems in automata without non-trivial cycles, Extremal synchronizing circular automata, An Extremal Series of Eulerian Synchronizing Automata, Matrix Mortality and the Černý-Pin Conjecture, Černý's conjecture and the road colouring problem, Strongly transitive automata and the Černý conjecture, LOWER BOUNDS FOR THE LENGTH OF RESET WORDS IN EULERIAN AUTOMATA, Primitive Sets of Nonnegative Matrices and Synchronizing Automata, The Synchronizing Probability Function for Primitive Sets of Matrices, Synchronizing series-parallel deterministic finite automata with loops and related problems
Cites Work
- The road-colouring problem
- Equivalence of topological Markov shifts
- On two Combinatorial Problems Arising from Automata Theory
- On the Road Coloring Problem
- Similarity of automorphisms of the torus
- Cycles of relatively prime length and the road coloring problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
