Algoritma persimpangan DFA untuk kasus khusus

9

Saya tertarik pada algoritma yang efisien untuk persimpangan DFA untuk kasus khusus. Yaitu, ketika DFA untuk memotong mematuhi struktur tertentu dan / atau beroperasi pada alfabet terbatas. Apakah ada sumber di mana saya dapat menemukan algoritma kasus seperti itu?

Agar tidak membuat pertanyaan terlalu luas, struktur berikut ini sangat menarik: semua DFA untuk memotong beroperasi dalam alfabet biner (0 | 1), mereka juga dapat menggunakan simbol tidak peduli. Selain itu, semua negara hanya memiliki satu transisi kecuali untuk paling banyak negara khusus K, yang hanya memiliki dua transisi (dan transisi ini selalu 0 atau 1, tetapi tidak peduli). K adalah bilangan bulat, kurang dari 10 untuk tujuan praktis. Juga, mereka memiliki satu negara penerima. Selain itu, diketahui bahwa persimpangan SELALU DFA dalam bentuk "strip", yaitu, tidak ada cabang seperti pada gambar berikut:

masukkan deskripsi gambar di sini

EDIT: Mungkin deskripsi kendala pada input DFA tidak terlalu jelas. Saya akan mencoba memperbaikinya dalam paragraf ini. Anda memiliki sebagai input T DFA. Masing-masing DFA ini hanya beroperasi pada alfabet biner. Masing-masing dari mereka memiliki paling banyak N negara. Untuk setiap DFA, masing-masing negara bagian adalah salah satu dari yang berikut:

1) negara penerima (hanya satu dan tidak ada transisi dari itu ke negara lain)

2) negara dengan dua transisi (0 dan 1) ke negara target yang sama (mayoritas negara adalah jenis ini)

3) keadaan dengan dua transisi (0 dan 1) ke status target yang berbeda (paling banyak K dari jenis ini)

Dijamin bahwa hanya ada satu negara penerima dan bahwa ada paling banyak negara K tipe (3) di setiap input DFA. Hal ini juga dijamin bahwa persimpangan DFA dari semua DFAs masukan adalah "strip" (seperti dijelaskan di atas), ukuran kurang dari N .

EDIT2: Beberapa kendala tambahan, seperti yang diminta oleh DW dalam komentar:

  • Input DFA adalah DAG.
  • Input DFA "diratakan", mengikuti definisi DW dalam komentar. Yaitu, Anda dapat menetapkan bilangan bulat yang berbeda untuk setiap negara sedemikian rupa sehingga setiap transisi beralih dari bilangan bulat u ke bilangan bulat v , sehingga u + 1 = v .
  • Jumlah menerima negara untuk setiap masukan DFA, tidak melebihi K .

Ada ide? Terima kasih.

ale64bit
sumber
Bagaimana tepatnya Anda memodelkan "tidak peduli"? Tampaknya membuat automata nondeterministic, dengan cara.
Shaull
@Shaull Mengapa itu membuat automaton non deterministik. Itu bisa terjadi hanya jika ada transisi lain dari negara yang sama, yang secara eksplisit dikecualikan.
babou
1
Apa a DFA in form of "strip", i.e., no branches? Apakah Anda punya alasan khusus untuk percaya bahwa seseorang dapat melakukan lebih baik daripada algoritma standar dalam kasus Anda?
babou
1
Hai. Menghitung persimpangan yang sebenarnya akan menjadi besar, karena akan menyederhanakan banyak hal, tetapi memutuskan kekosongan akan berguna juga.
ale64bit
1
hanya berlari melintasi kertas baru pada grafik persimpangan , dapatkah beberapa teori ini relevan? Bisakah Anda memperluas aplikasi Anda yang disebutkan dalam komentar Anda di Theoretical Computer Science Chat ? & undang orang lain untuk melanjutkan diskusi lebih lanjut di sana.
vzn

Jawaban:

9

[2]

NC3


[1]{0,1}uvuv

  1. L-selesai untuk satu status akhir di setiap DFA,
  2. Lengkap NL untuk dua status akhir di setiap DFA, dan
  3. Lengkapi NP untuk tiga atau lebih status akhir di setiap DFA.

KK=2

Karena itu, tidak , saya rasa tidak ada algoritma yang efisien untuk masalah Anda.

[3]


x2x3x5

gadget pengurangan

Perhatikan bahwa automata adalah pohon (dan karenanya DAG), diratakan, dan memiliki tiga status akhir. Sebenarnya, tiga kondisi terakhir tidak dapat digabung menjadi satu, jika ada yang puas dengan DAG. Selain itu, hanya dua negara bagian yang memiliki dua transisi keluar (berbeda).

  1. Michael Blondin. Complexité raffinée du problème d'intersection d'automates, M.Sc. tesis, Université de Montréal, 2012.
  2. Michael Blondin, Andreas Krebs et Pierre McKenzie. Kompleksitas Automata Hingga Intersecting Memiliki Beberapa Status Akhir, Kompleksitas Komputasi (CC), 2014.
  3. Michael Wehar. Hasil Kekerasan untuk Persimpangan Non-Kekosongan. ICALP, 2014.
Michael Blondin
sumber
2
Terima kasih banyak! Saya menerima jawaban Anda. Pertanyaan tersebut berasal dari beberapa tes praktis di mana semuanya berkurang setelah banyak langkah untuk memotong solusi dari banyak DFA dengan karakteristik khusus ini. Namun demikian, kami mengamati bahwa meskipun pada akhirnya kami akan mendapatkan DFA sederhana, proses tidak pernah selesai karena DFA menengah (sementara berpotongan secara berurutan) tumbuh liar menjadi sejumlah negara yang eksponensial. Demikian pertanyaannya, tentang bagaimana mendapatkan jawaban tanpa melalui langkah perantara "naif".
ale64bit
1
Terima kasih banyak (dan maaf karena tidak jelas, saya di bawah pemula di bidang ini). Sekarang ada sesuatu yang tidak saya dapatkan. Anda menyebutkan bahwa "berbentuk pohon" berarti "jalur unik dari root ke setiap simpul lain". Tetapi, misalnya, dalam gambar yang Anda poskan di edit, itu bukan pohon (kecuali Anda menghitung transisi 0/1 sebagai label tunggal)?
ale64bit
1
Anda benar, tetapi pemahaman saya adalah bahwa Anda mengizinkan transisi "tidak peduli". Bukankah begitu?
Michael Blondin
2
Hai Michael. Terima kasih atas jawaban yang bagus. Saya harap semuanya baik-baik saja. :)
Michael Wehar
2
@MichaelWehar Jika Anda memperbaiki k dan c, Anda menyebutkan bahwa Anda dapat menyelesaikan masalah "dengan cepat". Tetapi Anda tidak menyebutkan kompleksitas waktu, hanya kompleksitas ruang. Apa sebenarnya arti "cepat" dalam konteks itu?
ale64bit