Relation entre

20

Soit REG la classe de toutes les langues régulières.

R E G A C 0 A C 0 R E GAC0REGREGAC0AC0REG

Alex Grilo
la source
6
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
5
Le zoo utilise la notation REG: complexitézoo.uwaterloo.ca
András Salamon

Réponses:

24

Le document suivant semble contenir une réponse:

Mix Barrington, DA, Compton, K., Straubing, H., Therien, D .: Langues régulières dans NC1 . Journal of Computer and System Sciences 44 (3), 478-499 (1992) ( lien )

L'une des caractérisations obtenues ici est la suivante. La classe REGAC0{0,1} contient exactement les langues qui peuvent être obtenues à partir de {0} , {1} et LENGTH(q) pour q>1 avec un nombre fini d'opérations booléennes et de concaténations. Ici, chaque langue 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
10
Il serait utile que vous puissiez également résumer la réponse ici.
Suresh Venkat
3
C'est fait, bien que je ne comprenne pas vraiment l'intérêt de le faire dans ce cas particulier.
dd1
7
C'est principalement pour garder la réponse aussi autonome que possible.
Suresh Venkat
1
Notez que la caractérisation algébrique produit un algorithme pour décider si un langage régulier donné appartient ou non à . REGAC0
J.-E.
8

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.AC0

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

Vous pouvez répondre à votre question comme suit.

F O [ < , S u c , ]AC0REG = = langues reconnues par des monoïdes quasi-apériodiques.FO[<,Suc,]

Ici est une logique du premier ordre utilisant moins de, successeur et des prédicats numériques.x ( 0 m o d q )FO[<,Suc,]x(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.NC1

Sreejith AV
la source