Beziehung zwischen

Sei die Klasse aller regulären Sprachen. $\mathsf{REG}$

Es sind und . Aber gibt es eine Charakterisierung für Sprachen in ? $\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
quelle

RL bezeichnet oft die Klasse von Problemen, die im randomisierten logarithmischen Raum lösbar sind. Können Sie zu einer anderen Notation wechseln und / oder diese im Hauptteil der Frage definieren?

Tsuyoshi Ito

Der Zoo verwendet die Notation REG: complexityzoo.uwaterloo.ca/Complexity_Zoo:R#reg

András Salamon

Antworten:

Das folgende Papier scheint eine Antwort zu enthalten:

Mischen Sie Barrington, DA, Compton, K., Straubing, H., Therien, D.: Reguläre Sprachen in . Zeitschrift für Computer- und Systemwissenschaften 44 (3), 478-499 (1992) ( link ) $\mathsf{NC}^1$

Eine der dort erhaltenen Charakterisierungen ist wie folgt. Die Klasse enthält genau die Sprachen, die aus , und für mit einer endlichen Anzahl von Booleschen Operationen und Verkettungen. Hier enthält jede Sprache alle Zeichenketten, deren Länge durch teilbar ist . (Es gibt auch eine logische Charakterisierung und zwei algebraische.) $\mathsf{REG} \cap \mathsf{AC}^0 \subset \{0, 1\}^*$ $\{0\}$ $\{1\}$ $\mathsf{LENGTH}(q)$ $q > 1$ $\mathsf{LENGTH}(q)$ $q$

dd1
quelle

Es wäre hilfreich, wenn Sie die Antwort auch hier zusammenfassen könnten.

Suresh Venkat

Fertig, obwohl ich den Sinn dieses Vorgangs in diesem speziellen Fall nicht wirklich verstehe.

dd1

Es geht hauptsächlich darum, die Antwort so weit wie möglich in sich geschlossen zu halten.

Suresh Venkat

Beachten Sie, dass die algebraische Charakterisierung einen Algorithmus liefert, der entscheidet, ob eine bestimmte reguläre Sprache zu gehört oder nicht .

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

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

J.-E.

Die regulären Sprachen in sind eine "nette" Untermenge der regulären Sprachen. Sie haben schöne logische sowie algebraische Charakterisierungen. $AC^0$

Das Buch "Endliche Automaten, Formale Logik und Schaltungskomplexität" von Straubing beschäftigt sich mit diesen Fragen.

Ihre Frage kann wie folgt beantwortet werden.

$AC^0 \cap REG$ = = Sprachen, die von quasi-aperiodischen Monoiden erkannt werden. $FO[<,Suc,\equiv]$

Hier ist eine Logik erster Ordnung, die numerische Prädikate kleiner als, Nachfolger und . $FO[<,Suc,\equiv]$ $x \equiv (0 ~mod ~q)$

Eine andere in "Reguläre Sprachen in " gezeigte Charakterisierung ist die Menge von Sprachen, die unter Verwendung einer endlichen Menge von Alphabeten LENGTH (q) gebildet und unter booleschen Kombinationen und Verkettungen geschlossen werden kann. $NC^1$

Sreejith AV
quelle