Welche nicht regulären Sprachen sind in ?

Zum Beispiel weiß ich, dass die nicht reguläre Sprache $a^nb^n$ in $AC^0$ . Ich würde gerne weitere Beispiele wie dieses kennenlernen.

Sprachen in können komplizierter sein, als es die naive Intuition vermuten lässt.$AC^0$

• Offensichtlich enthält { a n b n c n } , was nicht kontextfrei ist.$AC^0$$\{a^n b^n c^n\}$
• Jede unäre Sprache ist in ungleichmäßigem ; Zum Beispiel das Stoppproblem in unary ausgedrückt.$AC^0$
• Die Addition kann in mit einem Carry-Lookahead-Addierer implementiert werden . Hier besteht der Eingang aus 2 n Bits, die zwei Zahlen darstellen, und der Ausgang enthält n + 1 Drähte (äquivalent kann jedes Ausgangsbit in A C 0 realisiert werden ).$AC^0$$2n$$n+1$$AC^0$

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

  Ein Multiplexer ist eine Funktion für Variablen, die den Wert einer von 2 n Variablen ausgibt , wobei der Index durch die n Variablen bestimmt wird. (Gleiches gilt, wenn der Index unär geschrieben ist.)$2^n+n$$2^n$$n$

• Die Berechnung der 3SAT-Formeln erfolgt in .$AC^0$

  Die Eingabe besteht aus Variablen, gefolgt von einigen Klauseln. Jede enthält drei Literale, wobei jedes Literal ein Index der Variablen ist (unär oder binär, spielt keine Rolle) und ein Bit, das eine mögliche Negation anzeigt. Sie können die Literale mit Multiplexern auswerten und dann eine Schicht von ODERs und dann ein großes UND darüber hinzufügen.$n$

• enthält keine Mehrheit, aber eine ungefähre Mehrheit: eine Funktion, die der Mehrheit entspricht, wenn die Ausgabe ≥ $AC^0$Nullen oder Einsen. Siehe "Ungefähre Zählung mit gleichmäßigen Schaltungen mit konstanter Tiefe" von Ajtai.$\geq \frac{1}{2}+ \varepsilon$

wird unter logischen Operationen, Verkettung und Zusammensetzung geschlossen, sodass Sie die obigen Beispiele kombinieren können. Jetzt sollten Sie etwas Respekt vor P a r i t y ∉ A C 0 und anderen unteren Grenzen der Schaltung haben!$AC^0$$Parity \notin AC^0$