הצגת המקור של הדף "השערת צ'רני"

בתורת ה[[אוטומט סופי|אוטומטים הסופיים]], '''השערת צ'רני''' (ב[[אנגלית]]: '''Černý conjecture'''; על שם יאן צ'רני) היא השערה על האורך המקסימלי של [[מילה מסנכרנת]], באוטומט שיש בו מילה כזו. ההשערה קובעת שאם X היא משפחה של פונקציות מקבוצה בת n נקודות לעצמה, ואפשר ליצור מ-X באמצעות [[הרכבת פונקציות|הרכבה]] פונקציה קבועה, אז יש הרכבה כזו באורך שאינו עולה על <math>\ (n-1)^2</math>
{{הערה|1=J. Černý, Poznámka k homogénnym eksperimentom s konecnými automatami, Mat.-Fyz. Cas. Slovensk. Akad. Vied., Vol. 14, 208--216, (1964). (בסלובקית)}}.

את החסם שההשערה מציעה אי-אפשר לשפר. לדוגמה, מן התמורה <math>\ a=(1 2 \cdots n)</math> והפונקציה b המעבירה כל נקודה לעצמה, פרט לכך ש- <math>\ b(1)=2</math>, אפשר להגיע לערך קבוע באמצעות הסדרה <math>\ b(a^{n-1}b)^{n-2}</math>, ולא בשום דרך קצרה יותר. 

ידוע שההשערה נכונה אם הקבוצה X כוללת מחזור באורך n. החסם העליון הטוב ביותר הידוע כיום הוא <math>\ (n^3-n)/6</math>.

==ראו גם==
* [[בעיית צביעת המסלולים]]

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:אוטומטים]]
[[קטגוריה:בעיות פתוחות במדעי המחשב]]