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

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 hóa otomat 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 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à không có yếu tố khoảng). | Tạp chí Tin học và Điều khiển học, , (2014), 148–162 ĐƠN ĐỊNH VÀ TỐI TIỂU HOÁ OTOMAT KHOẢNG∗ BÙI VŨ ANH Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội; vuanh@ 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ô 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 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 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 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à 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 hoá và tối tiểu hoá otomat khoảng. Từ khóa. Khoảng, otomat khoảng, đơn định hoá, tối tiểu hoá. Abstract. In the previous papers, we have proposed duration automata model and used the model in optimization [3], schedule problems [4] and in problems of the security area [5]. In this paper, we study problem of determining and minimizing the duration automata. Some additional problems are also considered to show how separate and merge durations on the arcs of the automata without changing accepted languages, remove unreachable states (with and without duration meaning). These problems are applied to solve the main problem: determining and minimizing duration automata. Key words. Duration, duration automata, deterministic, minimization. 1. CÁC PHÉP TOÁN TRÊN KHOẢNG Gọi ε = [0, +∞), D = {∅, ε} ∪ {[l, u], [l, u), (l, u], (l, u) | l, u ∈ Q} là tập các khoảng. Ta 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ở 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 ứ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à ∅. Cho d1 , d2 ∈ D, d1 = [l1 , u1 ], d2 = [l2 , u2 ], các phép toán trên khoảng được định nghĩa: -