Reset Sequences for Monotonic Automata

DOI10.1137/0219033zbMath0698.68058DBLPjournals/siamcomp/Eppstein90OpenAlexW2102194201WikidataQ29028851 ScholiaQ29028851MaRDI QIDQ3476281

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

zbMATH Keywords

finite automatabreadth-first searchautomated designreset sequencesparts orienter

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Formal languages and automata (68Q45)

Related Items (97)

Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Cerny's conjecture for automata with simple idempotents ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Shortest synchronizing strings for Huffman codes ⋮ Synchronizing automata preserving a chain of partial orders ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ The Černý conjecture and 1-contracting automata ⋮ Unnamed Item ⋮ The annulation threshold for partially monotonic automata ⋮ A lower bound for the length of the shortest carefully synchronizing words ⋮ ON A CONJECTURE BY CARPI AND D'ALESSANDRO ⋮ The complexity of oblivious plans for orienting and distinguishing polygonal parts ⋮ P(l)aying for Synchronization ⋮ Synchronization of Automata with One Undefined or Ambiguous Transition ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Constrained synchronization for monotonic and solvable automata and automata with simple idempotents ⋮ Synchronizing times for \(k\)-sets in automata ⋮ Synchronizing automata with a letter of deficiency 2 ⋮ Approximating the minimum length of synchronizing words is hard ⋮ Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata ⋮ Strong Inapproximability of the Shortest Reset Word ⋮ Groups synchronizing a transformation of non-uniform kernel ⋮ On the Number of Synchronizing Colorings of Digraphs ⋮ Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ Reset words for commutative and solvable automata ⋮ Completely distinguishable automata and the set of synchronizing words ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Synchronizing automata with coinciding cycles ⋮ Synchronizing Automata Preserving a Chain of Partial Orders ⋮ Complexity of road coloring with prescribed reset words ⋮ On primitivity of sets of matrices ⋮ Synchronizing sequences for road colored digraphs ⋮ The road problem and homomorphisms of directed graphs ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Binary and circular automata having maximal state complexity for the set of synchronizing words ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ The NP-completeness of the road coloring problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity of problems concerning reset words for cyclic and Eulerian automata ⋮ Preimage problems for deterministic finite automata ⋮ A quadratic algorithm for road coloring ⋮ Synchronizing Automata and the Černý Conjecture ⋮ Hardness and inapproximability of minimizing adaptive distinguishing sequences ⋮ Surface Dimension, Tiles, and Synchronizing Automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ Algorithms for media ⋮ Synchronization ⋮ A series of slowly synchronizing automata with a zero state over a small alphabet ⋮ Černý conjecture for edge-colored digraphs with few junctions ⋮ 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 ⋮ Complexity of a problem concerning reset words for Eulerian binary automata ⋮ Orienting polygonal parts without sensors ⋮ WORDS GUARANTEEING MINIMUM IMAGE ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Synchronizing generalized monotonic automata ⋮ Synchronizing monotonic automata ⋮ Shortest Synchronizing Strings for Huffman Codes ⋮ Estimation of the length of reset words for automata with simple idempotents ⋮ Unnamed Item ⋮ Algebraic synchronization criterion and computing reset words ⋮ Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata ⋮ Orienting polyhedral parts by pushing ⋮ Experimental Study of the Shortest Reset Word of Random Automata ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time ⋮ Analytic methods for reachability problems ⋮ Genetic Algorithm for Synchronization ⋮ The relation between preset distinguishing sequences and synchronizing sequences ⋮ COMPAS - A Computing Package for Synchronization ⋮ Approximating Minimum Reset Sequences ⋮ Slowly synchronizing automata with fixed alphabet size ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Synchronizing finite automata with short reset words ⋮ Synchronizing Automata over Nested Words ⋮ Synchronization problems in automata without non-trivial cycles ⋮ Extremal synchronizing circular automata ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete ⋮ Experiments with Synchronizing Automata ⋮ Č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 ⋮ Synchronizing words for real-time deterministic pushdown automata (extended abstract) ⋮ Unnamed Item ⋮ Computational complexity of problems for deterministic presentations of sofic shifts ⋮ Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata ⋮ Sync-maximal permutation groups equal primitive permutation groups ⋮ Primitive Sets of Nonnegative Matrices and Synchronizing Automata ⋮ The Synchronizing Probability Function for Primitive Sets of Matrices ⋮ Synchronizing Almost-Group Automata ⋮ Composition sequences for functions over a finite domain. ⋮ A complete solution to the complexity of synchronizing road coloring for non-binary alphabets ⋮ Notable trends concerning the synchronization of graphs and automata ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems ⋮ Computing the shortest reset words of synchronizing automata ⋮ Distributed graph problems through an automata-theoretic Lens

This page was built for publication: Reset Sequences for Monotonic Automata