Computing the shortest reset words of synchronizing automata
From MaRDI portal
Publication:2354297
DOI10.1007/s10878-013-9682-0zbMath1331.68136WikidataQ59407171 ScholiaQ59407171MaRDI QIDQ2354297
Marek Szykuła, Jakub Kowalski, Andrzej P. Kisielewicz
Publication date: 10 July 2015
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-013-9682-0
68Q45: Formal languages and automata
Related Items
Synchronizing series-parallel deterministic finite automata with loops and related problems, Synchronizing words and monoid factorization, yielding a new parameterized complexity class?, D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA, Complexity of Preimage Problems for Deterministic Finite Automata, Attainable Values of Reset Thresholds, Černý's conjecture and the road colouring problem, Careful synchronization of partial deterministic finite automata, Preimage problems for deterministic finite automata, Complexity of road coloring with prescribed reset words, Using SAT solvers for synchronization issues in non-deterministic automata, An Extremal Series of Eulerian Synchronizing Automata, Checking Whether an Automaton Is Monotonic Is NP-complete
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved long-period generators based on linear recurrences modulo 2
- Primitive digraphs with large exponents and slowly synchronizing automata
- On the height of digital trees and related problems
- Synchronization
- Synchronizing finite automata with short reset words
- The range order of a product of i transformations from a finite full transformation semigroup
- A note on the average depth of trees
- An efficient algorithm for delay buffer minimization
- Approximating the minimum length of synchronizing words is hard
- Model-based testing of reactive systems. Advanced lectures.
- COMPAS - A Computing Package for Synchronization
- Approximating Minimum Reset Sequences
- Reset Sequences for Monotonic Automata
- Synchronizing Automata and the Černý Conjecture
- Slowly Synchronizing Automata and Digraphs
- The Complexity of Finding Reset Words in Finite Automata
- Genetic Algorithm for Synchronization
- A Fast Algorithm Finding the Shortest Reset Words
- Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata
- Experimental Study of the Shortest Reset Word of Random Automata
- Generating Small Automata and the Černý Conjecture
- Probability Inequalities for Sums of Bounded Random Variables
- Depth-First Search and Linear Graph Algorithms
- An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
