Które języki nieregularne są w

Na przykład wiem, że nieregularny język $a^nb^n$ jest w . Chciałbym poznać więcej takich przykładów.$AC^0$

Języki w może być bardziej skomplikowane niż naiwny intuicja może sugerować.$AC^0$

• Oczywiście C 0 zawiera { a n b n c n } , który jest nie-context wolne.$AC^0$$\{a^n b^n c^n\}$
• Każdy język jednoargumentowy jest w niejednolitej formie ; na przykład problem zatrzymania wyrażony jednostronnie.$AC^0$
• Dodawanie można zaimplementować w za pomocą sumatora przeniesienia. Tutaj wejście ma 2 n bitów reprezentujących dwie liczby, a wyjście zawiera n + 1 przewodów (równoważnie, każdy bit wyjściowy może być zrealizowany w A C 0 )$AC^0$$2n$$n+1$$AC^0$

• Multipleksowanie: jest w A C 0 .$\{w x: |w|=2^n, |x|=n, w[x] = 1\}$$AC^0$

  Multiplekser to funkcja na zmiennych, która generuje wartość jednej z 2 n zmiennych, gdzie indeks jest określony przez n zmiennych. (To samo dotyczy indeksu zapisanego jednostronnie).$2^n+n$$2^n$$n$

• Obliczenia wzorów 3SAT są w .$AC^0$

  Dane wejściowe składają się z zmiennych, po których następują niektóre klauzule, każda zawiera trzy literały, przy czym każda literał jest indeksem zmiennej (jedno lub dwójkowy, nie ma znaczenia) i nieco wskazuje na możliwą negację. Możesz ocenić literały za pomocą multiplekserów, a następnie dodać warstwę OR, a następnie duży AND na wierzchu.$n$

• nie zawiera większość, ale nie zawiera w przybliżeniu większość: funkcję, która jest równa większości, jeśli wyjście ≥ $AC^0$zera lub jedynki. Zobacz „Przybliżone zliczanie z jednolitymi obwodami o stałej głębokości” autorstwa Ajtai.$\geq \frac{1}{2}+ \varepsilon$

jest zamknięty pod logicznej operacji, łączenie i kompozycji, aby można było połączyć w przykładach powyżej. Teraz powinieneś poczuć szacunek dla P a r i t y ∉ A C 0 i innych dolnych granic obwodu!$AC^0$$Parity \notin AC^0$