Teoretyczne informatyka

4

Jeden z moich projektów Java jest rozwidleniem parboiled i, w przeciwieństwie do powiedzmy Antlr lub JavaCC, parsery są generowane w czasie wykonywania. Generowane gramatyki to gramatyka wyrażeń parsujących lub PEG (słyszę, że innym terminem jest „packrat”). Podczas gdy generowanie środowiska wykonawczego zwiększa złożoność (generowanie kodu bajtowego), inny aspekt dotyczy samej …

9 research-practice books parsing

2

Zrozumienie graficznego mniejszego twierdzenia

To pytanie jest dwojakie i dotyczy głównie odniesienia: Czy jest gdzieś, gdzie podane są główne intuicje dowodzenia niewielkiego twierdzenia o grafie, bez zbytniego zagłębiania się w szczegóły? Wiem, że dowód jest długi i trudny, ale z pewnością muszą istnieć kluczowe pomysły, które można przekazać w łatwiejszy sposób. Czy istnieją inne …

9 reference-request graph-theory graph-minor

1

Algorytm przecięcia DFA dla szczególnych przypadków

Interesują mnie wydajne algorytmy przecięcia DFA w szczególnych przypadkach. Mianowicie, gdy DFA przecinają się, zachowują określoną strukturę i / lub działają na ograniczonym alfabecie. Czy jest jakieś źródło, w którym mogę znaleźć algorytmy takich przypadków? Aby pytanie nie było zbyt szerokie, szczególnie interesująca jest następująca struktura: wszystkie przecinające się DFA …

9 automata-theory time-complexity dfa

1

Równość rozstrzygalnych dowodów?

Chcę wiedzieć, czy rozstrzygalność o równości dwóch rozstrzygalnych dowodów tej samej twierdzenia można udowodnić bez żadnych dodatkowych aksjomatów w rachunku konstrukcji indukcyjnych. W szczególności chcę wiedzieć, czy to prawda bez żadnych dodatkowych aksjomatów w Coq. ∀ P.: Prop , P∨ ¬ P⇒ ( ∀p1: P, ∀p2): P, {p1=p2)} ∨ {p1≠p2)} …

9 coq constructive-mathematics calculus-of-constructions

1

Dopasowanie masy „sprawiedliwe”

Interesuje mnie wariant maksymalnego dopasowania wagi na wykresie, który nazywam „maksymalnym uczciwym dopasowaniem”. Załóżmy, że wykres jest pełny (tj E=V×VE=V×VE=V\times V) Ma liczbę nawet wierzchołków, a masa jest podawana przez funkcję zysk . Biorąc pod uwagę pasujące , oznacz przez zysk krawędzi jest dopasowany.p:(V2)→Np:(V2)→Np:{V\choose 2}\to \mathbb NMMMM(v)M(v)M(v)vvv Pasujące jest sprawiedliwym …

9 ds.algorithms graph-algorithms np-hardness matching bipartite-graphs

2

Wyliczanie płaskich wykresów ograniczonej szerokości poprzecznej

Szukam odniesień do następującego problemu: biorąc pod uwagę liczby całkowite i , wyliczyć wszystkie nieizomorficzne wykresy płaskie na wierzchołkach i szerokości linii . Interesują mnie zarówno wyniki teoretyczne, jak i praktyczne, ale przede wszystkim praktyczne algorytmy, które można kodować i uruchamiać dla możliwie dużych wartości i (pomyśl i ). Jeśli …

9 reference-request graph-theory graph-algorithms treewidth

2

Teoretyczne wyniki dla losowych lasów?

Losowe lasy mają wśród praktyków reputację jednych z najbardziej skutecznych technik klasyfikacji. Jednak nie spotykamy ich zbyt wiele w literaturze teoretycznej, z której, jak sądzę, brak głębokich wyników teoretycznych. Gdyby ktoś chciał zagłębić się w tę teorię, od czego by to się zaczęło?

9 machine-learning lg.learning

1

Czy złożoność Kołmogorowa jest funkcją przypuszczającą?

