Dua arah deterministik penghitung multihead automata atau logspace TM dengan penghitung

Apakah itu diketahui sesuatu tentang bahasa yang dikenali oleh automaton counter multihead deterministik dua arah atau logspace TM dengan counter (model setara)? Kelas ini bernama Aux2DC dalam makalah penasihat saya . Atau tentang kelas nondeterministik seperti itu? Saya telah memperoleh bahwa kelas bahasa yang dikenali oleh maschine nondeterministic seperti itu termasuk NL dan sepertinya dimasukkan dalam LOGCFL. Apakah ada makalah tentang hal ini? Apakah hasilnya sepele?

cc.complexity-theory complexity-classes fl.formal-languages logspace counter-automata Alexander Rubtsov
sumber

Jawaban:

Automaton multi-head deterministik dua arah deterministik (nondeterministik) dapat disimulasikan oleh DTM logspace (NTM), dan sebaliknya.

$\mathsf{NL}$

$\mathsf{LOGCFL}$ $\mathsf{NL}$

$\mathsf{L}$ $\mathsf{NL}$

Ada banyak makalah tentang topik-topik ini, misalnya makalah ini . Anda dapat menemukan lebih banyak setelah beberapa googling. (Periksa juga Lemma 1 dari makalah ini .)

Abuzer Yakaryilmaz
sumber

Terima kasih, saya tahu tentang simulasi L (NL) oleh otomat dua arah multihead (nondeterministic). Pertama saya berpikir bahwa saya memperoleh inklusi NL untuk otomat deterministik dengan counter, tetapi tiba-tiba muncul bahwa dalam pengurangan saya nondeterminisme ditingkatkan dan saya memperbaiki postingan tetapi tidak sebaik yang seharusnya. Saya akan mempelajari makalah ini, terima kasih banyak!

Alexander Rubtsov