¿Qué idiomas no regulares están en ?

Por ejemplo, sé que el lenguaje no regular $a^nb^n$ está en $AC^0$ . Me gustaría saber más ejemplos como este.

Los idiomas en $AC^0$ pueden ser más complicados de lo que sugiere la intuición ingenua.

• Obviamente, contiene , que no está libre de contexto. { a n b n c n$AC^0$$\{a^n b^n c^n\}$
• Cada idioma unario está en no uniforme ; por ejemplo, el problema de detención expresado en unario.$AC^0$
• La adición se puede implementar en con un sumador de anticipación. Aquí la entrada es de bits que representan dos números, y la salida contiene cables (de forma equivalente, cada bit de salida puede realizarse en ) 2 n n + 1 A C $AC^0$$2n$$n+1$$AC^0$

• Multiplexación: está en .A C $\{w x: |w|=2^n, |x|=n, w[x] = 1\}$$AC^0$

  Un multiplexor es una función en variables que genera el valor de una de variables, donde el índice está determinado por las variables. (Lo mismo ocurre si el índice está escrito en unario).2 n$2^n+n$$2^n$$n$

• El cálculo de las fórmulas 3SAT está en .$AC^0$

  La entrada consta de variables, seguidas de algunas cláusulas, cada una contiene tres literales, donde cada literal es un índice de la variable (unario o binario, no importa) y un bit que indica una posible negación. Puede evaluar los literales con multiplexores y luego agregar una capa de OR y luego un gran AND en la parte superior.$n$

• ≥ $AC^0$ no contiene mayoría, pero contiene mayoría aproximada: una función que es igual a mayoría si la salida es ceros o unos. Consulte "Recuento aproximado con circuitos uniformes de profundidad constante" de Ajtai.$\geq \frac{1}{2}+ \varepsilon$

P a r i t y ∉ A C $AC^0$ se cierra en operaciones lógicas, concatenación y composición, por lo que puede combinar los ejemplos anteriores. ¡Ahora debe sentir un poco de respeto por y otros límites inferiores del circuito!$Parity \notin AC^0$