NFA ke DFA Powerset Construction: Algoritma determinasi parsial dengan trade-off antara waktu berjalan dan ukuran untuk automata yang dihasilkan?

Mengingat NFA $N$ dan yang setara DFA $D$ yang dihasilkan dari keseluruhan determinization dari $N$ (menggunakan konstruksi Powerset, misalnya), sifat-sifat berikut tahan selama $N$ , $D$ dan untuk setiap kata $w$ :

$N$ membaca $w$ dalam menjalankan waktu paling banyak $O(|w|.|N|^2)$ .
$D$ membaca $w$ dalam menjalankan waktu paling banyak $O(|w|)$ dan ukurannya mungkin $O(2^{|N|})$ (dalam jumlah negara yang diperlukan untuk mewakili $D$ ).

Saya bertanya-tanya apakah ada beberapa algoritma determinasi parsial yang menjamin trade-off antara ukuran hasil dan waktu berjalan?

Sebagai contoh, algoritma determinisasi parsial ini dapat mengubah NFA menjadi automata deterministik parsial $D'$ sedemikian rupa sehingga $D'$ menjamin bahwa kata $w$ dibaca dalam $O(|w|.|N|^x)$ mana $0 \leq x \leq 2$ tanpa melebihi ukuran $|D'| \leq 2^{f(x)}$ mana $f(x)$ adalah fungsi penurunan kontinu yang didefinisikan pada rentang $[0, 2]$ sedemikian rupa sehingga $f(0)=|N|$ dan $f(2)=log |N|$ .

Saya tidak menemukan metode apa pun untuk menentukan sebagian NFA sedemikian rupa. Dalam semua makalah: penentuan baik dihindari karena NFA terlalu besar, baik determinasi penuh dan NFA diubah menjadi DFA (dengan kemungkinan ledakan eksponensial). Tidak ada kompromi ...

Saya akan sangat menghargai referensi atau jawaban apa pun mengenai masalah ini. Terima kasih banyak, Luz.

automata-theory regular-language nondeterminism dfa nfa Luz
sumber

Apakah cstheory.stackexchange.com/a/1273/236 bermanfaat?

Radu GRIGore

Wow :-) ini luar biasa! Memang, postingan cstheory.stackexchange.com/questions/1132/… sepertinya melakukan pekerjaan itu. Terima kasih banyak, saya akan memproses jawaban D. Eppstein ...

Luz

Jawaban:

Makalah [HP06] dalam semangat ide Anda, meskipun dalam arah yang berbeda, dalam konteks kata-kata yang tak terbatas. Itu dapat diadaptasi lebih mudah untuk kata-kata yang terbatas.

Dalam konstruksi powerset, kami secara simultan melacak semua kemungkinan menjalankan otomat status- , dengan bergerak di sekitar token. Tetapi kita dapat memutuskan untuk mengikuti hanya running, dan melakukan konstruksi parsial powerset. Secara umum ini akan menghasilkan otomat non-deterministik, yang tidak benar-benar lebih berguna daripada yang asli. $n$ $n$ $k<n$

$k$ $a$ $b$ $2$ $2$ $\dfrac{n(n+1)}{2}$

$1$

$k$ $k$ $k$ $k$

[HP06] Memecahkan game tanpa determinasi , Henzinger, Piterman, di CSL 2006

[BKKS13] Nondeterminisme di hadapan masa depan yang beragam atau tidak diketahui , Boker, Kuperberg, Kupferman, Skrzypczak, di ICALP 2013

[KS15] Tentang Penentuan Good-for-Games Automata , Kuperberg, Skrzypczak, di ICALP 2015

Denis
sumber

Terima kasih banyak untuk posting Anda :-) tapi saya butuh sedikit bantuan untuk memahami gambaran besar dari apa yang Anda usulkan. Saya juga ingin memahami perbedaan utama antara posting Anda dan salah satu dari D. Eppstein (seperti yang disarankan dalam komentar atas), di sini: cstheory.stackexchange.com/questions/1132/… .

Luz

n

$n$

1 \leq x \leq n

$1 \leq x \leq n$

w

$w$

O (w . x^{2})

$O(w.x^2)$

O (x^{2} {.2}^{n / x})

$O(x^2.2^{n/x})$

k

$k$

N

$N$

n

$n$

S = O (\sum_{i = 0}^{k} (\binom{n}{i}))

$S=O(\sum\limits_{i=0}^{k}{{n}\choose{i}})$

k

$k$

N

$N$

T = O (w . k)

$T=O(w.k)$

N

$N$

Pertanyaan tambahan jika kedua hipotesis sebelumnya benar. Bayangkan sebuah usecase di mana ruang yang tersedia untuk menentukan diperbaiki sehingga dengan . Kemudian kita secara parsial menentukan menjadi dengan menerapkan konstruksi -powerset pada (karena ada cukup ruang untuk melakukannya). Apakah waktu maksimum yang diperlukan untuk mensimulasikan ?

S

$S$

N

$N$

S = O (\sum_{i = 0}^{p} (\binom{n}{i}))

$S=O(\sum\limits_{i=0}^{p}{{n}\choose{i}})$

p \leq k

$p \leq k$

N

$N$

N^{'}

$N'$

p

$p$

N

$N$

O (w . (k / p))

$O(w.(k/p))$

N^{'}

$N'$

Luz

(1) Ya (2) tidak yakin apa yang Anda maksud dengan "simulasi", tetapi Anda dapat dengan pasti memindahkan k token di N untuk melihat apakah sebuah kata diterima, jadi saya akan mengatakan ya (3) Ya, dengan langit-langit pada k / p

Denis