Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The Černý conjecture ...
Article

The Černý conjecture for aperiodic automata

Avraham N. Trahtman
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2007
Last modified on
March 31, 2025
Volume 9
vol. 9:2
DOI
10.46298/dmtcs.395
License
https://about.hal.science/hal-authorisation-v1
Indicators
904
Views
1650
Downloads

The Černý conjecture for aperiodic automata

Avraham N. Trahtman
Abstract
A word w is called a synchronizing (recurrent, reset, directable) word of a deterministic finite automaton (DFA) if w brings all states of the automaton to some specific state; a DFA that has a synchronizing word is said to be synchronizable. Cerny conjectured in 1964 that every n-state synchronizable DFA possesses a synchronizing word of length at most (n-1)2. We consider automata with aperiodic transition monoid (such automata are called aperiodic). We show that every synchronizable n-state aperiodic DFA has a synchronizing word of length at most n(n-1)/2. Thus, for aperiodic automata as well as for automata accepting only star-free languages, the Cerny conjecture holds true.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • The Cerný conjecture for automata respecting intervals of a directed graph

    Discrete Mathematics & Theoretical Computer Science

    Authors : Mariusz Grech ORCID, Andrzej Kisielewicz ORCID

    Journal reference : Volume Vol. 15 no. 3, 2013, pp.

    DOI : 10.46298/dmtcs.619
  • Синхронизация конечных автоматов

    Успехи математических наук

    Authors : Mikhail Vladimirovich Volkov ORCID

    Journal reference : Volume 77, 2022, pp. 53-130

    DOI : 10.4213/rm10005
  • Synchronization Under Dynamic Constraints

    DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Authors : Wolf

    Journal reference : Volume , 2019, pp.

    DOI : 10.4230/lipics.fsttcs.2020.58
  • The Černý conjecture for one-cluster automata with prime length cycle

    Theoretical Computer Science

    Authors : Benjamin Steinberg ORCID

    Journal reference : Volume 412, 2011, pp. 5487-5491

    DOI : 10.1016/j.tcs.2011.06.012
  • Synchronization of finite automata

    Russian Mathematical Surveys

    Authors : Mikhail Vladimirovich Volkov ORCID

    Journal reference : Volume 77, 2022, pp. 819-891

    DOI : 10.4213/rm10005e
  • Synchronizing automata preserving a chain of partial orders

    Theoretical Computer Science

    Authors : M.V. Volkov ORCID

    Journal reference : Volume 410, 2009, pp. 3513-3519

    DOI : 10.1016/j.tcs.2009.03.021
  • Careful Synchronization of One-Cluster Automata

    Jagiellonian University Repository (Jagiellonian University)

    Authors : Jakub Ruszil ORCID

    Journal reference : Volume , 2024, pp. 252-265

    DOI : 10.1007/978-3-031-66159-4_18
  • The Černý Conjecture and 1-Contracting Automata

    The Electronic Journal of Combinatorics

    Authors : Henk Don ORCID

    Journal reference : Volume 23, 2016, pp.

    DOI : 10.37236/5616
  • Slowly synchronizing automata with fixed alphabet size

    Information and Computation

    Authors : Henk Don ORCID, Hans Zantema, Michiel de Bondt

    Journal reference : Volume 279, 2020, pp. 104614

    DOI : 10.1016/j.ic.2020.104614
Preview
Loading PDF preview...