Synchronizing Automata and the Černý Conjecture

DOI10.1007/978-3-540-88282-4_4zbMath1156.68466OpenAlexW1991980356MaRDI QIDQ3540093

Mikhail V. Volkov

Publication date: 20 November 2008

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-88282-4_4

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (only showing first 100 items - show all)

Uniform distribution of sequences generated by iterated polynomials ⋮ Recognizing 3-collapsing words over a binary alphabet ⋮ Extremal binary PFAs in a Černý family ⋮ Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Deciding the boundedness and dead-beat stability of constrained switching systems ⋮ Synchronizing automata preserving a chain of partial orders ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Strongly connected synchronizing automata and the language of minimal reset words ⋮ Using SAT solvers for synchronization issues in non-deterministic automata ⋮ The Černý conjecture and 1-contracting automata ⋮ Unnamed Item ⋮ ON A CONJECTURE BY CARPI AND D'ALESSANDRO ⋮ STATE COMPLEXITY OF CODE OPERATORS ⋮ The Synchronization Problem for Locally Strongly Transitive Automata ⋮ Synchronizing Automata on Quasi-Eulerian Digraph ⋮ P(l)aying for Synchronization ⋮ Synchronizing Automata of Bounded Rank ⋮ Synchronization of Automata with One Undefined or Ambiguous Transition ⋮ Ideal regular languages and strongly connected synchronizing automata ⋮ Reset Thresholds of Automata with Two Cycle Lengths ⋮ Representation of (Left) Ideal Regular Languages by Synchronizing Automata ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Robbins and Ardila meet Berstel ⋮ Unnamed Item ⋮ Careful synchronization of partial deterministic finite automata ⋮ Synchronizing times for \(k\)-sets in automata ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ Synchronizing random automata on a 4-letter alphabet ⋮ 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 ⋮ Synchronizing Automata with Extremal Properties ⋮ On the Number of Synchronizing Colorings of Digraphs ⋮ Describing Homing and Distinguishing Sequences for Nondeterministic Finite State Machines via Synchronizing Automata ⋮ Automorphisms of shift spaces and the Higman--Thompson groups: the one-sided case ⋮ Slow continued fractions, transducers, and the Serret theorem ⋮ Algorithm for determining pure pointedness of self-affine tilings ⋮ Synchronizing sequences for road colored digraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lifespan in a primitive Boolean linear dynamical system ⋮ Ideal separation and general theorems for constrained synchronization and their application to small constraint automata ⋮ Slowly synchronizing automata with zero and noncomplete sets ⋮ On the computational complexity of problems related to distinguishability sets ⋮ Preimage problems for deterministic finite automata ⋮ Circular automata synchronize with high probability ⋮ Surface Dimension, Tiles, and Synchronizing Automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words ⋮ State complexity of the set of synchronizing words for circular automata and automata over binary alphabets ⋮ Constrained synchronization and commutativity ⋮ ON THE LOCAL INVERTIBILITY OF FINITE STATE INFORMATION LOSSLESS AUTOMATA ⋮ The complexity of synchronizing Markov decision processes ⋮ A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices ⋮ Complexity of a problem concerning reset words for Eulerian binary automata ⋮ On incomplete and synchronizing finite sets ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number ⋮ Synchronizing automata with finitely many minimal synchronizing words ⋮ Computational complexity of synchronization under regular commutative constraints ⋮ Unnamed Item ⋮ The Černý conjecture for one-cluster automata with prime length cycle ⋮ Algebraic synchronization criterion and computing reset words ⋮ On the Probability of Being Synchronizable ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time ⋮ Analytic methods for reachability problems ⋮ Reset Complexity of Ideal Languages Over a Binary Alphabet ⋮ Finitely Generated Synchronizing Automata ⋮ The relation between preset distinguishing sequences and synchronizing sequences ⋮ Approximating Minimum Reset Sequences ⋮ Slowly synchronizing automata with fixed alphabet size ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Unnamed Item ⋮ Synchronizing Automata over Nested Words ⋮ An Expansion Property of Boolean Linear Maps ⋮ Extremal synchronizing circular automata ⋮ Conjugate subgroups and overgroups of Vn ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ The uniform distribution of sequences generated by iterated polynomials ⋮ The least channel capacity for chaos synchronization ⋮ Matrix Mortality and the Černý-Pin Conjecture ⋮ A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata ⋮ Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete ⋮ On finite monoids over nonnegative integer matrices and short killing words ⋮ Semicomputable points in Euclidean spaces ⋮ Completely Reachable Automata ⋮ Experiments with Synchronizing Automata ⋮ On Synchronizing Automata and Uniform Distribution ⋮ Černý's conjecture and the road colouring problem ⋮ Strongly transitive automata and the Černý conjecture ⋮ On Nonnegative Integer Matrices and Short Killing Words ⋮ Attainable Values of Reset Thresholds ⋮ Synchronizing words for real-time deterministic pushdown automata (extended abstract) ⋮ Unnamed Item ⋮ Computational complexity of problems for deterministic presentations of sofic shifts ⋮ Sync-maximal permutation groups equal primitive permutation groups ⋮ Primitive Sets of Nonnegative Matrices and Synchronizing Automata ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems ⋮ Computing the shortest reset words of synchronizing automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orienting polygonal parts without sensors
• The road coloring problem
• Synchronizing automata with a letter of deficiency 2
• The range order of a product of i transformations from a finite full transformation semigroup
• An extremal problem for two families of sets
• Synchronizing finite automata on Eulerian digraphs.
• Establishing certain bounds concerning finite automata
• Composition sequences for functions over a finite domain.
• The complexity of oblivious plans for orienting and distinguishing polygonal parts
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• On the Length of the Smallest Uniform Experiment which Distinguishes the Terminal States of a Machine
• Reset Sequences for Monotonic Automata
• Synchronizing Automata Preserving a Chain of Partial Orders
• SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
• Representation theory of finite semigroups, semigroup radicals and formal language theory
• On two Combinatorial Problems Arising from Automata Theory
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
• State-identification experiments in finite automata
• Developments in Language Theory
• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture

This page was built for publication: Synchronizing Automata and the Černý Conjecture