Apakah automata berjalan-pohon non-deterministik lebih kuat dari automata deterministik?

10

Pembaruan: Tampaknya masalah ini telah dipelajari dan diselesaikan baru-baru ini, lihat artikel wiki ini: http://en.wikipedia.org/wiki/Tree_walking_automaton Dan juga survei ini: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf

Misalkan alih-alih seperangkat kata yang biasa, {0,1} *, kata-kata kita tidak linear tetapi diberikan pada beberapa struktur pohon. Untuk mencegah mesin kami dari "tersesat", tentukan kata-kata kami sebagai himpunan biner, punjung yang tertanam. (Jadi setiap kata adalah pohon, di mana setiap tepi diarahkan jauh dari akar yang diberikan derajat dua, setiap simpul non-daun lainnya memiliki derajat tiga, dan setiap tepi diberi label kiri atau kanan sehingga setiap dua tepi mulai dari simpul yang sama memiliki label yang berbeda.) Bahasa adalah seperangkat pohon seperti itu. (Perhatikan bahwa tidak perlu menulis nol dan yang pada simpul karena mereka dapat disimulasikan dengan memodifikasi pohon secara lokal.) Ketika mesin "membaca pohon", itu dimulai dari root, itu bisa merasakan jika diberikan simpul adalah root,

Benarkah dalam model ini bahwa bahasa apa pun yang dapat dikenali oleh otomat keadaan terbatas non-deterministik juga dapat dikenali oleh otomat keadaan terbatas deterministik?

Perhatikan bahwa ketika rekaman itu adalah pita linear biasa, ini benar, karena 2-NFA dapat disimulasikan dengan 2-DFA (bahkan dengan DFA). Saya sudah bertanya contoh khusus dari masalah di sini yang diselesaikan oleh Kristoffer . Motivasinya adalah untuk menyelesaikan ini .

cc.complexity-theory automata-theory space-bounded dfa domotorp
sumber
2
Saya akan menyarankan memodifikasi judul untuk menyebutkan " automata berjalan pohon non-deterministik ".
Sylvain

Jawaban:

6

Untuk tree automata, Anda memiliki hasil berikut:

  • Automata bottom-up tree automata memiliki kekuatan ekspresif yang sama dengan automata tree bottom-up non-deterministik.

  • Automata top-down tree automata lebih lemah daripada automata top-down tree non-deterministik.

Rincian lebih lanjut dapat ditemukan di buku Tree Automata .

Tampaknya Anda tertarik pada pohon automata top-down, jadi jawaban untuk pertanyaan Anda adalah tidak . Anda tentu saja harus memeriksa apakah pohon automata top-down sebenarnya adalah apa yang Anda minati.

Dave Clarke
sumber
1
Tidak, tidak satu pun dari ini, tetapi artikel wiki memiliki tautan ke gagasan yang saya definisikan: en.wikipedia.org/wiki/Tree_walking_automaton
domotorp