Persimpangan DFA di ruang subquadratic?

25

Perpotongan dua (minimal) DFA dengan n status dapat dihitung menggunakan O (n ² ) waktu dan ruang. Ini optimal secara umum, karena DFA (minimal) yang dihasilkan mungkin memiliki n ² status. Namun, jika DFA minimal yang dihasilkan memiliki status z, di mana z = O (n), dapatkah ia dihitung dalam ruang n ^2-eps , untuk beberapa eps konstan> 0? Saya akan tertarik pada hasil seperti itu bahkan untuk kasus khusus di mana input DFA asiklik.

automata-theory dfa Rasmus Pagh
sumber

3

Um ... jika dua n-state DFA adalah asiklik, maka masing-masing hanya menerima satu set panjang kata hingga paling banyak n, dalam hal ini perpotongan mereka hanya persimpangan dari dua grafik transisi berlabel, yang akan memiliki n negara dan dapat dihitung dalam ruang dan waktu linier. Atau apakah saya melewatkan sesuatu?

Joshua Grochow

4

Ya, DFA asiklik hanya menerima serangkaian kata yang terbatas. Tetapi ada beberapa contoh DFA asiklik yang simpangnya memiliki ukuran n ^ 2. Misalnya, pikirkan tentang satu DFA yang menerima string dari bentuk AABC (di mana ABC adalah string dengan panjang k), dan yang menerima string dari bentuk ABCC.

Rasmus Pagh

1

retagging: cs.cc adalah sebutan arxiv, jadi tag yang diberikan tidak memerlukan awalan cs.cc.

Suresh Venkat

15

Jawabannya adalah ya tanpa persyaratan tentang ukuran otomat. Ia dapat dihitung dalam ruang bahkan untuk DFAs di mana adalah konstanta. $O(\log^2 n)$ $k$ $k$

Biarkan ( menjadi DFA. Kami menunjukkan bahwa, dengan , menghitung DFA minimal yang mengenali dapat dilakukan dalam spasi. Kami pertama-tama membuktikan beberapa hasil teknis. $A_i = (Q_i, \Sigma_i, \delta_i, z_i, F_i)$ $i \in [k])$ $k$ $\langle A_1, \ldots, A_k \rangle$ $\text{L}(A_1) \cap \cdots \cap\text{L}(A_k)$ $O(\log^2 n)$

Definisi 1 : Misalkan menjadi dua keadaan lalu iff , $q, r$ $q \equiv r$ $\forall w \in \Sigma^*$ $q . w \in F \Leftrightarrow r . w \in F$

Kami sekarang mempertimbangkan otomat diberikan oleh konstruksi produk kartesius klasik. Biarkan dan menjadi negara . $A$ $q = (q_1, \ldots, q_k)$ $r = (r_1, \ldots, r_k)$ $A$

Lemma 1 : Memutuskan apakah ada di NL. $q \equiv r$

Bukti (sketsa): Kami menunjukkan bahwa pengujian ketidakseimbangan dalam NL dan menggunakan NL = coNL. Tebak kata (satu huruf pada saat itu) sedemikian rupa sehingga adalah kondisi akhir dan tidak. Ini dapat dicapai dengan menghitung dalam log-space untuk dan menggunakan fakta bahwa adalah final iff . Dapat ditunjukkan bahwa menyiratkan keberadaan dari ukuran-poli. $w \in \Sigma^*$ $q . w$ $r . w$ $q_i . w, r_i . w$ $i \in [k]$ $q$ $q_i \in F_i \, \forall i \in [k]$ $q \not\equiv r$ $w$

Lemma 2 : Memutuskan apakah dapat diakses di NL. $q$

Bukti (sketsa): Tebak jalur (ukuran-poli) dari ke ( ). $z_i$ $q_i$ $i \in [k]$

Definisi 2 : Pertimbangkan keadaan dalam urutan leksikografis. Tentukan sebagai negara yang dapat diakses pertama dan negara yang dapat diakses pertama setelah yang tidak setara dengan keadaan sebelumnya. Kami mendefinisikan sebagai unik sedemikian rupa sehingga . $A$ $s(1)$ $s(i)$ $s(i-1)$ $c(q)$ $i$ $q \equiv s(i)$

Lemma 3 : dapat dihitung dalam ruang . $s(i)$ $O(\log^2 n)$

Bukti (sketsa): Definisi 2 menghasilkan suatu algoritma. Kami menggunakan counter untuk beralih ke negara bagian. Biarkan dan menjadi kondisi saat ini. Di setiap negara bagian, kami menggunakan lemma 2 untuk memverifikasi apakah dapat diakses. Jika ya, kami mengulangi setiap status sebelumnya dan kami memverifikasi apakah ada di antaranya yang setara dengan . Jika tidak ada, kami menambah dan output jika . Kalau tidak, kita menyimpan sebagai dan kami melanjutkan. Karena kami hanya menyimpan jumlah penghitung yang konstan dan pengujian kami dapat dilakukan dalam $k$ $j \leftarrow 0$ $q$ $q$ $q$ $j$ $q$ $j = i$ $q$ $s(j)$ $\text{NL} \subseteq \text{DSPACE}(\log^2 n)$ , ini melengkapi buktinya.

