On Carpi and Alessandro conjecture

Details On Carpi and Alessandro conjecture On Carpi and Alessandro conjecture

2009-09-21

arxiv.org/abs/0909.3790v2

Computer Science

Formal Languages and Automata Theory

11 pages, 1 figure

Scientific paper

The well known open \v{C}ern\'y conjecture states that each \san with $n$ states has a \sw of length at most $(n-1)^2$. On the other hand, the best known upper bound is cubic of $n$. Recently, in the paper \cite{CARPI1} of Alessandro and Carpi, the authors introduced the new notion of strongly transitivity for automata and conjectured that this property with a help of \emph{Extension} method allows to get a quadratic upper bound for the length of the shortest \sws. They also confirmed this conjecture for circular automata. We disprove this conjecture and the long-standing \emph{Extension} conjecture too. We also consider the widely used Extension method and its perspectives.

Affiliated with

Also associated with

No associations

Rating

On Carpi and Alessandro conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Carpi and Alessandro conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Carpi and Alessandro conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-432962