Jumlah status automata lokal

Otomat deterministik disebut k- lokal untuk k > 0 jika untuk setiap w ∈ X k himpunan { δ ( q , w ) : q ∈ Q } berisi paling banyak satu elemen. Secara intuitif itu berarti jika kata w dengan panjang k mengarah ke keadaan, maka keadaan ini unik, atau dikatakan berbeda dari kata panjang yang sewenang-wenang.$\mathcal A = (X, Q, q_0, F, \delta)$$k$$k > 0$$w \in X^k$$\{ \delta(q,w) : q \in Q \}$$w$$k$ simbol k terakhirmenentukan status yang dipimpinnya.$> k$$k$

Sekarang jika sebuah automaton adalah -lokal, maka itu tidak perlu k ′ -lokal untuk beberapa k ′ < k , tetapi harus k ′ -lokal untuk k ′ > k menyebabkan simbol terakhir dari beberapa kata | w | > k menentukan negara, jika ada, secara unik.$k$$k'$$k' < k$$k'$$k' > k$$|w| > k$

Sekarang saya mencoba menghubungkan jumlah status dan -localness dari sebuah otomat. Saya menduga:$k$

Lemma: Misalkan menjadi k- lokal, jika | Q | < k maka automatonnya juga | Q | -lokal.$\mathcal A = (X,Q,q_0,F,\delta)$$k$$|Q| < k$$|Q|$

Tapi saya gagal membuktikan, ada saran atau ide?

Saya berharap dengan Lemma ini untuk sesuatu Turunkan tentang jumlah negara bagian robot yang tidak -local untuk semua k ≤ N diberikan tetap N > 0 , tapi k -local untuk beberapa k > N .$k$$k \le N$$N > 0$$k$$k > N$

Karena Anda mengatakan bahwa harus memiliki paling banyak satu elemen, saya akan berasumsi bahwa Anda menggunakan versi DFA mana δ bisa parsial. Maka ini adalah contoh tandingan: X = { a , b } , Q = { 0 , 1 , 2 , 3 , 4 } , δ ( q , a ) $T_w:=\{\delta(q,w):q\in Q\}$$\delta$ untuk q < 4 , dan δ ( 1 , b ) = 2 , δ ( 2 , b ) = 3 , δ ( 4 , b ) = 0 . F dan q 0 jelas tidak masalah untuk pertanyaan ini.$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$

Otomatnya adalah lokal, tetapi tidak 5- lokal, karena T a b a a b = { 0 , 3 } .$6$$5$$T_{abaab} = \{0,3\}$

Sunting: contoh tandingan ini tidak berfungsi, saya akan menyimpannya agar komentar masuk akal. Namun, berikut ini tidak.

Ambil , dengan transisi 0 → 1 ( a ) , 1 → 2 ( a ) , 2 → 3 ( a ) , 2 → 0 ( b ) , 3 → 2 ( b ) . Otomat ini adalah $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$-local, tetapi tidak -local: untuk a a b a , kita mendapatkan jalur 0 → 1 → 2 → 0 → 1 dan 1 → 2 → 3 → 2 → 3 , yaitu 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\}$

Sebuah jawaban terlambat, tetapi terikat pada penundaan sinkronisasi telah dipelajari untuk beberapa kelas automata: lihat misalnya Automata Unambiguous; Béal et al. MCS'08 .

Khususnya; ada keluarga automata deterministik yang memiliki keterlambatan seperti yang ditunjukkan dalam On the Bound of the Synchronization Delay of the Local Automaton; Béal et al. TCS'98 , yang cocok dengan batas atas O ( | Q | 2 ) yang sesuai .$\Omega(|Q|^2)$$O(|Q|^2)$

PS penundaan sinkronisasi yang ditentukan dalam makalah adalah minimal yang mana otomat lokal deterministik adalah k- lokal.$k$$k$