Automaty Büchi ze strategią akceptacji

Problem

Niech jest automatem Biichi rozpoznawania języka . Zakładamy, że ma strategię odbioru w następującym sensie: jest funkcja , które mogą być używane do tras pilotażowych . Formalizujemy to, spełniając następujące warunki: $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ $L\subseteq\Sigma^\omega$ $A$ $\sigma:\Sigma^*\to Q$ $A$

$\sigma(\epsilon)=q_0$
dla wszystkich $u\in\Sigma^*$ i $a\in\Sigma$ , $(\sigma(u),a,\sigma(ua))\in\Delta$
dla wszystkich $w=a_0a_1a_2\dots\in L$ , przebieg pilotowany przez $\sigma$ jest akceptowany, tj. sekwencja $\sigma(\epsilon),\sigma(a_0),\sigma(a_0a_1),\sigma(a_0a_1a_2),\dots$ ma nieskończenie wiele elementów $F$ .

Aby spełnić warunki, $A$ może zaakceptować dowolne słowo w swoim języku bez konieczności zgadywania o przyszłości.

Czy przy tych założeniach dotyczących prawdą jest, że można określić tylko poprzez usunięcie przejść? Innymi słowy, czy zawsze możemy wybrać następne przejście w zależności tylko od aktualnego stanu i litery? Czy jest jakieś odniesienie na ten temat? To samo pytanie można następnie zadać na automatach co-Büchi, a bardziej ogólnie na automatach parzystości. $A$ $A$

Co jest znane

Oto niektóre częściowe wyniki.

Po pierwsze, możemy ograniczyć do niedeterministycznych wyborów między stanami mającymi tę samą resztę. Rzeczywiście, jeśli jest językiem przyjmowane od , strategia akceptacji może nie wybrać nad w pewnym momencie, jeśli istnieje . $\sigma$ $L(q)$ $q$ $q_1$ $q_2$ $w\in L(q_2)\setminus L(q_1)$

Zauważ, że pozostałe wybory mają znaczenie, więc pomimo intuicji nie wystarczy to, aby pozbyć się niedeterminizmu. Jest tak, ponieważ możliwe jest pozostanie ad infinitum w dobrej reszcie (tj. Reszta słowa jest w reszcie), ale odrzucenie słowa, ponieważ nieskończenie wiele stanów Büchi jest widoczne. Jest to główna trudność problemu: nieskończony bieg może być zły, bez popełniania w dowolnym momencie fatalnego błędu.

Po drugie, problem jest rozwiązany, gdy , czyli wszystkie słowa są akceptowane przez . W tym przypadku możemy postrzegać jako grę Büchi, w której Gracz I wybiera litery wejściowe, a Gracz II wybiera przejścia. Następnie możemy użyć determinacji pozycyjnej gier Büchi, aby wyodrębnić strategię pozycyjną dla Gracza II. Argumenty te działają nawet w bardziej ogólnym przypadku automatów parzystości. Trudność tego problemu wynika z faktu, że niektórych słów nie ma w , aw tym przypadku strategia może mieć dowolne zachowanie. $L=\Sigma^\omega$ $A$ $A$ $L$ $\sigma$

Po trzecie, o to dowód, że zgodnie z założeniami, język jest w klasie deterministycznych języków BUCHI świadkiem przez automat z państwami . Zauważ, że oznacza to, że nie może być żadnym językiem nieregularnym , na przykład jeśli , nie może istnieć strategia spełniająca warunki. $L$ $2^Q$ $L$ $\omega$ $L=(a+b)^*a^\omega$ $\sigma$

Zaczynamy od ograniczenia przejść zgodnie z pierwszą uwagą: jedyne opcje, jakie możemy podjąć, nie wpływają na pozostały język. Bierzemy tylko następców z maksymalną resztkową wartością, muszą istnieć, ponieważ istnieje . $\sigma$

Następnie budować w następujący sposób. jest automatem podzestawu , ale za każdym razem, gdy w składniku pojawia się stan Büchi , wszystkie inne stany można usunąć z komponentu, i zaczynamy od singletonu . Następnie możemy ustawić $A'=\langle \Sigma, 2^Q, \{ q_0\},F',\Delta'\rangle$ $A'$ $A$ $q$ $\{ q\}$ $F'=\{\{ q\} : q\in F\}$ . Możemy sprawdzić, jest deterministyczny automat büchiego dla . $A'$ $L$

