Języki rozpoznawane przez DFA wielkości wielomianowej

W przypadku ustalonego skończonego alfabetu język formalny ponad jest regularny, jeśli istnieje deterministyczny automat skończony (DFA) ponad $\Sigma$ $L$ $\Sigma$ $\Sigma$ który akceptuje dokładnie . $L$

Interesują mnie języki, które są „prawie” regularne w tym sensie, że mogą być rozpoznawane przez rodziny automatów wielkości, które rosną tylko wielomianowo wraz z długością słowa.

Formalnie powiem, że język formalny jest rozpoznawany przez rodzinę DFA jeśli dla każdego słowa , pozwalając , jest w iff akceptuje (bez względu na to, czy inne akceptują to, czy nie), i pozwól mi zdefiniować p-regularne języki jako języki rozpoznawane przez obliczaną przez PTIME rodzinę DFA $L$ $(A_n)$ $w \in \Sigma^*$ $n = |w|$ $w$ $L$ $A_n$ $w$ $A_i$ $(A_n)$ wielkości wielomianowej, a mianowicie istnieje wielomian taki, że dla wszystkich . (Ta nazwa, „p-regular”, jest czymś, co wymyśliłam, moim pytaniem jest wiedzieć, czy istnieje już inna nazwa dla tego. Pamiętaj, że to jest $P$ $|A_n| \leq P(n)$ $n$ nie to samo, co p-regularne języki w sensie automatów permutacyjnych .)

Ta klasa języków p-regular obejmuje oczywiście języki zwykłe (po prostu weź dla wszystkich , gdzie jest pewnym DFA rozpoznającym język regularny); ale jest to ścisły nadzór: na przykład dobrze wiadomo, że jest pozbawiony kontekstu, ale nie jest regularny, ale jest p-regularny ( musi tylko policzyć wystąpienia oraz wystąpienia ). Ponieważ jednak wymagam, aby automaty były wielowymiarowymi DFA $A_n = A$ $n$ $A$ $\{a^n b^n \mid n \in \mathbb{N}\}$ $A_n$ $n$ $a$ $n$ $b$ , niektóre języki formalne (właściwie niektóre języki bezkontekstowe) nie są p-regularne: na przykład język palindromów nie jest p-regularny, ponieważ intuicyjnie, po przeczytaniu pierwszej połowy słowa, musisz mieć tyle różnych stanów, ile jest możliwych słów, ponieważ musisz dokładnie dopasować tę pierwszą połowę do drugiej.

Tak więc klasa p-regularnych języków jest ścisłym nadzorem zwykłych języków, nieporównywalnym z językami bezkontekstowymi. W rzeczywistości wydaje się, że można nawet uzyskać hierarchię języków, rozróżniając języki p-regularne w oparciu o najmniejszy stopień wielomianu dla którego są one $P$ $P$ nieregularne. Nietrudno jest skonstruować przykłady pokazujące, że hierarchia ta jest ścisła; chociaż nie rozumiem jeszcze dobrze interakcji między tym a alternatywną definicją hierarchii, która również ograniczyłaby złożoność obliczania . $A_n$

Moje pytanie brzmi: czy ta klasa, którą nazywam p-regular, i powiązana z nią hierarchia, była wcześniej badana? Jeśli tak, gdzie i pod jaką nazwą?

(Możliwy link dotyczy algorytmu terenowego lub strumieniowego lub algorytmów online. W terminologii algorytmów strumieniowych dla problemów z rozpoznawaniem języka interesuje mnie klasa (lub hierarchia) języków, które mogą mieć deterministyczne, jednoprzebiegowe algorytmy rozpoznawania, używając wielomianowej liczby stanów (czyli logarytmicznej wielkości pamięci), ale nie znalazłem definicji tej klasy w tym artykule ani w powiązanych artykułach. Zauważ jednak, że w moim sformułowaniu problemu długość słowa jest znana z góry , co jest mniej naturalne w kontekście transmisji strumieniowej: w transmisji strumieniowej można to zobaczyć jako nieskończony automat, specjalny symbol „końca słowa” i ograniczenie, że liczba stanów osiągalnych po odczytaniu znaków jest wielomianowa w $n$ $n$ . Myślę, że to rozróżnienie robi różnicę, możliwy przykład: język słów binarnych, których wartość jest podzielna przez ich długość, co jest łatwe dla stałej długości, ale (przypuszczam) nie może być reprezentowane przez nieskończony automat w poprzednim znaczeniu, ponieważ nie ma identyfikacji można wykonać, jeśli długość nie jest wcześniej znana.)

(Motywacją dla tej klasy p-regular jest to, że niektóre problemy, takie jak prawdopodobieństwo członkostwa w języku dla słów probabilistycznych, wydają się być PTIME nie tylko, gdy język jest regularny, ale także, gdy jest on regularny, i próbuję aby dokładnie scharakteryzować, w jakich okolicznościach problemy te są możliwe do rozwiązania).

— a3nm
źródło

Argh, nie zastanawiałem się dobrze nad zagadnieniem obliczalności

. Dzięki za zwrócenie na to uwagi. Właśnie dodałem wymóg, że są one obliczalne. Mamy nadzieję, że nie ma złych sytuacji z p-regularnymi językami, które muszą zatrudniać rodziny obliczalne, ale o dużej złożoności

(A_{n})

$(A_n)$

(A_{n})

$(A_n)$

— a3nm

Ok, usunąłem komentarz „nieobliczalny”. Ale nawet z ograniczeniem obliczalnym nadal można uzyskać dziwne rzeczy, takie jak: wybierz

jest NEXP-zupełny (

przeciwnym razie). Być może możesz to jeszcze bardziej ograniczyć, dodając ograniczenie, że

