Discrete Mathematics & Theoretical Computer Science, Vol 17, No 1 (2015)

Font Size:  Small  Medium  Large

A Note on a Recent Attempt to Improve the Pin-Frankl Bound

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

Abstract


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.

Full Text: PDF