Recently, Carpi and D’Alessandro [3] have formulated a conjecture whose validity would imply an O(n 2) upper bound for the minimum length of reset words for synchronizing automata with n states. We refute this conjecture as well as a related conjecture by Rystsov [13] and suggest a weaker version that still suffices to achieve a quadratic upper bound.
Original languageEnglish
Title of host publicationDevelopments in Language Theory. DLT 2010
Subtitle of host publicationbook
EditorsY. Gao
Place of PublicationBerlin
PublisherSpringer
Pages66–75
Number of pages10
Volume6264
ISBN (Electronic)978-3-642-14455-4
ISBN (Print)978-3-642-14454-7
DOIs
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volumevol 6264
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

    WoS ResearchAreas Categories

  • Computer Science, Theory & Methods

    ASJC Scopus subject areas

  • Computational Theory and Mathematics

ID: 37847773