Regular versus 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}$ $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$

¿Hay un candidato para un problema en que no está en ? $\mathsf{Reg}$ $\mathsf{TC^0}$

¿Hay un resultado condicional que implique que , por ejemplo, si entonces ? $\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
fuente

Respuestas:

Tome como alfabeto y Barrington demostró en [2] que es -completo para la reducción de (e incluso con una reducción más restrictiva en realidad). $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$

En particular, esto muestra que los idiomas normales no están en si . Al usar la teoría de los semigrupos (consulte el libro de Straubing [1] para obtener más detalles), obtenemos que si está estrictamente en , todos los idiomas regulares son -completo o . $\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). "Autómatas finitos, lógica formal y complejidad del circuito". Progreso en informática teórica. Basilea: Birkhäuser. pag. 8. ISBN 3-7643-3719-2.

[2] Barrington, David A. Mix (1989). "Los programas de ramificación de tamaño polinómico de ancho limitado reconocen exactamente esos idiomas en NC1"

CP
fuente

Además, si ACC

no está "estrictamente en NC

entonces todos los idiomas normales están" en ACC

todos modos.

^{0}

$^0$

^{1}

$^1$

^{0}

$^0$

$\;\;\;\;$

Los lenguajes regulares con monoides sintácticos insolubles son -completo (debido a Barrington; esta es la razón subyacente detrás del resultado más comúnmente citado de que es igual a los programas de ramificación uniforme de ancho-5). Por lo tanto, dicho lenguaje no está en menos que . $\mathrm{NC}^1$ $\mathrm{NC}^1$ $\mathrm{TC}^0$ $\mathrm{TC}^0=\mathrm{NC}^1$

Mi expresión regular completa favorita de es (esto es en realidad una codificación de , como en la respuesta de CP). $\mathrm{NC}^1$ $((a|b)^3(ab^∗a|b))^∗$ $S_5$

Emil Jeřábek apoya a Monica
fuente

¿Qué es un monoide sintáctico?

T ....

Advertencia de terminología confusa: en este contexto, se dice que un monoide es insoluble si contiene un grupo insoluble como un subsemigrupo , no necesariamente como un submonoide.

Emil Jeřábek apoya a Monica el

Mi expresión regular NC ^ 1 completa completa favorita es

(esto es en realidad una codificación de S_5, como en la respuesta de CP).

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

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

Emil Jeřábek apoya a Monica el

Otro ejemplo, menos conciso pero más fácil de entender:

la 'a' actúa como el ciclo (1 2 3 4 5), el " b "actúa como la permutación (1 2), y se sabe que esos dos elementos del grupo generan

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

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

S - 5

$S-5$

@MichaelCadilhac:

actúa como

, y

como

. Estos generan

como

es una transposición.

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 apoya a Monica el