Synchronizing generalized monotonic automata
From MaRDI portal
Publication:1763695
DOI10.1016/j.tcs.2004.09.006zbMath1078.68071OpenAlexW2061027066MaRDI QIDQ1763695
D. S. Ananichev, Mikhail V. Volkov
Publication date: 22 February 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10995/72264
Monotonic automataSynchronizing automataCongruence on an automatonGeneralized monotonic automataOrder-preserving transformationRank of a word with respect to an automatonRank of an automaton
Related Items (31)
Shortest synchronizing strings for Huffman codes ⋮ On the complexity of existence of homing sequences for nondeterministic finite state machines ⋮ Synchronizing automata preserving a chain of partial orders ⋮ Strongly connected synchronizing automata and the language of minimal reset words ⋮ Unnamed Item ⋮ The annulation threshold for partially monotonic automata ⋮ THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE ⋮ The Synchronization Problem for Locally Strongly Transitive Automata ⋮ Synchronizing automata with a letter of deficiency 2 ⋮ Strong Inapproximability of the Shortest Reset Word ⋮ Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Synchronizing Automata Preserving a Chain of Partial Orders ⋮ Primitive groups, graph endomorphisms and synchronization ⋮ Preimage problems for deterministic finite automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ A series of slowly synchronizing automata with a zero state over a small alphabet ⋮ Černý conjecture for edge-colored digraphs with few junctions ⋮ 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 ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time ⋮ The relation between preset distinguishing sequences and synchronizing sequences ⋮ Approximating Minimum Reset Sequences ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Extremal synchronizing circular automata ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ Matrix Mortality and the Černý-Pin Conjecture ⋮ Strongly transitive automata and the Černý conjecture ⋮ Sync-maximal permutation groups equal primitive permutation groups
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Synchronizing monotonic automata
- An extremal problem for two families of sets
- Monoids respecting \(n\)-chains of intervals
- Composition sequences for functions over a finite domain.
- The proof and the generalization of Higgins' theorem of divisors of semigroups of order-preserving mappings
- WORDS GUARANTEEING MINIMUM IMAGE
- Reset Sequences for Monotonic Automata
- On two Combinatorial Problems Arising from Automata Theory
- On finite monoids having only trivial subgroups
This page was built for publication: Synchronizing generalized monotonic automata
