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

DOI10.1016/j.tcs.2011.06.012zbMath1243.68204OpenAlexW2962940319WikidataQ122955349 ScholiaQ122955349MaRDI QIDQ719288

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 automataČerný conjectureone-cluster automatasynchonization

Mathematics Subject Classification ID

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

Related Items (30)

Reliable \(L_1\) control of positive switched systems with time-varying delays ⋮ Cerny's conjecture for automata with simple idempotents ⋮ Strongly connected synchronizing automata and the language of minimal reset words ⋮ The Černý conjecture and 1-contracting automata ⋮ Unnamed Item ⋮ Synchronizing Automata on Quasi-Eulerian Digraph ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ Strong Inapproximability of the Shortest Reset Word ⋮ Synchronizing Automata with Extremal Properties ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Synchronizing automata with coinciding cycles ⋮ Synchronizing sequences for road colored digraphs ⋮ Preimage problems for deterministic finite automata ⋮ On the Interplay Between Černý and Babai’s Conjectures ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ SYNCHRONIZING QUASI-EULERIAN AND QUASI-ONE-CLUSTER AUTOMATA ⋮ Complexity of a problem concerning reset words for Eulerian binary automata ⋮ Finding DFAs with Maximal Shortest Synchronizing Word Length ⋮ A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number ⋮ Algebraic synchronization criterion and computing reset words ⋮ Semisimple Synchronizing Automata and the Wedderburn-Artin Theory ⋮ Simplicity of augmentation submodules for transformation monoids ⋮ Slowly synchronizing automata with fixed alphabet size ⋮ Extremal synchronizing circular automata ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ Experiments with Synchronizing Automata ⋮ Černý's conjecture and the road colouring problem ⋮ Cliques and colorings in generalized Paley graphs and an approach to synchronization ⋮ Sync-maximal permutation groups equal primitive permutation groups ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Uses Software

• TESTAS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The road coloring problem
• Synchronizing automata with a letter of deficiency 2
• The road-colouring problem
• Reset words for commutative and solvable automata
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic automata
• Composition sequences for functions over a finite domain.
• Černý's conjecture and group representation theory
• Synchronizing groups and automata
• A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
• The Synchronization Problem for Locally Strongly Transitive Automata
• The Synchronization Problem for Strongly Transitive Automata
• Synchronizing Automata and the Černý Conjecture
• SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
• The Averaging Trick and the Černý Conjecture
• Representation theory of finite semigroups, semigroup radicals and formal language theory
• Matrix Mortality and the Černý-Pin Conjecture
• A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
• On two Combinatorial Problems Arising from Automata Theory
• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
• Estimation of the length of reset words for automata with simple idempotents

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