השערת צ'רני
בתורת האוטומטים הסופיים, השערת צ'רני (באנגלית: Černý conjecture; על שם יאן צ'רני) היא השערה על האורך המקסימלי של מילה מסנכרנת, באוטומט שיש בו מילה כזו. ההשערה קובעת שאם X היא משפחה של פונקציות מקבוצה בת n נקודות לעצמה, ואפשר ליצור מ-X באמצעות הרכבה פונקציה קבועה, אז יש הרכבה כזו באורך שאינו עולה על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (n-1)^2} [1].
את החסם שההשערה מציעה אי-אפשר לשפר. לדוגמה, מן התמורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a=(1 2 \cdots n)} והפונקציה b המעבירה כל נקודה לעצמה, פרט לכך ש- , אפשר להגיע לערך קבוע באמצעות הסדרה הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \ b(a^{n-1}b)^{n-2}} , ולא בשום דרך קצרה יותר.
ידוע שההשערה נכונה אם הקבוצה X כוללת מחזור באורך n. החסם העליון הטוב ביותר הידוע כיום הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (n^3-n)/6} .
ראו גם
הערות שוליים
- ^ J. Černý, Poznámka k homogénnym eksperimentom s konecnými automatami, Mat.-Fyz. Cas. Slovensk. Akad. Vied., Vol. 14, 208--216, (1964). (בסלובקית)
השערת צ'רני35456670Q7662204