Status dugaan Cerny?

19

DFA memiliki kata sinkronisasi jika ada string yang mengirim keadaan DFA ke satu keadaan. Dalam 'The Cerny Conjecture for Aperiodic Automata ”oleh AN Trahtman (Matematika Diskrit dan Ilmu Komputer Teoritis vol. 9: 2, 2007, hal.3-10), ia menulis,

Cerny menduga pada tahun 1964 bahwa setiap N-state DFA yang dapat disinkronisasi memiliki panjang kata sinkronisasi yang paling banyak .(n−1)2

Dia juga menulis, "dalam kasus ketika grafik yang mendasari DFA aperiodik sangat terhubung, batas atas ini baru-baru ini ditingkatkan oleh Volkov yang telah mengurangi estimasi menjadi n(n+1)/6 .

  1. Adakah yang tahu status dugaan Cerny saat ini?

  2. Dan di mana kertas Volkov memperoleh hasil n (n +1) / 6?

Terima kasih atas penunjuk atau tautan apa pun.

fl.formal-languages automata-theory open-problem synchronization scaaahu
sumber
Setelah saya memposting pertanyaan, saya melakukan pencarian dan menemukan jawaban dari pertanyaan kedua saya, di mana kertas Volkov memperoleh hasil n (n +1) / 6? Jawabannya adalah Catatan Kuliah 'Menyinkronkan Automata Melestarikan Rantai Pesanan Parsial' dalam Ilmu Komputer, 2007, Volume 4783/2007, 27-37, DOI: 10.1007 / 978-3-540-76336-9_5
scaaahu
8
Anda dapat mengedit pertanyaan untuk mencerminkan ini.
Suresh Venkat

Jawaban:

19

Trakhtman memiliki daftar pustaka tentang masalah tersebut, yang tampaknya terus diperbarui; jadi saya kira pertanyaan remainserný masih belum terselesaikan sampai hari ini. Hal yang sama dinyatakan dalam survei terbaru Volkov (LATA 2008) yang ditautkan dari artikel wikipedia yang dikutip dalam pertanyaan. Di sana Anda menemukan petunjuk untuk beberapa hasil parsial, misalnya, untuk subclass mana dari bahasa-bahasa biasa, dugaan tersebut diketahui benar. Yang lebih baru adalah makalah penelitian oleh Ananichev, Gusev & Volkov (MFCS 2010) tentang topik terkait, di mana mereka mengkonfirmasi bahwa dugaan ýerný masih terbuka sekarang (setidaknya pada Mei 2010).

Hermann Gruber
sumber
2
Pada 2012, Trahtman mengunggah kertas ke arXiv, di mana ia menyajikan upaya untuk menyelesaikan dugaan tersebut. Ini lebih dari setahun yang lalu. Apakah ada berita tentang kebenaran buktinya?
molnarg
2
Di bagian komentar pada versi saat ini (v7) dari preprint arXiv, penulis menyatakan "13 halaman, contoh, versi yang salah. Bukti dugaan iserný salah": arxiv.org/ab/1202.4626
Hermann Gruber
3

lihat ArXiv: 1405.2435 cs.FL "Panjang kata sinkronisasi minimal dan dugaan \ v {C} erny" dengan kisah studi https://arxiv.org/pdf/1405.2435.pdf

trahtman
sumber
3
Akan lebih baik untuk meringkas klaim utama dari makalah ini - jika tidak, ini adalah jawaban tautan saja.
chi
Diperburuk oleh fakta bahwa tautannya terputus.
domotorp