Hubungan antara

Biarkan menjadi kelas dari semua bahasa reguler.$\mathsf{REG}$

Diketahui dan \ mathsf {REG} \ tidak \ subset \ mathsf {AC} ^ 0 . Tetapi apakah ada karakterisasi untuk bahasa di \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?$\mathsf{AC}^0 \not\subset \mathsf{REG}$$\mathsf{REG} \not\subset \mathsf{AC}^0$$\mathsf{AC}^0 \cap \mathsf{REG}$

Makalah berikut ini sepertinya berisi jawaban:

Campur Barrington, DA, Compton, K., Straubing, H., Therien, D .: Bahasa reguler di $\mathsf{NC}^1$ . Jurnal Ilmu Komputer dan Sistem 44 (3), 478-499 (1992) ( tautan )

Salah satu penokohan yang didapat ada sebagai berikut. Kelas $\mathsf{REG} \cap \mathsf{AC}^0 \subset \{0, 1\}^*$ berisi persis bahasa-bahasa yang dapat diperoleh dari $\{0\}$ , $\{1\}$ dan $\mathsf{LENGTH}(q)$ untuk $q > 1$ dengan sejumlah terbatas operasi dan gabungan Boolean. Di sini setiap bahasa $\mathsf{LENGTH}(q)$ berisi semua string yang panjangnya dapat dibagi oleh $q$ . (Ada juga karakterisasi logis dan dua yang aljabar.)

Bahasa reguler di dalam adalah subset "bagus" dari bahasa biasa. Mereka memiliki karakterisasi logis dan aljabar yang bagus.$AC^0$

Buku "Finite Automata, Formal Logic, dan Complexity Circuit" oleh Straubing mempertimbangkan pertanyaan-pertanyaan ini.

Pertanyaan Anda dapat dijawab sebagai berikut.

F O [ < , S u c , ≡ $AC^0 \cap REG$ = = bahasa yang dikenali oleh monoids semu-aperiodik.$FO[<,Suc,\equiv]$

Di sini adalah logika urutan pertama menggunakan kurang dari, penerus dan predikat numerik.x ≡ ( 0 m o d q $FO[<,Suc,\equiv]$$x \equiv (0 ~mod ~q)$

Karakterisasi lain seperti yang ditunjukkan dalam "Bahasa reguler di " adalah himpunan bahasa yang dapat dibentuk menggunakan himpunan huruf hingga, PANJANG (q) dan menutupnya di bawah kombinasi dan gabungan boolean.$NC^1$