Reset Sequences for Monotonic Automata
From MaRDI portal
Publication:3476281
DOI10.1137/0219033zbMATH Open0698.68058DBLPjournals/siamcomp/Eppstein90OpenAlexW2102194201WikidataQ29028851 ScholiaQ29028851MaRDI QIDQ3476281FDOQ3476281
Authors: David Eppstein 
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0219033
Recommendations
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)
Cited In (94)
- Synchronizing automata with a letter of deficiency 2
- On the Number of Synchronizing Colorings of Digraphs
- Groups synchronizing a transformation of non-uniform kernel
- Orienting polygonal parts without sensors
- Černý conjecture for edge-colored digraphs with few junctions
- Constrained synchronization and subset synchronization problems for weakly acyclic automata
- Synchronizing monotonic automata
- Strongly transitive automata and the Černý conjecture
- Genetic Algorithm for Synchronization
- Shortest synchronizing strings for Huffman codes
- A lower bound for the length of the shortest carefully synchronizing words
- The annulation threshold for partially monotonic automata
- Experimental study of the shortest reset word of random automata
- Strong inapproximability of the shortest reset word
- Synchronization
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- The complexity of oblivious plans for orienting and distinguishing polygonal parts
- Estimation of the length of reset words for automata with simple idempotents
- Complexity of problems concerning reset words for cyclic and Eulerian automata
- Preimage problems for deterministic finite automata
- Sync-maximal permutation groups equal primitive permutation groups
- Primitive sets of nonnegative matrices and synchronizing automata
- The relation between preset distinguishing sequences and synchronizing sequences
- Title not available (Why is that?)
- A Unified Method to Decentralized State Detection and Fault Diagnosis/prediction of Discrete-event Systems
- Reset words for commutative and solvable automata
- On a conjecture by Carpi and D'Alessandro
- Analytic methods for reachability problems
- Synchronizing finite automata with short reset words
- On randomized generation of slowly synchronizing automata
- Constrained synchronization for monotonic and solvable automata and automata with simple idempotents
- Synchronizing Automata Preserving a Chain of Partial Orders
- Slowly synchronizing automata with fixed alphabet size
- Notable trends concerning the synchronization of graphs and automata
- Synchronizing automata preserving a chain of partial orders
- Hardness and inapproximability of minimizing adaptive distinguishing sequences
- Cerny's conjecture for automata with simple idempotents
- Extremal synchronizing circular automata
- On primitivity of sets of matrices
- Synchronizing generalized monotonic automata
- Distributed graph problems through an automata-theoretic Lens
- Approximating minimum reset sequences
- Černý's conjecture and the road colouring problem
- Synchronization of automata with one undefined or ambiguous transition
- Lower bounds for the length of reset words in Eulerian automata
- Composition sequences for functions over a finite domain.
- A multi-parameter analysis of hard problems on deterministic finite automata
- Complexities of some problems related to synchronizing, non-synchronizing and monotonic automata
- The Černý conjecture and 1-contracting automata
- A note on polynomial approximation of synchronizing optimal coloring
- Computing the shortest reset words of synchronizing automata
- The NP-completeness of the road coloring problem
- Experiments with Synchronizing Automata
- An extremal series of Eulerian synchronizing automata
- WORDS GUARANTEEING MINIMUM IMAGE
- Synchronizing Automata and the Černý Conjecture
- Distributed graph problems through an automata-theoretic lens
- Title not available (Why is that?)
- Complexity of preimage problems for deterministic finite automata
- Synchronizing words for real-time deterministic pushdown automata (extended abstract)
- A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
- COMPAS -- a computing package for synchronization
- Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
- Synchronizing series-parallel deterministic finite automata with loops and related problems
- A quadratic algorithm for road coloring
- Complexity of a problem concerning reset words for Eulerian binary automata
- Algorithms for media
- A series of slowly synchronizing automata with a zero state over a small alphabet
- Synchronizing automata over nested words
- Orienting polyhedral parts by pushing
- Synchronizing almost-group automata
- On the synchronizing probability function and the triple rendezvous time. New approaches to Černý's conjecture
- Synchronizing automata with coinciding cycles
- Title not available (Why is that?)
- Computational complexity of synchronization under sparse regular constraints
- The road problem and homomorphisms of directed graphs
- Binary and circular automata having maximal state complexity for the set of synchronizing words
- Synchronizing deterministic push-down automata can be really hard
- Non-dominating sequences of vectors using only resets and increments
- Checking whether an automaton is monotonic is NP-complete
- Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
- Some results concerning careful synchronization of partial automata and subset synchronization of DFA's
- The Synchronizing Probability Function for Primitive Sets of Matrices
- Synchronizing times for \(k\)-sets in automata
- Finding short synchronizing words for prefix codes
- Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
- On the synchronizing probability function and the triple rendezvous time for synchronizing automata
- Complexity of problems concerning reset words for cyclic and Eulerian automata
- Shortest Synchronizing Strings for Huffman Codes
- Synchronizing sequences for road colored digraphs
- Computational complexity of problems for deterministic presentations of sofic shifts
- Completely distinguishable automata and the set of synchronizing words
- A linear bound on the \(k\)-rendezvous time for primitive sets of NZ matrices
- Surface dimension, tiles, and synchronizing automata
This page was built for publication: Reset Sequences for Monotonic Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3476281)
