Liczba stanów automatów lokalnych

Automat deterministyczny nazywa się k -lokalny dla k > 0, jeżeli dla każdego w ∈ X k zbiór { δ ( q , w ) : q ∈ Q } zawiera co najwyżej jeden element. Intuicyjnie oznacza to, że jeśli słowo w o długości k prowadzi do stanu, to ten stan jest unikalny lub inaczej niż dowolne słowo o długości$\mathcal A = (X, Q, q_0, F, \delta)$$k$$k > 0$$w \in X^k$$\{ \delta(q,w) : q \in Q \}$$w$$k$ ostatnich k symboli określa stan, do którego prowadzi.$> k$$k$

Teraz, jeśli automat jest -lokalny, to nie musi być k ′ -lokalny dla niektórych k ′ < k , ale musi być k ′ -lokalny dla k ′ > k, ponieważ ostatnie symbole jakiegoś słowa | w | > k określ stan, jeśli występuje, w sposób unikalny.$k$$k'$$k' < k$$k'$$k' > k$$|w| > k$

Teraz staram się połączyć liczbę stanów i -localness z automatu. Przypuszczam:$k$

Lemat: Niech będzie k -lokalne, jeśli | Q | < k to automat jest również | Q | -lokalny.$\mathcal A = (X,Q,q_0,F,\delta)$$k$$|Q| < k$$|Q|$

Ale nie udało mi się udowodnić, żadnych sugestii lub pomysłów?

Mam nadzieję, że przez ten lematu do uzyskania czegoś o liczbie stanów automatu, która nie jest -local dla wszystkich k ≤ N danej stałej N > 0 , ale k -local pewnego k > N .$k$$k \le N$$N > 0$$k$$k > N$

Ponieważ mówisz, że powinien mieć najwyżej jeden element, założę, że używasz wersji DFA, gdzie δ może być częściowe. To jest przykład kontrprzykładowy: X = { a , b } , Q = { 0 , 1 , 2 , 3 , 4 } , δ ( q , a ) $T_w:=\{\delta(q,w):q\in Q\}$$\delta$ dla q < 4 i δ ( 1 , b ) = 2 , δ ( 2 , b ) = 3 , δ ( 4 , b ) = 0 . F i q 0 oczywiście nie mają znaczenia dla tego pytania.$X=\{a,b\}, Q=\{0,1,2,3,4\},\delta(q,a)=q+1$$q<4$$\delta(1,b)=2,\delta(2,b)=3,\delta(4,b)=0$$F$$q_0$

Automat jest lokalny, ale nie 5- lokalny, ponieważ T a b a a b = { 0 , 3 } .$6$$5$$T_{abaab} = \{0,3\}$

Edycja: ten kontrprzykład nie działa, zachowam go, aby komentarze miały sens. Ale tak jest.

Weź , z przejściami 0 → 1 ( a ) , 1 → 2 ( a ) , 2 → 3 ( a ) , 2 → 0 ( b ) , 3 → 2 ( b ) . Ten automat to $X=\{a,b\}, Q=\{0,1,2,3\}$$0\to 1(a),1\to 2(a), 2\to 3(a), 2\to 0(b), 3\to 2(b)$$5$-lokalne, ale nie -lokalne: dla a a b a otrzymujemy ścieżki 0 → 1 → 2 → 0 → 1 i 1 → 2 → 3 → 2 → 3 , tj. T a a b a = { 1 , 3 } .$4$$aaba$$0\to 1\to 2\to 0\to 1$$1\to 2\to 3\to 2\to 3$$T_{aaba}=\{1,3\}$

Późna odpowiedź, ale ograniczono opóźnienie synchronizacji dla kilku klas automatów: patrz na przykład Automaty jednoznaczne; Béal i in. MCS'08 .

W szczególności; istnieje rodzina deterministycznych automatów, które mają opóźnienie jak pokazano w: Na granicy opóźnienia synchronizacji lokalnego automatu; Béal i in. TCS'98 , który odpowiada odpowiedniej górnej granicy O ( | Q | 2 ) .$\Omega(|Q|^2)$$O(|Q|^2)$

PS zdefiniowane w pracy opóźnienie synchronizacji jest minimalnym dla którego deterministyczny automat lokalny jest k -lokalny.$k$$k$