François Gonze ; Raphaël M. Jungers ; Avraham N. Trahtman - A note on a recent attempt to improve the Pin-Frankl bound

dmtcs:2101 - Discrete Mathematics & Theoretical Computer Science, April 27, 2015, Vol. 17 no. 1 - https://doi.org/10.46298/dmtcs.2101
A note on a recent attempt to improve the Pin-Frankl boundArticle

Authors: François Gonze 1; Raphaël M. Jungers 1; Avraham N. Trahtman 2

  • 1 Institute of Information and Communication Technologies, Electronics and Applied Mathematics
  • 2 Department of Mathematics [Ramat Gan]

We provide a counterexample to a lemma used in a recent tentative improvement of the Pin-Frankl bound for synchronizing automata. This example naturally leads us to formulate an open question, whose answer could fix the line of the proof, and improve the bound.

https://doi.org/10.46298/dmtcs.2101
Source: HAL:hal-01196844v1
Volume: Vol. 17 no. 1
Section: Automata, Logic and Semantics
Published on: April 27, 2015
Submitted on: December 3, 2014
Keywords: Automata,Synchronization,Cerny’s conjecture,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 446 times.
This article's PDF has been downloaded 431 times.