Đơn định và tối tiểu hóa otomat khoảng

Tạp chí Tin học và Điều khiển học, T.30, S.2 (2014), 148–162<br /> <br /> ĐƠN ĐỊNH VÀ TỐI TIỂU HOÁ OTOMAT KHOẢNG∗<br /> BÙI VŨ ANH<br /> Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội; vuanh@vnu.edu.vn<br /> <br /> Tóm tắt. Các công trình trước đây chúng tôi đã đề xuất mô hình otomat khoảng và sử dụng mô<br /> hình này trong một số bài toán tối ưu [3] và lập lịch [4] cũng như các bài toán trong lĩnh vực bảo<br /> mật [5]. Trong nghiên cứu này, bài báo sẽ tập trung vào hai bài toán đơn định và tối tiểu hoá otomat<br /> khoảng. Các bài toán nhỏ hơn cũng được giải quyết là: tách/ghép các khoảng trên các cung của<br /> otomat mà không làm thay đổi ngôn ngữ được đoán nhận, loại các trạng thái không đạt được (có và<br /> không có yếu tố khoảng). Những bài toán này được dùng trong việc giải bài toán chính: đơn định<br /> hoá và tối tiểu hoá otomat khoảng.<br /> <br /> Từ khóa. Khoảng, otomat khoảng, đơn định hoá, tối tiểu hoá.<br /> Abstract. In the previous papers, we have proposed duration automata model and used the model<br /> in optimization [3], schedule problems [4] and in problems of the security area [5]. In this paper,<br /> we study problem of determining and minimizing the duration automata. Some additional problems<br /> are also considered to show how separate and merge durations on the arcs of the automata without<br /> changing accepted languages, remove unreachable states (with and without duration meaning). These<br /> problems are applied to solve the main problem: determining and minimizing duration automata.<br /> <br /> Key words. Duration, duration automata, deterministic, minimization.<br /> 1.<br /> <br /> CÁC PHÉP TOÁN TRÊN KHOẢNG<br /> <br /> Gọi ε = [0, +∞), D = {∅, ε} ∪ {[l, u], [l, u), (l, u], (l, u) | l, u ∈ Q} là tập các khoảng. Ta<br /> nói giá trị t ∈ R thuộc khoảng đóng d = [l, u] nếu l ≤ t ≤ u, viết là t ∈ d. Nếu khoảng d là mở<br /> thì dấu bằng không xảy ra và thay dấu ngoặc vuông (“ [, ]”) bằng ngoặc tròn (“ (, )”) tương<br /> ứng. Nếu không tồn tại giá trị t để t ∈ d thì d là khoảng trống, ký hiệu là ∅.<br /> Cho d1 , d2 ∈ D, d1 = [l1 , u1 ], d2 = [l2 , u2 ], các phép toán trên khoảng được định nghĩa:<br /> - Phép giao: d1 ∩ d2 = {t : t ∈ d1 và t ∈ d2 }.<br /> - Đoạn con: [l1 , u1 ] ⊆ [l2 , u2 ] ⇔ l2 ≤ l1 ≤ u1 ≤ u2 .<br /> - Phép hiệu liên tục:<br /> d1 \m d2 =<br /> <br /> d1 \ d2<br /> ∅<br /> <br /> nếu d1 = ∅, max{l1 , l2 } ≤ min{u1 , u2 } và d2 ⊆ d1<br /> (không xác định) nếu ngược lại.<br /> <br /> Hiệu của hai khoảng là phần còn lại liên tục của khoảng thứ nhất sau khi bớt khoảng thứ<br /> hai. Như vậy trong trường hợp khoảng thứ nhất chứa khoảng thứ hai hoặc khoảng thứ nhất<br /> là rỗng, hiệu sẽ là khoảng rỗng. Hiệu hai khoảng được minh hoạ ở Hình 1.<br /> ∗ Bài<br /> <br /> báo được thực hiện dưới sự hỗ trợ từ đề tài TN 13-02.<br /> <br /> 149<br /> <br /> ĐƠN ĐỊNH VÀ TỐI TIỂU HOÁ OTOMAT KHOẢNG<br /> <br /> d1<br /> <br /> d1<br /> <br /> d1<br /> <br /> d2<br /> <br /> d2<br /> <br /> d2<br /> d1 \d2<br /> <br /> d1 \d2 = ∅<br /> <br /> d1 \d2<br /> <br /> d1<br /> <br /> d1<br /> <br /> d1<br /> <br /> d2<br /> <br /> d2<br /> d1 \d2<br /> <br /> d2<br /> d1 \d2 = ∅<br /> <br /> d1 \d2<br /> <br /> Hình 1. Hiệu liên tục của hai khoảng<br /> - Phép hợp liên tục: Hợp liên tục của hai khoảng là khoảng lớn nhất chứa cả hai khoảng<br /> trong trường hợp hai khoảng có giao khác rỗng, trái lại, hợp liên tục không xác định.<br /> d1<br /> <br /> d2 =<br /> <br /> [min{l1 , l2 }, max{u1 , u2 }] nếu d1 ∩ d2 = ∅<br /> ∅<br /> (không xác định) nếu ngược lại.<br /> 2.<br /> <br /> 2.1.<br /> <br /> OTOMAT KHOẢNG<br /> <br /> Định nghĩa<br /> <br /> Trong một mạng giao thông, khi đi trên một cung đường, phương tiện đi lại thường bị<br /> ràng buộc về tốc độ tối thiểu và tốc độ tối đa hay thời gian cho phép xe cộ đi có dạng từ giờ<br /> nào đến giờ nào. Chẳng hạn chỉ cho xe tải chạy qua từ 22h ngày hôm trước đến 6h sáng ngày<br /> hôm sau (tương đương với cấm xe tải từ 6h-22h). Trong lập lịch cho các công việc, một công<br /> việc thường được gắn với thời gian có thể hoàn thành nó, hoặc ước lượng thời gian tối thiểu<br /> một công việc sẽ hoàn thành và ước lượng chắc chắn thực hiện công việc đó không vượt quá<br /> một giá trị ngưỡng. Trong kinh tế, khi thực hiện một dự án, mức kinh phí sử dụng có thể<br /> nằm trong một khoảng (mức tối thiểu để có thể triển khai được và mức tối đa không được<br /> phép vượt qua)... Như vậy có thể thấy ràng buộc dạng khoảng rất thường gặp trong thực tế,<br /> có thể mang ý nghĩa thời gian hay phi thời gian. Trường hợp riêng của khoảng là khi nó thu<br /> chuyển về dạng điểm, tức là hai mốc của khoảng trùng nhau. Trong phần này ta sẽ xây dựng<br /> một mô hình mà dùng nó, ta có thể mô hình hoá các hệ thống có ràng buộc dạng khoảng như<br /> nêu trên.<br /> Định nghĩa 2.1. Otomat khoảng (DA) M là bộ 7: S, Σ,<br /> <br /> ,<br /> <br /> , q, R, F trong đó:<br /> <br /> • S là tập hữu hạn các trạng thái của otomat, q ∈ S là trạng thái khởi đầu.<br /> • Σ, , lần lượt là các bảng chữ cái hành động internal, input và output. Ký hiệu<br /> A=Σ∪ ∪ .<br /> • R ⊆ S × A × D × S là quan hệ chuyển gắn thời gian, trong đó D là tập hợp các khoảng.<br /> Với mỗi phép chuyển e = (s, a, d, s ) ∈ R, a là hành động output của s và cũng là hành<br /> động input của s , d ∈ D là ràng buộc khoảng. Nếu s = s thì e là khuyên (vòng).<br /> <br /> 150<br /> <br /> BÙI VŨ ANH<br /> <br /> • F ⊆ S là tập các trạng thái đoán nhận (trạng thái kết).<br /> <br /> Gọi M = S, Σ,<br /> <br /> ,<br /> <br /> , q, R, F là DA. Xét dãy chuyển r<br /> (a1 ,d1 )<br /> <br /> (a2 ,d2 )<br /> <br /> (an ,dn )<br /> <br /> −−<br /> −−<br /> −−<br /> r : s0 − − → s1 − − → . . . sn−1 − − → sn .<br /> <br /> Nếu s0 là trạng thái khởi đầu và với mỗi i : 1 ≤ i ≤ n, ∃ej = (si−1 , ai , di , si ) ∈ R, thì<br /> p = (s0 , d1 )(s1 , d2 ) . . . (sn−1 , dn ) được gọi là một d-đường trong M và dãy<br /> w = (a1 , d1 )(a2 , d2 )(a3 , d3 ) . . . (an , dn )<br /> được gọi là một d-từ ứng với d-đường nói trên. Nếu tồn tại dãy ti ∈ di với mọi i = 1..n thì<br /> dãy w = (a1 , t1 )(a2 , t2 ) . . . (an , tn ) được gọi là một t-từ thoả w, khi đó w được gọi là d-từ thoả<br /> được. Trường hợp sn ∈ F thì p được gọi là một d-đường của M và w tương ứng được gọi<br /> là d-từ của M . Tập hợp các d-từ của M được gọi là ngôn ngữ do M đoán nhận, ký hiệu là<br /> L(M ). Mỗi (ai , di ) và (ai , ti ) lần lượt được gọi là một d-nhãn và t-nhãn. d-nhãn rỗng được<br /> định nghĩa là ε∞ = (∧, ε) trong đó ∧ là từ rỗng trong otomat truyền thống.<br /> Mô hình otomat với cách tiếp cận dùng khoảng như ở trên đã được nghiên cứu trong một<br /> số công trình như [10] của Dang Van Hung và Bui Vu Anh, [7] của Deepak D’Souza và P. S.<br /> Thiagarajan. So sánh với mô hình trong [7], otomat khoảng IA (interval automata) được xây<br /> dựng dựa trên otomat B¨chi với bảng chữ bổ sung thêm thành phần ràng buộc khoảng có<br /> u<br /> hai đầu mút là hai số thực. Bản chất ngôn ngữ do otomat khoảng IA đoán nhận sẽ là ngôn<br /> ngữ vô hạn và hành vi của các hệ thống được mô hình hoá bởi IA sẽ là các hệ có hành vi vô<br /> hạn. Trong [7], tác giả nghiên cứu khía cạnh ngôn ngữ của IA và chỉ ra ngôn ngữ được đoán<br /> nhận bởi IA là một tập con của ngôn ngữ thời gian được đoán nhận bởi otomat thời gian [1]<br /> (Timed Automata - TA). Khác với IA, DA sử dụng các đầu mút khoảng là các số nguyên và<br /> gán các ngữ nghĩa khoảng khác nhau cho d-từ tùy theo các tình huống trong thực tế. Có thể<br /> nói ngôn ngữ được đoán nhận bởi DA cũng không nằm ngoài lớp các ngôn ngữ được đoán<br /> nhận bởi TA. Do các mốc thời gian khoảng được sử dụng là các số nguyên nên DA và IA đều<br /> có thể mô tả các hệ thống thời gian thực với các mốc ràng buộc thời gian khoảng là các số<br /> nguyên. Ngoài ra, do các đầu mút thời gian của IA là các số thực nên không tận dụng được<br /> các kết quả đã có của TA như trong [1] khi nghiên cứu về tính đạt được và tính đóng của các<br /> phép toán trên ngôn ngữ... Thực tiễn, đặc biệt là khi xử lý mô hình trên máy tính, ít khi mốc<br /> là số thực được sử dụng, hoặc nếu có thì cũng có cách để chuyển sang mốc nguyên.<br /> Cho dãy các phép chuyển r, có một số cách gán ngữ nghĩa cho d−từ tương ứng với r được<br /> xác định như sau:<br /> - Ngữ nghĩa 1 : Gọi ti là thời gian tiêu tốn để hoàn thành hành động ai trong dãy r. Nếu<br /> ti ∈ di thì dãy w = (a1 , t1 )(a2 , t2 ) . . . (an , tn ) được gọi là một t-từ thoả w. Ngữ nghĩa này được<br /> gọi là ngữ nghĩa (theo) thời gian khoảng, lấy mốc tính thời gian là khi hành động bắt đầu<br /> thực hiện.<br /> - Ngữ nghĩa 2 : Gọi ti là thời điểm hoàn thành hành động ai trong dãy r. Xuất phát tại s0<br /> với t0 , nếu ti ∈ di với mọi i = 1..n thì dãy w = (a1 , t1 )(a2 , t2 ) . . . (an , tn ) được gọi là một t-từ<br /> thoả w. Ngữ nghĩa này được gọi là ngữ nghĩa (theo) thời gian điểm, lấy mốc tính thời gian là<br /> khi hành động đầu tiên của dãy bắt đầu thực hiện.<br /> - Ngữ nghĩa 3 : Gọi ti là thời điểm hệ thống thực hiện xong hành động ai và chuyển sang trạng<br /> thái si trong dãy r. Nếu ti ∈ di với mọi i = 1..n thì dãy w = (a1 , t1 )(a2 , t2 ) . . . (an , tn ) được<br /> gọi là một t-từ thoả w. Ngữ nghĩa này được gọi là ngữ nghĩa (theo) thời điểm chuyển trạng<br /> thái. Như vậy, hệ thống thực hiện xong hành động ai nhưng có thể chưa chuyển sang trạng<br /> <br /> ĐƠN ĐỊNH VÀ TỐI TIỂU HOÁ OTOMAT KHOẢNG<br /> <br /> 151<br /> <br /> thái mới; ngược lại, để có thể chuyển trạng thái, hành động ai phải được thực hiện xong. Nói<br /> cách khác, ngữ nghĩa này quan tâm đến thời điểm chuyển trạng thái sau thời điểm hoàn thành<br /> hành động. Otomat sau khi hoàn thành hành động có thể được chấp nhận một thời gian trễ<br /> trước khi nó chuyển trạng thái.<br /> Cho một d-từ, ngữ nghĩa theo thời gian khoảng luôn tồn tại (ngoại trừ khoảng ràng buộc<br /> là rỗng) hoặc công việc không hoàn thành trong khoảng thời gian ràng buộc. Nhưng khi xét<br /> với ngữ nghĩa thời gian điểm, một số trường hợp tồn tại ngữ nghĩa, một số trường hợp không<br /> và điều này cũng tương tự đối với ngữ nghĩa theo thời điểm chuyển trạng thái. Tuỳ theo yêu<br /> cầu, mục đích mà có thể chọn một loại ngữ nghĩa khi mô tả các hệ thống trong thực tiễn. Ngữ<br /> nghĩa 2 sẽ là trường hợp riêng của ngữ nghĩa 3 nếu thời điểm thực hiện xong hành động và<br /> thời điểm chuyển trạng thái là trùng nhau (không có độ trễ). Với ngữ nghĩa 3, ràng buộc di<br /> đối với một cung đi vào một trạng thái sẽ mang ý nghĩa đó là thời điểm sớm nhất cần đạt đến<br /> trạng thái đó và thời điểm muộn nhất phải rời khỏi trạng thái đó nếu đi vào theo cung được<br /> gắn với ràng buộc khoảng di . Otomat thay đổi trạng thái nếu nó thoả điều kiện rời khỏi một<br /> trạng thái và thoả cả điều kiện đến được một trạng thái mới. Như vậy, ràng buộc khoảng trên<br /> cung nó đã đến một trạng thái (và đang ở trạng thái đó) cùng ràng buộc khoảng trên cung<br /> nó sẽ đi đến phải đồng thời được thoả mãn. Để có được điều đó, ràng buộc khoảng trên hai<br /> cung đã đến và sẽ đi ra khỏi một trạng thái phải giao nhau. Do đó, nếu t là thời điểm chuyển<br /> trạng thái từ s sang s thì trước thời điểm t, hệ thống ở trạng thái s, sau thời điểm t hệ thống<br /> sẽ ở trạng thái s . Ở đây mỗi hành động chỉ có một trong hai khả năng là nếu thực hiện thì<br /> sẽ thành công và không thực hiện được.<br /> Otomat khoảng được định nghĩa trên ràng buộc khoảng tổng quát, yêu cầu các khoảng<br /> liên tiếp trên một đường là giao nhau hoặc không giao nhau. Mô hình mà bài báo nghiên cứu<br /> xét trường hợp các ràng buộc khoảng trên cung đi vào và đi ra khỏi một trạng thái là giao<br /> nhau nếu muốn đến/rời khỏi trạng thái đó, trái lại thì sẽ rơi vào trạng thái treo NULL (tắc<br /> nghẽn). Đây là trạng thái đặc biệt nằm trong không gian các trạng thái của otomat.<br /> Có thể nhận thấy nếu dãy số thực ti , i = 1..n diễn tả khoảng thời gian tiêu tốn để hoàn<br /> thành hành động tương ứng ai thì dãy này không có tính chất đơn điệu tăng. Nhưng với một<br /> dãy số thực ti , i = 1..n diễn tả thời điểm hoàn thành hành động tương ứng ai , hoặc diễn tả<br /> thời điểm chuyển trạng thái thì các dãy này sẽ là dãy đơn điệu tăng. Nếu quan sát thực hiện<br /> của một dãy hành động thì luôn có ngữ nghĩa 1. Với ngữ nghĩa 2, tại mọi vị trí i của d-từ cần<br /> có li ≤ ui+1 và với ngữ nghĩa 3, điều kiện sẽ là max{li , ll+1 } ≤ max{ui , ui+1 } với i = 1..n − 1.<br /> Với các hệ thời gian thực, ta chỉ có thể quan sát hoạt động của hệ theo thời gian. Do đó,<br /> t-từ chính là một dãy các quan sát (một thể hiện) tại các thời điểm của hệ. Các cách quan<br /> sát khác nhau sẽ dẫn đến các t-từ khác nhau ứng với các ý nghĩa được gắn cho t-từ. Một d-từ<br /> có thể xác định nhiều t-từ thoả nó. Trường hợp tồn tại t-từ thoả d-từ (theo một trong các<br /> ngữ nghĩa) thì d-từ là thoả được (theo ngữ nghĩa đó). Nếu không tồn tại t-từ như vậy, d-từ<br /> là không thoả được (ứng với một ngữ nghĩa, nhưng vẫn có thể là một t-từ ứng với một ngữ<br /> nghĩa khác). Ngữ nghĩa ở đây chính là giá trị quan sát của dãy ti và cách thức otomat vận<br /> hành để tạo ra dãy này. Với ngữ nghĩa 2 và 3, otomat rơi vào trạng thái treo (NULL) nếu<br /> otomat đang ở trạng thái s tại thời điểm t, mà không tồn tại giá trị t > t nào trên các cung<br /> ra khỏi s để ràng buộc khoảng d của nó được thoả (tức là t ∈ d với mọi t > t).<br /> Có thể thấy với một d-từ thoả được theo ngữ nghĩa 2 thì có thể xác định một dãy t-từ<br /> tương ứng theo ngữ nghĩa 1 khi chọn t0 = 0, ti = ti − ti−1 với i = 1..n. Tất nhiên ràng buộc<br /> khoảng di cũng phải thay đổi để phù hợp với điều kiện ti ∈ di thay cho ti ∈ di .<br /> <br /> 152<br /> <br /> BÙI VŨ ANH<br /> <br /> Trong [10] và [7], để theo dõi được thời gian thực hiện của hành động, giá trị (biến) đồng<br /> hồ được khởi tạo lại bằng 0. Như vậy, giá trị thời gian ti ở mỗi phép chuyển chính là thời gian<br /> thực hiện hành động ai trong dãy các phép chuyển. Việc đặt lại giá trị ti về 0 trước khi mỗi<br /> hành động bắt đầu sẽ phù hợp với việc gán ngữ nghĩa 1. Trong ứng dụng lập lịch công việc<br /> trên máy tính, thời gian triển khai công việc được tính từ khi công việc đó bắt đầu được triển<br /> khai nên có thể sử dụng ngữ nghĩa 1. Trong quan sát vận hành của một mạng giao thông, ngữ<br /> nghĩa sử dụng lại là ngữ nghĩa 2. Trong phần nghiên cứu về khía cạnh ngôn ngữ của otomat<br /> khoảng ở đây, bài báo tập trung vào nghiên cứu ngôn ngữ theo ngữ nghĩa thời điểm chuyển<br /> trạng thái, tức là yêu cầu mô hình có các khoảng liên tiếp phải giao nhau thì mới đi qua được.<br /> Nhận xét: Trong mô hình otomat khoảng, nếu mọi ràng buộc khoảng đều là ε, tức là ràng<br /> buộc luôn có thể thỏa mãn và không phân biệt loại chữ cái hành động thì mô hình trở thành<br /> mô hình otomat truyền thống. Nói cách khác, mô hình otomat truyền thống là trường hợp<br /> riêng của mô hình otomat khoảng. Đồng thời, cũng với ràng buộc khoảng là ε trên mọi cung<br /> thì nó trở thành mô hình otomat IO [11] và otomat IO cũng trở thành trường hợp riêng của<br /> DA. Nếu trên hai cung liên tiếp của một đường đi giao nhau bằng rỗng nhưng biên phải cung<br /> trước nhỏ hơn biên trái cung sau thì có thể bổ sung thêm một hành động chờ cho otomat để<br /> giá trị thời gian trôi đến khi gặp biên trái của ràng buộc khoảng trên cung tiếp theo và chuyển<br /> sang cung đó. Tuy nhiên, nếu giao các khoảng là rỗng nhưng biên trái khoảng sau nhỏ hơn<br /> biên phải của khoảng trước thì otomat sẽ không chuyển trạng thái tiếp được. Các phần sau<br /> đây nếu không có lưu ý gì thì ngữ nghĩa sử dụng sẽ là ngữ nghĩa theo thời điểm chuyển trạng<br /> thái.<br /> Hoạt động của otomat được mô tả như sau. Otomat xuất phát từ trạng thái khởi đầu q<br /> tại thời điểm t0 (thường được gán bằng 0). Cấu hình của M tại thời điểm t là cặp (s, t), trong<br /> đó s ∈ S và t ∈ R+ chỉ ra M đang ở trạng thái s tại thời điểm t và lân cận ngay trước t (trừ<br /> cấu hình xuất phát). Cấu hình khởi đầu của M là (q, t0 ) và cấu hình đoán nhận của M là<br /> (s, t) với s ∈ F và t ≥ 0.<br /> (s, a, d, s )<br /> <br /> s<br /> <br /> a)<br /> <br /> d<br /> <br /> t<br /> <br /> b)<br /> <br /> s<br /> <br /> d<br /> <br /> t<br /> <br /> Hình 2. Trạng thái di chuyển được a) và trạng thái treo b) theo ngữ nghĩa 2.<br /> <br /> Hình 2 minh hoạ otomat ở một trạng thái s với ràng buộc thời gian trên cung đi ra d và<br /> cấu hình hiện tại là (s, t). Ở hình 2a), otomat không bị rơi vào trạng thái tắc nghẽn (giá trị<br /> thời gian thực hiện hành động trước nhỏ hơn thời điểm cho phép thực hiện hành động tiếp<br /> theo). Trong Hình 2b) minh hoạ tình huống otomat ở trạng thái mà ràng buộc thời gian trên<br /> cung đi ra d không thể thoả (giá trị thời gian hoàn thành hành động đã vượt quá ràng buộc<br /> cho phép thực hiện hành động kế tiếp). Khi đó otomat không thể chuyển sang trạng thái tiếp<br /> mà rơi vào trạng thái tắc nghẽn. Như vậy, việc otomat có chuyển được đến trạng thái tiếp<br /> theo hay không phụ thuộc vào ràng buộc khoảng trên cung đi ra và thời điểm hoàn thành<br /> hành động.<br /> <br />