Relacja między

Niech będzie klasą wszystkich zwykłych języków. $\mathsf{REG}$

Znane jest i . Ale czy istnieje jakaś charakterystyka języków w ? $\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
źródło

RL często oznacza klasę problemów możliwych do rozwiązania w losowej przestrzeni logarytmicznej. Czy możesz przejść do innej notacji i / lub zdefiniować ją w treści pytania?

Tsuyoshi Ito,

Zoo używa notacji REG: complexityzoo.uwaterloo.ca/Complexity_Zoo:R#reg

András Salamon

Odpowiedzi:

Poniższy artykuł wydaje się zawierać odpowiedź:

Mieszanka Barrington DA Compton K., Straubing, H. Therien D .: języki regularne w . Journal of Computer and System Sciences 44 (3), 478-499 (1992) ( link ) $\mathsf{NC}^1$

Jedna z uzyskanych tam charakterystyk jest następująca. Klasa zawiera dokładnie te języki, które można uzyskać z , i dla ze skończoną liczbą operacji boolowskich i konkatenacji. Tutaj każdy język $\mathsf{REG} \cap \mathsf{AC}^0 \subset \{0, 1\}^*$ $\{0\}$ $\{1\}$ $\mathsf{LENGTH}(q)$ $q > 1$ zawiera wszystkie ciągi, których długość jest podzielna przez . (Istnieje również charakterystyka logiczna i dwie algebraiczne). $\mathsf{LENGTH}(q)$ $q$

dd1
źródło

Przydałoby się również podsumować odpowiedź tutaj.

Suresh Venkat,

Zrobione, chociaż tak naprawdę nie rozumiem sensu robienia tego w tym konkretnym przypadku.

dd1

Chodzi głównie o to, aby odpowiedź była jak najbardziej samodzielna.

Suresh Venkat

Zauważ, że charakterystyka algebraiczna daje algorytm decydujący, czy dany język regularny należy do

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

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

J.-E.

Zwykłe języki w są „ładnym” podzbiorem zwykłych języków. Mają ładne logiczne i algebraiczne charakterystyki. $AC^0$

Książka „Automaty skończone, logika formalna i złożoność obwodów” autorstwa Straubinga rozważa te pytania.

Na twoje pytanie można odpowiedzieć w następujący sposób.

= = języki rozpoznawane przez quasi-aperiodyczne monoidy. $AC^0 \cap REG$ $FO[<,Suc,\equiv]$

Tutaj jest logiką pierwszego rzędu przy użyciu predykatów liczbowych mniejszych niż, następca i . $FO[<,Suc,\equiv]$ $x \equiv (0 ~mod ~q)$

Inną charakterystykę jak przedstawiono w „języki regularnych ”, to zestaw języków, które mogą być utworzone za pomocą skończony zestaw alfabetu, długość (Q) i zamknięcie go pod kombinacje logiczne i powiązań,. $NC^1$

Sreejith AV
źródło