The Černý conjecture for one-cluster automata with prime length cycle
type: Item
instance of: scholarly article
title: The Černý conjecture for one-cluster automata with prime length cycle
zbMATH Open document ID: 1243.68204
author: Benjamin Steinberg
published in: Theoretical Computer Science
publication date: 2011-10-10T00:00:00Z
review text: A deterministic finite automaton \(M\) is said to be synchronizing if there is a ``reset word'' \(w\) such that any path from the initial state labeled \(w\) leads to the same state. A celebrated conjecture of \textit{J. Černý} [Mat.-Fyz. Čas., Slovensk. Akad. Vied 14, 208--216 (1964; Zbl 0137.01101)] states that if an \(n\)-state automaton is synchronizing, then there is a reset word of length at most \((n-1)^2\). An automaton is said to be one-cluster if there exists an input letter such that the edges corresponding to \(a\) contain exactly one simple cycle. In this paper the author, using techniques of linear algebra, proves Černý's conjecture in the special case of ``one-cluster automata'' with prime length cycle.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 5955903
zbMATH Keywords: Černý conjecture
zbMATH Keywords: synchonization
zbMATH Keywords: synchronizing automata
zbMATH Keywords: reset word
zbMATH Keywords: one-cluster automata
reviewed by: Jeffrey Shallit
describes a project that uses: TESTAS
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.06.012
OpenAlex ID: W2962940319
Wikidata QID: Q122955349
cites work: Representation theory of finite semigroups, semigroup radicals and formal language theory
cites work: Matrix Mortality and the Černý-Pin Conjecture
cites work: SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
cites work: Synchronizing generalized monotonic automata
cites work: Synchronizing automata with a letter of deficiency 2
cites work: Synchronizing groups and automata
cites work: A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
cites work: A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
cites work: The Synchronization Problem for Strongly Transitive Automata
cites work: The Synchronization Problem for Locally Strongly Transitive Automata
cites work: Q5509690
cites work: A counter example to a conjecture concerning synchronizing words in finite automata
cites work: Synchronizing finite automata on Eulerian digraphs.
cites work: The road-colouring problem
cites work: Q4171566
cites work: Q3332252
cites work: On two Combinatorial Problems Arising from Automata Theory
cites work: Reset words for commutative and solvable automata
cites work: Q4864787
cites work: Estimation of the length of reset words for automata with simple idempotents
cites work: Composition sequences for functions over a finite domain.
cites work: The Averaging Trick and the Černý Conjecture
cites work: Černý's conjecture and group representation theory
cites work: An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
cites work: Q5387708
cites work: The road coloring problem
cites work: Synchronizing Automata and the Černý Conjecture
DOI: 10.1016/J.TCS.2011.06.012
Recommended article: Q5387708
Recommended article: The Černý conjecture and 1-contracting automata
Recommended article: Cerny's conjecture for automata with simple idempotents
Recommended article: Q5747408
Recommended article: Q3655361
Recommended article: Les automates circulaires biaisés vérifient la conjecture de Černý
Recommended article: Strongly transitive automata and the Černý conjecture
Recommended article: Synchronizing Automata and the Černý Conjecture
Recommended article: Generating Small Automata and the Černý Conjecture
Recommended article: A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
description: scientific article; zbMATH DE number 5955903