Gonze, François and Jungers, Raphaël M. and Trahtman, Avraham N. - 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
A note on a recent attempt to improve the Pin-Frankl bound

Authors: Gonze, François and Jungers, Raphaël M. and Trahtman, Avraham N.

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.


Source : oai: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]


Share

Browsing statistics

This page has been seen 36 times.
This article's PDF has been downloaded 59 times.