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

DOI10.1016/J.TCS.2011.06.012zbMATH Open1243.68204OpenAlexW2962940319WikidataQ122955349 ScholiaQ122955349MaRDI QIDQ719288FDOQ719288

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

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

zbMATH Keywords

reset wordsynchronizing automataone-cluster automatasynchonizationČerný conjecture

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (45)

• Černý conjecture for edge-colored digraphs with few junctions
• Title not available (Why is that?)
• Semisimple synchronizing automata and the Wedderburn-Artin theory
• The Černý conjecture for automata respecting intervals of a directed graph
• Title not available (Why is that?)
• 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
• Finding DFAs with maximal shortest synchronizing word length
• Resetting words for decidable automata
• Strongly connected synchronizing automata and the language of minimal reset words
• The Černý conjecture for automata with blocking states
• Between primitive and 2-transitive: synchronization and its friends
• Simplicity of augmentation submodules for transformation monoids
• Slowly synchronizing automata with fixed alphabet size
• 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
• Reliable \(L_1\) control of positive switched systems with time-varying delays
• The Černý conjecture and 1-contracting automata
• Cliques and colorings in generalized Paley graphs and an approach to synchronization
• Experiments with Synchronizing Automata
• An extremal series of Eulerian synchronizing automata
• The Černý conjecture for aperiodic automata
• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• On the interplay between Černý and Babai's conjectures
• The averaging trick and the Černý conjecture
• The averaging trick and the Černý conjecture
• Title not available (Why is that?)
• Complexity of preimage problems for deterministic finite automata
• Synchronizing sequences for road colored digraphs
• Primitive digraphs with large exponents and slowly synchronizing automata
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• Synchronizing quasi-Eulerian and quasi-one-cluster automata
• Complexity of a problem concerning reset words for Eulerian binary automata
• Matrix Mortality and the Černý-Pin Conjecture
• Synchronizing automata on quasi-Eulerian digraph

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)