Akibat wajar 1 : dapat dihitung dalam ruang . $c(q)$ $O(\log^2 n)$

Teorema : Meminimalkan dapat dilakukan dalam ruang . $A$ $O(\log^2 n)$

Bukti (sketsa): Biarkanmenjadi terbesar sehingga didefinisikan (mis. jumlah kelas ). Kami memberikan algoritme yang mengeluarkan otomat mana $1 \leq m \leq |Q_0| \cdots |Q_1|$ $i$ $s(i)$ $\equiv$ $A' = (Q', \Sigma, \delta', z', F')$

$Q' = \lbrace s(i) : i \in [m] \rbrace$ ;
$F' = \lbrace q \in Q' : q_i \in F_i \, \forall i \in [k] \rbrace$ ;
$z' = s(c(q))$ mana . $q = (z_0, \ldots, z_k)$

Kami sekarang menunjukkan cara menghitung . Untuk setiap , hitung dan output transisi . Oleh lemma 3 dan akibat wajar 1, algoritma ini berjalan dalam ruang . Dapat diperiksa bahwa minimal dan . $\delta'$ $i \in [m], a \in \Sigma$ $q \leftarrow s(i) . a$ $\left(s(i), a, s(c(q))\right)$ $O(\log^2 n)$ $A'$ $\text{L}(A') = \text{L}(A)$

Michael Blondin
sumber

3

Algoritma yang bagus! Berikut ini cara yang sedikit berbeda untuk melihat algoritma ini. Intinya adalah bahwa meminimalkan keadaan setiap DFA yang diberikan dapat dilakukan dalam waktu polinomial dan ruang. Setelah itu, mudah untuk membangun beberapa DFA yang mewakili persimpangan dalam ruang logaritmik (maka dalam waktu polinomial dan ruang ), dan kita dapat menyusun dua fungsi yang dapat dihitung dalam waktu polinomial dan ruang (dengan cara yang mirip dengan menyusun dua reduksi ruang-logaritmik), menghasilkan keseluruhan algoritma dalam waktu polinomial dan ruang .

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

Tsuyoshi Ito

2

Saya baru saja melihat jawaban ini ... Saya tidak melihat mengapa algoritma berjalan dalam ruang polytime dan secara bersamaan. Ya, , tetapi tidak diketahui apakah - yaitu, kita dapat dapatkan algoritme yang berjalan dalam polytime, dan kita bisa mendapatkan algoritme lain yang berjalan di ruang , tapi saya tidak tahu bagaimana menyelesaikan masalah dalam ruang polytime dan dengan satu algoritma.

O (\log^{2} n)

$O(\log^2 n)$

N L \subseteq P \cap D S P A C E [\log^{2} n]

$NL \subseteq P \cap DSPACE[\log^2 n]$

N L \subseteq T I S P [n^{O (1)}, \log^{2} n]

$NL \subseteq TISP[n^{O(1)}, \log^2 n]$

O (\log^{2} n)

$O(\log^2 n)$

N L

$NL$

O (\log^{2} n)

$O(\log^2 n)$

Ryan Williams

Anda benar, saya juga tidak tahu. Saya memposting ini sejak lama, jadi saya tidak yakin mengapa saya menulisnya seperti ini, tapi mungkin saya maksudkan "waktu polinomial atau O (log² n)". Saya akan mengeditnya karena itu menyesatkan. Terima kasih!

Michael Blondin

14

Dick Lipton dan rekannya baru-baru ini menangani masalah ini, dan Lipton menulis blog tentang itu di sini:

http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

Tampaknya melakukan lebih baik daripada O (n ^ 2) terbuka bahkan untuk kasus yang sangat khusus untuk menentukan apakah persimpangan DFA mendefinisikan bahasa kosong.
Makalah ini memberikan konsekuensi kompleksitas yang akan dihasilkan dari penanganan algoritma yang jauh lebih baik tidak hanya 2 DFA di persimpangan, tetapi jumlah yang lebih besar juga.

Andy Drucker
sumber

1

dan bagaimana dengan batas bawah?

Marcos Villagra

1

Hanya untuk mengklarifikasi pertanyaan: Saya senang menghabiskan waktu O (n ^ 2) (atau bahkan mungkin n ^ O (1) waktu) untuk meningkatkan batas ruang.

Rasmus Pagh

13

Jika Anda diberi k DFA (k adalah bagian dari input) dan ingin tahu apakah persimpangannya kosong, masalah ini umumnya selesai dengan PSPACE:

Dexter Kozen: Batas Bawah untuk Sistem Bukti Alami FOCS 1977: 254-266

Mungkin jika Anda hati-hati mempelajari bukti ini (dan konstruksi serupa oleh Lipton dan rekan penulisnya), Anda mungkin menemukan semacam ruang dengan batas bawah bahkan untuk k tetap.

Ryan Williams
sumber

Terima kasih atas penunjuk ini. Saya menduga bahwa ini mungkin dapat menyebabkan ruang n ^ Omega (1) lebih rendah pada ruang tambahan yang dibutuhkan, terlepas dari input. Tetapi mungkinkah hal itu mengarah pada ruang super-linear batas bawah?

Rasmus Pagh

1

@ user124864 Diberikan DFA dengan menyatakan masing-masing, otomat produk akan memiliki status . Sekarang, ada dua trik yang bisa Anda lakukan untuk mengurangi ukurannya. Yang pertama adalah Anda hanya mempertimbangkan komponen yang dapat dijangkau dari grafik produk. Kedua, Anda bisa meminimalkan DFA produk. Pada akhirnya, mencari tahu bahasa apa yang dikenali oleh otomat produk ini sulit.

k

$k$

n

$n$

n^{k}

$n^k$

Michael Wehar

1

@ user124864 Bahkan hanya berusaha menentukan apakah produk DFA mengenali bahasa yang tidak kosong itu sulit. Ini adalah masalah non-kekosongan persimpangan. Dengan keras, maksud saya lengkap dalam arti yang kuat.

X N L

$XNL$

Michael Wehar

1

@ user124864 Jika Anda dapat menyelesaikannya dalam waktu kurang dari waktu, maka kita bisa lebih cepat algoritma untuk PSPACE masalah lengkap. Ini tidak dapat dipecahkan dalam ruang biner non-deterministik. Tidak diketahui apakah kita dapat menyelesaikannya dalam waktu kurang dari ruang biner deterministik. Tidak diketahui apakah kita dapat menyelesaikannya dalam waktu polinomial deterministik simultan dan ruang biner untuk fungsi apa pun (melakukan itu akan meningkatkan teorema Savitch).

n^{k}

$n^k$

o (1) \cdot k \cdot \log (n)

$o(1) \cdot k \cdot \log(n)$

k^{2} \log^{2} (n)

$k^2 \log^2(n)$

f (k) \cdot \log^{2} (n)

$f(k) \cdot \log^2(n)$

f

$f$

Michael Wehar

1

@ user124864 Catatan: kami memiliki keduanya berikut ini. (1) Pemukulan waktu deterministik menyiratkan algoritma deterministik lebih cepat untuk PSPACE masalah lengkap dan (2) pemukulan waktu non-deterministik menyiratkan algoritma lebih cepat non-deterministik untuk PSPACE masalah lengkap.

n^{k}

$n^k$

n^{k}

$n^k$

Michael Wehar

7

Diberikan dua automata , menerima bahasa berhingga (acyclic automata), kompleksitas negara ada di (1) . Hasil ini juga berlaku untuk DFA unary (belum tentu asiklik) (2) . Namun, Anda tampaknya berbicara tentang ruang yang diperlukan untuk menghitung persimpangan dua automata. Saya tidak melihat bagaimana konstruksi klasik menggunakan produk Cartesian menggunakan ruang . Yang Anda butuhkan hanyalah sejumlah konter ukuran logaritmik. Ketika Anda menghitung fungsi transisi untuk status baru Anda hanya perlu memindai input tanpa melihat ke data yang dihasilkan sebelumnya. $A$ $B$ $L(A) \cap L(B)$ $\Theta(|A| \cdot |B|)$ $O(n^2)$ $(q,r)$

Mungkin Anda ingin menampilkan robot minimal? Jika ini masalahnya, maka saya tidak tahu apakah itu bisa dicapai. Kompleksitas keadaan persimpangan untuk bahasa yang terbatas tampaknya tidak menggembirakan. Namun, DFA unary memiliki kompleksitas keadaan yang sama dan saya pikir itu dapat dicapai dengan automata tersebut. Dengan menggunakan hasil dari (2) , Anda bisa mendapatkan ukuran yang tepat dari robot yang mengenali persimpangan. Ukuran ini dijelaskan oleh panjang ekor dan siklus, sehingga fungsi transisi dapat dengan mudah dihitung dengan sedikit ruang karena struktur sepenuhnya dijelaskan oleh dua ukuran tersebut. Kemudian, yang harus Anda lakukan adalah membuat set status akhir. Biarkan menjadi jumlah status dalam otomat yang dihasilkan, maka untuk semua , $n$ $1 \leq i \leq n$ $i$ adalah keadaan akhir IFF diterima oleh kedua dan . Tes ini dapat dilakukan dengan sedikit ruang. $a^i$ $A$ $B$

Michael Blondin
sumber

1

Ya, saya tertarik dengan otomat minimal, atau setidaknya otomat dengan ukuran yang sama. Terima kasih atas petunjuk untuk DFA unary. Namun, ini tampaknya tidak banyak membantu untuk kasus umum.

Rasmus Pagh

Persimpangan DFA di ruang subquadratic?

Jawaban: