Seberapa cepat kita dapat memutuskan apakah DFA yang diberikan minimal?

Meminimalkan deterministic finite automata (DFAs) adalah masalah yang telah dipelajari secara menyeluruh dalam literatur, dan beberapa algoritma telah diusulkan untuk menyelesaikan masalah berikut: Dengan DFA , hitung DFA minimal yang sesuai yang menerima bahasa yang sama dengan . Sebagian besar algoritma ini berjalan dalam waktu polinomial. $\mathscr{A}$ $\mathscr{A}$

Namun, saya bertanya-tanya apakah varian keputusan dari masalah ini - "diberi DFA , apakah minimal?" - dapat diselesaikan lebih efisien daripada benar-benar menghitung otomat minimal. Jelas, ini juga dapat dilakukan secara efisien dengan menjalankan misalnya algoritma perbaikan partisi Hopcroft dan kemudian memutuskan apakah semua partisi mengandung tepat satu keadaan. $\mathscr{A}$ $\mathscr{A}$

Seperti yang Yuval Filmus sarankan dalam jawabannya , varian decidability dapat diselesaikan lebih cepat, mungkin dengan menggunakan algoritma standar. Sayangnya, saya tidak bisa melihat caranya (saya harap saya tidak kehilangan poin yang jelas di sini).

Yuval menunjukkan dalam komentar di sini bahwa algoritma yang paling dikenal (seperti yang di atas) berjalan dalam waktu untuk huruf berukuran konstan. Oleh karena itu, saya tidak hanya tertarik pada keuntungan asimtotis yang signifikan dalam runtime, karena ini tampaknya agak tidak mungkin. Yang paling menggangguku adalah bahwa aku tidak bisa membayangkan "jalan pintas" apa pun yang mungkin diambil dari fakta bahwa kita hanya tertarik pada jawaban ya-tidak-tidak - bahkan jalan pintas yang memungkinkan untuk menghemat jumlah waktu yang dapat diabaikan secara asimptot. Saya merasa bahwa setiap algoritma yang masuk akal yang menentukan minimal DFA harus benar-benar meminimalkan DFA dan melihat apakah ada perubahan selama proses. $\mathcal{O}(n \log n)$

algorithms formal-languages finite-automata Cornelius Brand
sumber

Algoritma Hopcroft sudah berjalan dalam waktu singkat, jadi tidak ada banyak ruang untuk perbaikan.

Yuval Filmus

Ya, saya mengedit pertanyaan saya sehingga mencerminkan fakta ini, @YuvalFilmus

Cornelius Brand

Saya percaya algoritma minimalisasi DFA yang paling cepat diketahui masih yang satu ini . Ini lebih cepat daripada algoritma apa pun yang diterbitkan sebelum 2008 yang berjalan dalam waktu , di mana adalah jumlah transisi.

O (n + m \log n)

$O(n+m \log n)$

m

$m$

Juho

tampaknya tidak mungkin bagi saya masalah keputusan setara dalam kompleksitas dengan masalah minimisasi, yang pertama tampaknya mungkin lebih sulit karena melibatkan pengujian untuk kesetaraan DFA yang tidak biasa. jadi sepertinya kompleksitas dari masalah keputusan adalah maksimum "minimalisasi atau pengujian kesetaraan". dan apa kompleksitas pengujian kesetaraan?

vzn

@ vzn Anggap saja Anda bermaksud "[...] yang bukan trivial": Tidak harus seperti itu, misalnya prosedur yang saya berikan dalam pertanyaan saya menghindari pengujian untuk kesetaraan. Namun, saya juga berpikir bahwa masalahnya tidak semudah meminimalkan.

Cornelius Brand

Jawaban:

Ini mungkin bukan jenis jawaban yang Anda cari, tetapi karena Anda bertanya tentang masalah keputusan, saya pikir Anda mungkin tertarik pada kompleksitas masalah. Ini -lengkap. $\mathsf{NL}$

Sekarang, apa artinya DFA menjadi minimal? Ada dua properti:

Setiap negara dapat dijangkau: sedemikian rupa sehingga kita dapat mencapai dari status awal dengan mengikuti ; dalam simbol: . $\forall q \in Q \; \exists w \in \Sigma^*$ $q$ $s$ $w$ $s \rightarrow_w q$
Setiap pasangan negara dapat dibedakan: dengan sedemikian rupa sehingga dan dan (hanya satu dari adalah keadaan terima). $\forall q,r \in Q$ $q \neq r$ $\exists w \in \Sigma^*$ $q \rightarrow_w s$ $r \rightarrow_w t$ $|\{s,t\} \cap F| = 1$ $s,t$

Perhatikan bahwa dapat dihitung dalam log-ruang (yaitu ; hanya melacak posisi Anda saat Anda mengikuti satu huruf pada suatu waktu). Lebih jauh lagi, hanya ada sejumlah alternatif antara dan sehingga sebagai akibat dari teorema Immerman-Szelepcsenyi , kita memiliki masalah dalam . $x \rightarrow_w y$ $\mathsf{L}$ $w$ $\forall$ $\exists$ $\mathsf{NL}$

Cara termudah untuk melihat bahwa itu sulit untuk adalah untuk memperhatikan bahwa properti 1 memecahkan - diarahkan unreachability, yang merupakan masalah sulit prototipe. Tetapi bahkan jika Anda menganggap hanya DFA yang dapat dijangkau, masalahnya masih sulit (yaitu properti 2 adalah -hard) dan Anda dapat menemukan bukti yang relatif mudah di Lemma 2.2 dari Cho & Huynh (1992) . $\mathsf{NL}$ $s$ $t$ $\mathsf{NL}$

Tentu saja, saya menggunakan non-determinisme, jadi itu sedikit batuk dalam cara berbeda dari algoritma Hopcroft. Tetapi kita tahu bahwa , sehingga Anda dapat menggunakan konstruksi tersebut untuk mendapatkan algoritma yang lebih hemat-ruang daripada Hopcroft (yang pada dasarnya harus melacak banyak partisi ). $\mathsf{NL} \subseteq \mathsf{L}^2$ $n$

Artem Kaznatcheev
sumber

ini tampaknya meningkatkan ruang tetapi bukan kompleksitas waktu?

vzn

Saya setuju dengan vzn. Meskipun saya menyukai jawaban ini, saya masih tertarik pada wawasan yang lebih dekat hubungannya dengan pertanyaan awal.

Cornelius Brand

@ C.Brand Jawaban saya dimaksudkan sebagai tangensial (karena itu penafian di awal;)) Saya baru saja memberi Anda kelas kompleksitas terendah yang saya tahu masalahnya harus diselesaikan. Ada teknik standar untuk mengonversi menjadi yang (yaitu BFS pada grafik konfigurasi ) tetapi saya tidak berpikir bahwa konstruksi akan memberi Anda algoritma waktu yang lebih cepat.

N L

$\mathsf{NL}$

P

$\mathsf{P}$

Artem Kaznatcheev