The Černý conjecture for one-cluster automata with prime length cycle

DOI10.1016/J.TCS.2011.06.012MaRDI QIDQ719288zbMATH OpenOpenAlexWikidataFDO

Authors Benjamin Steinberg

Publication date 10 October 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.06.012

zbMATH Keywords

reset wordsynchronizing automataone-cluster automatasynchonizationČerný conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Directed graphs (digraphs), tournaments (05C20)

Recommendations

• The Černý conjecture for aperiodic automata
• The Černý conjecture and 1-contracting automata
• Cerny's conjecture for automata with simple idempotents
• The Černý conjecture for automata respecting intervals of a directed graph
• The Černý conjecture for automata with blocking states
• Les automates circulaires biaisés vérifient la conjecture de Černý
• Strongly transitive automata and the Černý conjecture
• Synchronizing Automata and the Černý Conjecture
• Generating small automata and the Černý conjecture
• A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata

Cites work

• scientific article; zbMATH DE number 3864504 (Why is no real title available?)
• scientific article; zbMATH DE number 3605922 (Why is no real title available?)
• scientific article; zbMATH DE number 846959 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
• A counter example to a conjecture concerning synchronizing words in finite automata
• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
• Composition sequences for functions over a finite domain.
• Estimation of the length of reset words for automata with simple idempotents
• Matrix Mortality and the Černý-Pin Conjecture
• On two Combinatorial Problems Arising from Automata Theory
• Representation theory of finite semigroups, semigroup radicals and formal language theory
• Reset words for commutative and solvable automata
• SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
• Synchronizing Automata and the Černý Conjecture
• Synchronizing automata with a letter of deficiency 2
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic automata
• Synchronizing groups and automata
• The Synchronization Problem for Locally Strongly Transitive Automata
• The Synchronization Problem for Strongly Transitive Automata
• The averaging trick and the Černý conjecture
• The road coloring problem
• The road-colouring problem
• The Černý conjecture for aperiodic automata
• Černý's conjecture and group representation theory

Cited in

(45)

• Černý conjecture for edge-colored digraphs with few junctions
• scientific article; zbMATH DE number 5593050 (Why is no real title available?)
• Semisimple synchronizing automata and the Wedderburn-Artin theory
• The Černý conjecture for automata respecting intervals of a directed graph
• scientific article; zbMATH DE number 3864504 (Why is no real title available?)
• Strong inapproximability of the shortest reset word
• A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number
• Synchronizing automata with coinciding cycles
• Synchronised automata
• Preimage problems for deterministic finite automata
• Sync-maximal permutation groups equal primitive permutation groups
• A counter example to a conjecture concerning synchronizing words in finite automata
• Resetting words for decidable automata
• Finding DFAs with maximal shortest synchronizing word length
• Strongly connected synchronizing automata and the language of minimal reset words
• Between primitive and 2-transitive: synchronization and its friends
• Simplicity of augmentation submodules for transformation monoids
• Slowly synchronizing automata with fixed alphabet size
• The Černý conjecture for automata with blocking states
• Synchronization of Some DFA
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
• A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
• Cerny's conjecture for automata with simple idempotents
• Extremal synchronizing circular automata
• Synchronizing Automata with Extremal Properties
• Černý's conjecture and the road colouring problem
• The Černý conjecture and 1-contracting automata
• Reliable \(L_1\) control of positive switched systems with time-varying delays
• Experiments with Synchronizing Automata
• Cliques and colorings in generalized Paley graphs and an approach to synchronization
• An extremal series of Eulerian synchronizing automata
• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• The Černý conjecture for aperiodic automata
• On the interplay between Černý and Babai's conjectures
• The averaging trick and the Černý conjecture
• The averaging trick and the Černý conjecture
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)
• Complexity of preimage problems for deterministic finite automata
• Primitive digraphs with large exponents and slowly synchronizing automata
• Synchronizing sequences for road colored digraphs
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• Complexity of a problem concerning reset words for Eulerian binary automata
• Synchronizing quasi-Eulerian and quasi-one-cluster automata
• Matrix Mortality and the Černý-Pin Conjecture
• Synchronizing automata on quasi-Eulerian digraph

Describes a project that uses

Uses Software

• TESTAS

This page was built for publication: The Černý conjecture for one-cluster automata with prime length cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q719288)