Regular gegen TC0

$\mathsf{Reg} \subseteq \mathsf{NC^1}$ $\mathsf{Reg}$ $\mathsf{TC^0} \not\subseteq \mathsf{Reg}$ $\mathsf{Reg} \subseteq \mathsf{TC^0}$ $\mathsf{NC^1}\not\subseteq\mathsf{TC^0}$ nicht kennen, kennen wir auch . $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$

Gibt es einen Kandidaten für ein Problem in $\mathsf{Reg}$ , das sich nicht in ? $\mathsf{TC^0}$

Gibt es ein bedingtes Ergebnis, das impliziert, dass , z. B. wenn dann ? $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$ $\mathsf{NC^1} \not\subseteq \mathsf{TC^0}$ $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$

cc.complexity-theory fl.formal-languages automata-theory circuit-complexity regular-language Kaveh
quelle

Antworten:

Nehmen als Alphabet und Barrington erwies sich in [2] , dass ist -komplett für -Reduktion (und sogar tatsächlich mit einer restriktiveren Reduktion). $S_5$

L = {σ_{1} \dots σ_{n} \in S_{5}^{*} ∣ σ_{1} \circ \dots \circ σ_{n} = Id}

$L= \{ \sigma_1\cdots \sigma_n \in S_5^*\mid \sigma_1\circ\cdots\circ\sigma_n = \text{Id}\}$

L

$L$

{NC}^{1}

$\textrm{NC}^1$

{AC}^{0}

$\textrm{AC}^0$

Dies zeigt insbesondere, dass reguläre Sprachen nicht in wenn . Durch Anwendung der Halbgruppentheorie (siehe das Buch von Straubing [1] für weitere Einzelheiten) erhalten wir, dass, wenn ausschließlich in ist, alle regulären Sprachen entweder -complete oder $\textrm{TC}^0$ $\textrm{TC}^0 \subsetneq \textrm{NC}^1$ $\textrm{ACC}^0$ $\textrm{NC}^1$ $\textrm{NC}^1$ $\textrm{ACC}^0$ .

[1] Straubing, Howard (1994). "Endliche Automaten, formale Logik und Schaltungskomplexität". Fortschritte in der theoretischen Informatik. Basel: Birkhäuser. p. 8. ISBN 3-7643-3719-2.

[2] Barrington, David A. Mix (1989). Verzweigungsprogramme mit begrenzter Breite und Polynomgröße erkennen genau diese Sprachen in NC1

CP
quelle

Außerdem, wenn ACC

ist nicht „streng in NC

dann alle regulären Sprachen sind“ in ACC

sowieso.

^{0}

$^0$

^{1}

$^1$

^{0}

$^0$

$\;\;\;\;$

Reguläre Sprachen mit unlösbaren syntaktischen Monoiden sind -vollständig (aufgrund von Barrington; dies ist der Grund für das häufiger zitierte Ergebnis, dass gleich einheitlichen Verzweigungsprogrammen der Breite 5 ist). Somit ist eine solche Sprache nicht in sei denn, . $\mathrm{NC}^1$ $\mathrm{NC}^1$ $\mathrm{TC}^0$ $\mathrm{TC}^0=\mathrm{NC}^1$

Mein bevorzugter -kompletter regulärer Ausdruck ist (dies ist tatsächlich eine Codierung von , wie in der Antwort von CP). $\mathrm{NC}^1$ $((a|b)^3(ab^∗a|b))^∗$ $S_5$

Emil Jeřábek unterstützt Monica
quelle

Was ist ein syntaktisches Monoid?

T ....

Warnung vor verwirrender Terminologie: In diesem Zusammenhang wird ein Monoid als unlösbar bezeichnet, wenn es eine unlösbare Gruppe als Untergruppe enthält , nicht unbedingt als Submonoid.

Emil Jeřábek unterstützt Monica am

Mein bevorzugter NC ^ 1-vollständiger regulärer Ausdruck ist

(dies ist tatsächlich eine Kodierung von S_5, wie in der Antwort von CP).

((a | b)^{3} (a b^{*} a | b))^{*}

$((a|b)^3(ab^*a|b))^*$

Emil Jeřábek unterstützt Monica am

Ein weiteres Beispiel, weniger präzise , aber leichter zu verstehen:

das 'a' wirkt als den Zyklus (1 2 3 4 5), die " b "fungiert als Permutation (1 2), und es ist bekannt, dass diese beiden Gruppenelemente

erzeugen .

((a + b) (a b^{*} a b^{*} a b^{*} a + b))^{*}

$((a+b)(ab^*ab^*ab^*a+b))^*$

S - 5

$S-5$

@MichaelCadilhac:

fungiert als

und

als

. Diese erzeugen

als

eine Transposition ist.

a

$a$

(1, 2, 3, 4, 5)

$(1,2,3,4,5)$

b

$b$

(1, 2, 3, 4)

$(1,2,3,4)$

S_{5}

$S_5$

b a^{- 1}

$ba^{-1}$

Emil Jeřábek unterstützt Monica am