Quelles langues non régulières sont dans ?

Par exemple, je sais que la langue non régulière est en . J'aimerais en savoir plus d'exemples comme celui-ci.$a^nb^n$$AC^0$

Les langues en peuvent être plus compliquées que ne le suggère l'intuition naïve.$AC^0$

• De toute évidence, contient , qui n'est pas sans contexte.$AC^0$$\{a^n b^n c^n\}$
• Chaque langue unaire est en non uniforme ; par exemple, le problème d'arrêt exprimé en unaire.$AC^0$
• L'addition peut être implémentée dans avec un additionneur d'anticipation. Ici, l'entrée est de bits représentant deux nombres, et la sortie contient fils (de manière équivalente, chaque bit de sortie peut être réalisé en )$AC^0$$2n$$n+1$$AC^0$

• Multiplexage: est en .$\{w x: |w|=2^n, |x|=n, w[x] = 1\}$$AC^0$

  Un multiplexeur est une fonction sur variables qui délivre la valeur de l'une des variables, où l'indice est déterminé par les variables. (Il en va de même si l'index est écrit en unaire.)$2^n+n$$2^n$$n$

• Le calcul des formules 3SAT est en .$AC^0$

  L'entrée se compose de variables, suivies de quelques clauses, chacune contenant trois littéraux, où chaque littéral est un index de la variable (unaire ou binaire, peu importe) et un bit indiquant une éventuelle négation. Vous pouvez évaluer les littéraux avec des multiplexeurs, puis ajouter une couche de blocs opératoires, puis un grand ET en haut.$n$

• $AC^0$ ne contient pas la majorité, mais il contient la majorité approximative: une fonction qui est égale à la majorité si la sortie est zéros ou uns. Voir "Comptage approximatif avec des circuits uniformes à profondeur constante" par Ajtai.$\geq \frac{1}{2}+ \varepsilon$

$AC^0$ est fermé sous opérations logiques, concaténation et composition, vous pouvez donc combiner les exemples ci-dessus. Maintenant, vous devriez ressentir du respect pour et les autres limites inférieures du circuit!$Parity \notin AC^0$