Relation entre

Soit $\mathsf{REG}$ la classe de toutes les langues régulières.

$\mathsf{AC}^0 \not\subset \mathsf{REG}$ $\mathsf{REG} \not\subset \mathsf{AC}^0$ $\mathsf{AC}^0 \cap \mathsf{REG}$

circuit-complexity regular-language Alex Grilo
la source

RL désigne souvent la classe de problèmes pouvant être résolus dans l'espace logarithmique randomisé. Pouvez-vous passer à une autre notation et / ou la définir dans le corps de la question?

Tsuyoshi Ito

Le zoo utilise la notation REG: complexitézoo.uwaterloo.ca

András Salamon

Réponses:

Le document suivant semble contenir une réponse:

Mix Barrington, DA, Compton, K., Straubing, H., Therien, D .: Langues régulières dans $\mathsf{NC}^1$ . Journal of Computer and System Sciences 44 (3), 478-499 (1992) ( lien )

L'une des caractérisations obtenues ici est la suivante. La classe $\mathsf{REG} \cap \mathsf{AC}^0 \subset \{0, 1\}^*$ contient exactement les langues qui peuvent être obtenues à partir de $\{0\}$ , $\{1\}$ et $\mathsf{LENGTH}(q)$ pour $q > 1$ avec un nombre fini d'opérations booléennes et de concaténations. Ici, chaque langue $\mathsf{LENGTH}(q)$ contient toutes les chaînes dont la longueur est divisible par $q$ . (Il existe également une caractérisation logique et deux algébriques.)

dd1
la source

Il serait utile que vous puissiez également résumer la réponse ici.

Suresh Venkat

C'est fait, bien que je ne comprenne pas vraiment l'intérêt de le faire dans ce cas particulier.

dd1

C'est principalement pour garder la réponse aussi autonome que possible.

Suresh Venkat

Notez que la caractérisation algébrique produit un algorithme pour décider si un langage régulier donné appartient ou non à .

R E G \cap {A C}^{0}

$\mathsf{REG} \cap \mathsf{AC}^0$

J.-E.

Les langues régulières à l'intérieur d' sont un "joli" sous-ensemble des langues régulières. Ils ont de belles caractérisations logiques et algébriques. $AC^0$

Le livre "Finite Automata, Formal Logic and Circuit Complexity" de Straubing examine ces questions.

Vous pouvez répondre à votre question comme suit.

$AC^0 \cap REG$ = = langues reconnues par des monoïdes quasi-apériodiques. $FO[<,Suc,\equiv]$

Ici est une logique du premier ordre utilisant moins de, successeur et des prédicats numériques. $FO[<,Suc,\equiv]$ $x \equiv (0 ~mod ~q)$

Une autre caractérisation comme indiqué dans "Langues régulières dans " est l'ensemble des langues qui peuvent être formées en utilisant un ensemble fini d'alphabets, LONGUEUR (q) et en le fermant sous des combinaisons booléennes et des concaténations. $NC^1$

Sreejith AV
la source