Wreszcie, łącząc uwagi drugie i trzecie, zawsze możemy uzyskać skończoną strategię pamięci , stosując strategię pozycyjną dla Gracza II w grze której Gracz I wybiera litery, Gracz II wybiera przejścia w i wygrywa, jeśli zaakceptuje, gdy zaakceptuje. $\sigma$ $A\times A'$ $A$ $A$ $A'$

— Denis
źródło

Napisz

dla (deterministycznego) automatu z usuniętymi przejściami. Niech

być słowo w

. Zatem według twoich warunków

jest

i akceptuje, a zatem

. I odwrotnie, każdy akceptujący przebieg

jest w szczególności akceptującym przebiegiem

, a zatem

A_{σ}

$A_\sigma$

w = w_{0} w_{1} \dots

$w=w_0w_1\cdots$

L

$L$

σ (w_{0}) σ (w_{0} w_{1}) \dots

$\sigma(w_0)\sigma(w_0w_1)\cdots$

A_{σ}

$A_\sigma$

L \subseteq L (A_{σ})

$L\subseteq L(A_\sigma)$

A_{σ}

$A_\sigma$

A

$A$

L (A_{σ}) \subseteq L

$L(A_\sigma)\subseteq L$

— Sylvain,

@Sylvain: Które przejścia są usuwane?

— Dave Clarke

Zakładam, że nazywasz

automatem

ograniczonym do przejść używanych w strategii

. Problem polega na tym, że nie masz żadnej gwarancji, że

jest deterministyczne. Załóżmy na przykład, że

, to

nie jest deterministyczne.

A_{σ}

$A_\sigma$

A

$A$

σ

$\sigma$

A_{σ}

$A_\sigma$

σ (a) = σ (ϵ) = q_{0}

$\sigma(a)=\sigma(\epsilon)=q_0$

σ (a a) = q_{1}

$\sigma(aa)=q_1$

A_{σ}

$A_\sigma$

— Denis

Zamieszczam go również na stronie mathOverflow, z dodatkowymi szczegółami na temat poprzedniej pracy tutaj: mathoverflow.net/questions/97007/… , czy to w porządku?

— Denis

Zasadniczo delegowanie krzyżowe jest niedozwolone, chyba że nie otrzymano odpowiedzi po upływie odpowiedniego czasu. Biorąc pod uwagę, że na to pytanie jest otwarta nagroda, poczekam kilka dni. Możesz usunąć drugi wpis i otworzyć go za kilka dni. (Również drugi post powinien zawierać link do tego.)

— Dave Clarke

Okazuje się, że odpowiedź brzmi nie, w tym artykule można znaleźć kilka kontrprzykładów .

— Denis
źródło

dzięki za aktualizację, ale niejasne! jaki zespół czy oni opublikowali? planować? jak słyszałeś jak to znaleźli? czy jest powód, dla którego go szukali? czy jest to teoretyczna ciekawość, czy wiąże się z jakimś większym problemem lub aplikacją? etc

— vzn

zobacz tę odpowiedź, aby uzyskać więcej informacji: cstheory.stackexchange.com/a/24918/8953

— Denis

-1

As you pointed out, non-deterministic and deterministic Buchi automata accept different languages. The most famous 'determinization' for a Buchi automaton is given by Safra (search "Safra's construction" on web. Here's one document that comes up: www.cs.cornell.edu/courses/cs686/2003sp/Handouts/safra.pdf). The procedure is quite intricate and involves transforming given Buchi automaton into a deterministic Rabin automaton (having 'accepting' F states and 'rejecting' G states: \sigma has only finitely many states in G). Safra's construction involves much more than simply removing transitions and/or usual subset construction.

— Sudeep
źródło

Wiem o tym, pytanie dotyczy specjalnej klasy automatów Büchi, a mianowicie tej, która dopuszcza strategie akceptacji

σ

$\sigma$ . Pokazałem już, że ta klasa ma taką samą moc, jak klasa deterministycznych automatów Büchi, i opisałem uproszczoną procedurę wyznaczania (w części „co wiadomo”). Przypuszcza się, że dla tej klasy istnieje znacznie prostsza procedura wyznaczania, która polega na usunięciu niektórych przejść.

— Denis