musi być obliczalne w czasie wielomianowym?!?

A_{n} = {1^{n} ∣ n \in B}

$A_n = \{ 1^n \mid n \in B \}$

B

$B$

A_{n} = \emptyset

$A_n = \emptyset$

A_{n}

$A_n$

— Marzio De Biasi

Marzio: Argh, masz rację. Dla mojej motywacji właściwym pojęciem jest to, że

są obliczalne przez PTIME, tak, więc zmieniłem to na ... nadal trochę mnie to niepokoi, że złożoność obliczania

ma taki wpływ na wynikowa klasa (ponieważ oznacza to, że jest to dodatkowy wybór, którego należy dokonać w definicji ...). To także komplikuje obraz hierarchii, o której myślałem.

A_{n}

$A_n$

(A_{n})

$(A_n)$

— a3nm

Nie rozumiem, co jest nie tak z niepoliczalnością, to, co definiujesz, jest niejednorodną klasą języka, jak wiele klas obwodów.

— domotorp

Jeśli wzmocnisz warunek jednorodności w obszarze dziennika, wówczas wszystkie takie języki będą obliczalne w obszarze dziennika. Zgodnie z podaną definicją wszystkie języki P-regular są w „P-mundurze L” (rozpoznawalnym przez rodzinę programów rozgałęziających w P-mundurze lub przez logspace TM z poradą obliczalną dla ptime).

— Emil Jeřábek wspiera Monikę

wydaje się, że nie zbadano zbyt wiele pytania (jedną z możliwości jest próba znalezienia związku z „pobliską” klasą złożoności, np. P / poli itp.); chociaż tutaj jest co najmniej jeden odnośnik, który go dotyczy:

Operacje językowe z wyrażeniami regularnymi o wielkości wielomianowej Gruber / Holzer

Praca dotyczy pytań dotyczących tego, w jakim stopniu operacje językowe zachowujące prawidłowość wpływają na złożoność opisową wyrażeń regularnych. Zidentyfikowano niektóre operacje językowe, które są wykonalne dla wyrażeń regularnych w tym sensie, że wynik operacji może być reprezentowany jako wyrażenie regularne wielomianowe wielkości w operandach. Udowadniamy, że przyjmowanie ilorazów językowych, w szczególności zamknięć prefiksów i sufiksów, w regularnym zestawie może spowodować co najwyżej kwadratowe powiększenie wymaganej wielkości wyrażenia. Operacja przesunięcia kołowego może spowodować jedynie sześcienny wzrost wielkości, a co najmniej kwadratowy wzdęcie może być konieczne w najgorszym przypadku.

jak sugeruje AS, mogą istnieć inne, bardziej naturalne sposoby badania czegoś takiego jak postawione pytanie. tutaj jest inny nieco podobny sposób badania wzrostu zwykłego języka na podstawie liczby słów o rozmiarze które mają luźny związek z pytaniem, np. $n$

Znajdowanie tempa wzrostu języka regularnego lub bezkontekstowego w czasie wielomianowym (Gawrychowski, Krieger, Rampersad, Shallit)

Biorąc pod uwagę bezkontekstowy język L, możemy przetestować, czy jest on wzrostem wielomianowym czy wykładniczym w czasie wielomianowym. Co więcej, jeśli jest to wzrost wielomianowy, możemy również znaleźć dokładną kolejność tego wielomianu w czasie wielomianowym.

— vzn
źródło

Chociaż nie jest to wyraźnie stwierdzone, dowód głównego wyniku poniższej pracy sugeruje, że klasa języków regularnych p nie jest zawarta w monotonnym NC ^ 1. H. Gruber i J. Johannsen: „Optymalne dolne granice wielkości wyrażeń regularnych przy użyciu złożoności komunikacyjnej”, FoSSaCS 2008, LNCS 4962, s. 273–286. hermann-gruber.com/data/fossacs08.pdf

— Hermann Gruber

addendum, omówiono tę rozprawę doktorską 2010 Klasy złożoności automatów skończonych / Kralovic, które definiują coś podobnego do tego, o co prosi się o „małe języki” p11. wydaje się, że jest to wszechstronne badanie tego ogólnego obszaru i buduje ogólne ramy teoretyczne / abstrakcje powiązanych pojęć. nie widzą jednak wielu twierdzeń odnoszących się bezpośrednio do konkretnej klasy „rodzin DFA wielkości P”.

— vzn

@vzn: Definicja w str. 11 pracy Kralovica jest nieco inna, ponieważ dotyczy rodzin językowych, podczas gdy w moim pytaniu różne języki są słowami o stałej długości zaczerpniętymi tylko z jednego głównego języka. Nie jestem pewien, czy którykolwiek związek z papierem Gruber i Holzer, który podajesz, nie widzę, jak w moim pytaniu można by pomyśleć, że automaty są wynikiem operacji zachowujących prawidłowość w ogóle. Jeśli chodzi o Gawrychowski i in., Zgadzam się, że może to być stycznie związane.

— a3nm

wydaje się, że odniesienie Gruber / Holzer pomaga w pomiarze redukcji P-regular wrt właściwości typu „P-regular closure”. Zgadzam się, że twoja def wydaje się inna niż cokolwiek innego. innymi słowy, istnieje przypuszczalnie redukcja między niektórymi z tych problemów / klas a referencje idą w tych kierunkach i można szukać operacji podobnych do redukcji, które łączą twoją def z poprzednio studiowanymi / opublikowanymi klasami (uzgodnione, że defn nie oznacza żadnego konkretnego operacje redukcji). Może ścisła odpowiedź na Twoje pytanie brzmi „nie twoja klasa nie badano dokładnie”

— vzn