Mariusz Grech ; Andrzej Kisielewicz - The Cerný conjecture for automata respecting intervals of a directed graph

dmtcs:619 - Discrete Mathematics & Theoretical Computer Science, November 3, 2013, Vol. 15 no. 3 - https://doi.org/10.46298/dmtcs.619
The Cerný conjecture for automata respecting intervals of a directed graph

Authors: Mariusz Grech ORCID-iD1; Andrzej Kisielewicz 1

  • 1 Mathematical Institute [Wroclaw]

The Cerný's conjecture states that for every synchronizing automaton with n states there exists a reset word of length not exceeding (n - 1)2. We prove this conjecture for a class of automata preserving certain properties of intervals of a directed graph. Our result unifies and generalizes some earlier results obtained by other authors.

https://doi.org/10.46298/dmtcs.619
Source: HAL:hal-00966381v1
Volume: Vol. 15 no. 3
Section: Automata, Logic and Semantics
Published on: November 3, 2013
Accepted on: June 9, 2015
Submitted on: July 11, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1708.04864
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1708.04864
  • 10.48550/arxiv.1708.04864
  • 1708.04864
Synchronizing automata and the language of minimal reset words

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 291 times.
This article's PDF has been downloaded 253 times.