Naprawmy kodowanie maszyn Turinga i uniwersalnej maszyny Turinga U, która na wejściu (T, x) wypisuje dowolne T na wejściu x (być może oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla x, K (x), jako długość najkrótszego programu, p, tak aby U (p) = x. Czy istnieje takie N, że dla wszystkich …

9 cc.complexity-theory universal-computation kolmogorov-complexity universal-turing-machines

1

Gdzie badana jest parametryczna relacja w modelach hiperdoktryny lub toposu?

Reynolds pierwotnie zaproponował semantykę relacyjną dla polimorficznego rachunku lambda drugiego rzędu [1]. Później jednak wykazał [2], że to podejście było niespójne z klasyczną teorią zbiorów. Pitts opisał ramy modeli hiperdoktryn i modeli topos [3], które są spójne z logiką konstruktywną. Następnie opracowano przypuszczalnie relacyjne modele hiperdoktryny i toposu. Gdzie mogę …

9 type-theory parametricity

2

Dlaczego większość kryptografii zależy od dużych par liczb pierwszych, a nie innych problemów?

Większość obecnych metod kryptograficznych zależy od trudności faktorowania liczb, które są iloczynem dwóch dużych liczb pierwszych. Jak rozumiem, jest to trudne tylko tak długo, jak długo metoda zastosowana do wygenerowania dużych liczb pierwszych nie może być użyta jako skrót do faktoryzacji wynikowej liczby złożonej (a samo faktoring dużych liczb jest …

9 cr.crypto-security primes

1

Zgodność pierwszego rzędu bez modeli skończonych

Wiemy z twierdzenia Kościoła, że określenie satysfakcji pierwszego rzędu jest ogólnie nierozstrzygalne, ale istnieje kilka technik, które można zastosować do ustalenia satysfakcji pierwszego rzędu. Najbardziej oczywiste jest poszukiwanie modelu skończonego. Istnieje jednak szereg instrukcji w logice pierwszego rzędu, które możemy wykazać, że nie mają modeli skończonych. Na przykład każda dziedzina, …

9 reference-request lo.logic automated-theorem-proving

1

Randomizowane testy tożsamości dla wielomianów wysokiego stopnia?

Niech będzie wielomianem zmiennym podanym jako obwód arytmetyczny o rozmiarze poli i niech będzie liczbą pierwszą.faffnnn(n)(n)(n)p=2)Ω(n)p=2Ω(n)p = 2^{\Omega(n)} Czy możesz sprawdzić, czy jest identycznie zerowe w stosunku do , z czasem i prawdopodobieństwem błędu , nawet jeśli stopień nie jest a priori ograniczone? Co jeśli jest jednoznaczny?faffZpZp\mathbb{Z}_ppoli(n)poly(n)\mbox{poly}(n)≤1-1/poli(n)≤1−1/poly(n)\leq 1-1/\mbox{poly}(n)faff Zauważ, że …

9 polynomials arithmetic-circuits

1

Problem członkostwa dla niektórych klas gramatyki nieograniczonej

Rozważ dowolną bezkontekstową gramatykę nad alfabetem . Do produkcji tej gramatyki dodaj dwie stałe produkcje bezkontekstowe : i \ overline {1} 1 \ rightarrow \ epsilon . Nazwij wynikową gramatykę G ^ P oznaczającą „ G uzupełniony o produkcje P ”.solGG{ 0 , 1 ,0¯¯¯,1¯¯¯}{0,1,0¯,1¯}\lbrace 0,1,\overline{0} ,\overline{1} \rbraceP.PP0¯¯¯0 → ϵ0¯0→ϵ\overline{0} …

9 context-free decidability

1

Czysto teoretyczne objaśnienie redukcji z Unique Label Cover do Max-Cut

Studiuję Unique Games Conjecture i słynną redukcję do Max-Cut Khota i in. Ze swojej pracy i innych stron internetowych większość autorów używa (jak dla mnie) niejawnej równoważności między redukcją MAX-CUT a budowaniem konkretnych testów dla długich kodów. Z powodu mojego braku jasności co do tej równoważności staram się podążać tym …

9 cc.complexity-theory approximation-hardness pcp max-cut unique-games-conjecture

2

Wykres izomorfizm z relacją równoważności na zbiorze wierzchołków

Kolorowy wykres można opisać jako krotkę (G,c)(G,c)(G,c)gdzie jest wykresem, a jest kolorem. Mówi się, że dwa kolorowe wykresy i są izomorficzne, jeśli istnieje izomorfizm prawy tak, że przestrzegane jest zabarwienie, tj. dla wszystkich .GGGc:V(G)→Nc:V(G)→Nc : V(G) \rightarrow \mathbb{N}(G,c)(G,c)(G,c)(H,d)(H,d)(H,d)π:V(G)→V(H)π:V(G)→V(H)\pi : V(G) \rightarrow V(H)c(v)=d(π(v))c(v)=d(π(v))c(v) = d(\pi(v))v∈V(G)v∈V(G)v \in V(G) Pojęcie to oddaje izomorfizm …

9 terminology graph-isomorphism equivalence