Régulier contre 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}$

Y a-t-il un candidat pour un problème dans qui n'est pas dans ? $\mathsf{Reg}$ $\mathsf{TC^0}$

Y a-t-il un résultat conditionnel impliquant que , par exemple si puis ? $\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
la source

Réponses:

Prenez comme alphabet et Barrington a prouvé dans [2] que est -complet pour la réduction de (et même avec une réduction plus restrictive en fait). $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 particulier, cela montre que les langues régulières ne sont pas dans si . En utilisant la théorie des semi-groupes (voir le livre de Straubing [1] pour plus de détails), nous obtenons que si est strictement en alors tous les langages réguliers sont soit -complet soit . $\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). "Automates finis, logique formelle et complexité des circuits". Progrès en informatique théorique. Bâle: Birkhäuser. p. 8. ISBN 3-7643-3719-2.

[2] Barrington, David A. Mix (1989). «Les programmes de ramification de taille polynomiale à largeur limitée reconnaissent exactement ces langues dans NC1»

CP
la source

De plus, si ACC

n'est pas "strictement dans NC

alors toutes les langues régulières sont" dans ACC

toute façon.

^{0}

$^0$

^{1}

$^1$

^{0}

$^0$

$\;\;\;\;$

Les langues régulières avec des monoides syntaxiques insolubles sont complètes en (en raison de Barrington; c'est la raison sous-jacente du résultat le plus souvent cité selon lequel équivaut à des programmes de branchement uniformes de largeur 5). Ainsi, un tel langage n'est pas en sauf si . $\mathrm{NC}^1$ $\mathrm{NC}^1$ $\mathrm{TC}^0$ $\mathrm{TC}^0=\mathrm{NC}^1$

Mon expression régulière -complète complète est (il s'agit en fait d'un codage de , comme dans la réponse de CP). $\mathrm{NC}^1$ $((a|b)^3(ab^∗a|b))^∗$ $S_5$

Emil Jeřábek soutient Monica
la source

qu'est-ce qu'un monoïde syntaxique?

T ....

Avertissement de confusion terminologique: dans ce contexte, un monoïde est dit sans solution si elle contient un groupe comme sans solution semigroupe , pas nécessairement comme monoïde.

Emil Jeřábek soutient Monica le

Mon expression régulière NC ^ 1-complete préférée est

(c'est en fait un encodage de S_5, comme dans la réponse de CP).

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

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

Emil Jeřábek soutient Monica le

Un autre exemple, moins concis mais plus facile à comprendre:

le 'a' agit comme le cycle (1 2 3 4 5), le " b "agit comme la permutation (1 2), et ces deux éléments de groupe sont connus pour générer

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

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

S - 5

$S-5$

@MichaelCadilhac:

agit comme

, et

comme

. Celles-ci génèrent

car

est une transposition.

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 soutient Monica le