Tổng quan về luận án

Nghiên cứu về điều khiển hệ thống phân tán và lý thuyết ngôn ngữ hình thức đóng vai trò nền tảng trong khoa học máy tính hiện đại. Trong bối cảnh các hệ thống tính toán song song, xử lý dữ liệu lớn và kiến trúc vi dịch vụ phát triển mạnh mẽ, việc tối ưu hóa thực thi các tiến trình phân tán đối mặt với thách thức cốt lõi: làm thế nào để chuyển đổi các hành vi tuần tự thành các hành vi tương tranh tối ưu mà vẫn bảo toàn tính đúng đắn ngữ nghĩa. Luận án tiến sĩ thuộc chuyên ngành Khoa học Máy tính (chuyên hướng Lý thuyết Tính toán và Hệ thống Phân tán) tập trung giải quyết trực tiếp bài toán này thông qua việc tích hợp lý thuyết đồ thị định hướng gán nhãn, mô hình mạng Petri và lý thuyết otomat.

Research gap trọng tâm được xác định từ khoảng trống giữa biểu diễn hình thức của hành vi hệ thống và thuật toán điều khiển thực thi: các công trình kinh điển của Wolfgang Reisig (1985) và Grzegorz Rozenberg (1995) đã đặt nền móng cho mạng Petri và ngôn ngữ vết (trace languages), song việc xây dựng thuật toán tự động biến đổi trực tiếp các quá trình tuần tự thành quá trình tương tranh cực đại trên đồ thị trạng thái vẫn còn phân mảnh và thiếu các đánh giá độ phức tạp cụ thể. Đồng thời, đối với các công cụ sinh ngôn ngữ mới như sơ đồ sinh (generating scheme) và chùm đầu (heading bunch), cận trên của độ phức tạp otomat (automata complexity) trong bài toán đoán nhận ngôn ngữ từ hữu hạn và từ vô hạn ($\omega$-ngôn ngữ) chưa được thiết lập một cách hoàn chỉnh.

Các câu hỏi nghiên cứu và giả thuyết khoa học của luận án được xác định rõ ràng:

  • Câu hỏi nghiên cứu 1 (RQ1): Làm thế nào để mô hình hóa và tự động hóa quy trình biến đổi một quá trình tuần tự trên hệ mạng điều kiện - biến cố (Condition-Event net system) thành quá trình tương tranh có số bước thực thi ít nhất?
    • Giả thuyết 1 (H1): Kỹ thuật ghép cạnh và đầy đủ hóa đồ thị các trường hợp (case graph) cho phép xác định chính xác các bước tương tranh cực đại (maximal concurrent steps) với độ phức tạp tính toán đa thức trên không gian trạng thái đạt được.
  • Câu hỏi nghiên cứu 2 (RQ2): Có thể cải tiến thuật toán xây dựng và rút gọn đồ thị phủ (coverage graph) trên hệ mạng vị trí - chuyển (Place-Transition net system) nhằm cực đại hóa tính song song mà không làm bùng nổ không gian trạng thái hay không?
    • Giả thuyết 2 (H2): Rút gọn đồ thị phủ kết hợp phân tích ma trận đại số tuyến tính cho phép nhận diện các bước tương tranh đa hành động độc lập tài nguyên trong thời gian tối ưu.
  • Câu hỏi nghiên cứu 3 (RQ3): Cận trên của độ phức tạp otomat đoán nhận các lớp ngôn ngữ và $\omega$-ngôn ngữ sinh bởi nguồn (source), biểu thức chính quy (regular expression), sơ đồ sinh và chùm đầu được xác định như thế nào?
    • Giả thuyết 3 (H3): Việc xác định tập đỉnh cốt yếu và cấu trúc tiền tố/cung bù cho phép thiết lập cận trên số trạng thái của otomat hữu hạn đơn định (DFA) ở mức $2^{|D(I)|}$ hoặc các hàm mũ hữu hạn tương ứng.

Khung lý thuyết của luận án được xây dựng dựa trên sự giao thoa của ba trụ cột: Lý thuyết Mạng Petri (Petri Nets Theory của C.A. Petri và W. Reisig), Lý thuyết Ngôn ngữ Vết & Hành vi Tương tranh (Trace Theory của A. Mazurkiewicz), và Lý thuyết Ngôn ngữ Từ Vô hạn & Otomat ($\omega$-Automata Theory của J.R. Büchi, D. Muller và L. Staiger). Đóng góp đột phá của luận án mang lại giá trị định lượng rõ rệt: giảm thiểu số chu kỳ thực thi của tiến trình tuần tự về mức tối thiểu lý thuyết (bước tương tranh cực đại), tối ưu hóa thuật toán duyệt đồ thị ở cấp độ $O(n+m)$, và xác lập biểu thức toán học tường minh cho cận trên không gian trạng thái của otomat đoán nhận. Phạm vi nghiên cứu bao quát các hệ mạng điều kiện - biến cố hữu hạn, hệ mạng vị trí - chuyển có dung lượng và trọng số tổng quát, cùng các hệ thống sinh ngôn ngữ chính quy và $\omega$-ngôn ngữ đại diện.

Literature Review và Positioning

Lịch sử nghiên cứu mô hình hóa hệ thống tương tranh khởi nguồn từ công trình tiên phong của Carl Adam Petri (1962), thiết lập cơ sở hình thức cho việc biểu diễn các điều kiện, sự kiện và quan hệ nhân quả cục bộ. Tiếp đó, Wolfgang Reisig (1985, 1992) đã hệ thống hóa các lớp hệ mạng điều kiện - biến cố (C/E nets) và hệ mạng vị trí - chuyển (P/T nets), định nghĩa chặt chẽ không gian các trường hợp ($C \subseteq 2^B$) và quan hệ đạt được ($R_N$). Về phương diện hành vi hệ thống, Antoni Mazurkiewicz (1977) cùng Grzegorz Rozenberg (1995) phát triển lý thuyết ngôn ngữ vết, xem xét hành vi tương tranh dưới dạng các lớp tương đương của chuỗi tuần tự dựa trên quan hệ độc lập (independence relation) giữa các bảng chữ cái hành động.

Song song với hướng tiếp cận đại số, lý thuyết ngôn ngữ từ vô hạn ($\omega$-languages) và otomat được phát triển mạnh mẽ từ các công trình logic của J. Richard Büchi (1962), lý thuyết mạch của David E. Muller (1963), và các đặc trưng topo/độ phức tạp của Ludwig Staiger (1987, 1997) cùng Maurice Nivat (1979). Tại Việt Nam, trường phái nghiên cứu lý thuyết tính toán, độ phức tạp otomat và ngôn ngữ hình thức được định hình bởi Đỗ Long Vân, Phan Trung Huy, Nguyễn Hương Lâm (Viện Toán học) và Đặng Huy Ruận, Hoàng Chí Thành (Đại học Quốc gia Hà Nội), tập trung vào ngôn ngữ vết, phép đẩy trái (left-pushing) và tính toán độ phức tạp của các lớp otomat.

Trong y văn tồn tại hai luồng quan điểm và tranh luận học thuật đối lập về phương pháp tối ưu hóa tương tranh:

  1. Trường phái tiếp cận tĩnh (Static/Syntactic Trace Approach): Đại diện bởi Mazurkiewicz (1977) và Diekert & Rozenberg (1995), lập luận rằng việc chuyển đổi sang hành vi tương tranh nên được xử lý thuần túy trên bảng chữ cái và quan hệ độc lập tĩnh của các tác vụ trước khi hệ thống vận hành. Hạn chế của phương pháp này là không phản ánh được tính động của các tài nguyên chia sẻ phụ thuộc trạng thái (state-dependent resource contention).
  2. Trường phái tiếp cận động theo không gian trạng thái (State-Space/Reachability Approach): Tiêu biểu bởi Karp & Miller (1969) và Peterson (1981), cho rằng cần xây dựng toàn bộ cây đạt được/cây phủ (reachability/coverability tree) để kiểm soát tương tranh. Tuy nhiên, hướng tiếp cận này thường xuyên đối mặt với sự bùng nổ tổ hợp trạng thái (state explosion problem).

Luận án định vị chính xác vào giao điểm của hai trường phái trên: sử dụng đồ thị các trường hợp gán nhãn có hướng để trực quan hóa và thao tác trực tiếp trên cấu trúc hình học của hành vi hệ thống. Luận án trích dẫn trực tiếp thực trạng nghiên cứu: "Việc phân tích và điều khiển tương tranh các quá trình tuần tự xảy ra trên một hệ thống phân tán dựa vào ngôn ngữ sinh bởi hệ thống đang là một vấn đề thời sự." Thay vì phân tích tĩnh hay duyệt toàn bộ không gian trạng thái thô, tác giả áp dụng kỹ thuật ghép cạnh (edge merging) và rút gọn đồ thị phủ (coverage graph reduction) để biến đổi trực tiếp từ tuần tự thành bước tương tranh cực đại.

So sánh với các nghiên cứu quốc tế tiêu biểu:

  • So với mô hình cây phủ của Karp & Miller (1969) với độ phức tạp không gian rất lớn khi xử lý vector $\omega$-marking, thuật toán cải tiến của luận án thao tác trực tiếp trên đồ thị phủ rút gọn, giảm thiểu số đỉnh dư thừa và tích hợp trực tiếp quan hệ kích hoạt bước tương tranh.
  • So với giải thuật phân rã vết của Diekert & Gastin (2006), mô hình đồ thị các trường hợp đầy đủ của luận án bảo toàn tuyệt đối tính chất ngữ nghĩa động của C/E net, cho phép nhận diện trực tiếp các chu trình tương tranh mà không cần chuyển đổi trung gian qua đồ thị phụ thuộc quan hệ thứ tự bộ phận (poset).

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án mở rộng và hoàn thiện hệ thống lý thuyết mạng Petri và lý thuyết otomat thông qua các đóng góp cụ thể:

  1. Mở rộng Lý thuyết Mạng Điều kiện - Biến cố (Reisig, 1985): Định nghĩa tường minh toán học cho bộ bốn $\Sigma = (B, E; F, C)$ và chứng minh mối liên hệ tương đương giữa tính chất chu trình (cycle net system) của hệ mạng với tính liên thông mạnh (strongly connected) của đồ thị các trường hợp $\Phi = (C, P)$. Luận án chứng minh định lý nền tảng: "Hệ mạng điều kiện - biến cố $\Sigma$ là chu trình khi và chỉ khi đồ thị các trường hợp của nó là liên thông mạnh."
  2. Hình thức hóa khái niệm Bước tương tranh cực đại (Maximal Concurrent Step): Phát triển mô hình chuyển đổi tuần tự - tương tranh dựa trên quan hệ đạt được $R_N = (r_N \cup r_N^{-1})^*$. Một tập các biến cố $U \subseteq E$ tạo thành một bước tương tranh tại trường hợp $c$ khi và chỉ khi các biến cố trong $U$ độc lập điều kiện vào/ra và được kích hoạt đồng thời. Luận án chỉ rõ cơ chế: "Đến khi không thể ghép cạnh được nữa thì các bước tương tranh mà ta nhận được trở thành cực đại và số bước của quá trình là ít nhất có thể. Khi đó, các quá trình với các bước tương tranh cực đại được thực thi trong môi trường song song với thời gian ít nhất."
  3. Mô hình hóa Đại số Tuyến tính cho Hệ mạng Vị trí - Chuyển (P/T nets): Biểu diễn mạng $\Sigma = (P, T; F, K, M_0, W)$ thông qua ma trận chuyển $N: P \times T \to \mathbb{Z}$ với $N(p,t) = W(t,p) - W(p,t)$, thiết lập quan hệ kích hoạt $M [t > M'$ dưới dạng phương trình trạng thái ma trận $M' = M + N \cdot \vec{t}$.
  4. Xác lập Cận trên Độ phức tạp Otomat của các công cụ sinh: Chứng minh toán học chặt chẽ về số trạng thái cực đại của DFA tương đương khi đoán nhận ngôn ngữ từ nguồn (Source), Biểu thức chính quy (Regular Expression), Sơ đồ sinh (Generating Scheme), và Chùm đầu (Heading Bunch), khẳng định cận trên số trạng thái DFA tương đương với nguồn $I$ không vượt quá $2^{|D(I)|}$, trong đó $D(I)$ là tập các đỉnh cốt yếu.
+-------------------------------------------------------------+
|               KHUNG PHÂN TÍCH TƯƠNG TRANH TOÀN DIỆN         |
+-------------------------------------------------------------+
|  [Hệ mạng Petri: C/E Net & P/T Net]                         |
|     │                                                       |
|     ▼ (Sinh ngôn ngữ / Hành vi tuần tự)                     |
|  [Chuỗi biến cố tuần tự: c0 [e1> c1 [e2> c2 ... [en> cn]    |
|     │                                                       |
|     ▼ (Biểu diễn hình học & Đại số)                         |
|  [Đồ thị các trường hợp / Đồ thị phủ]                       |
|     │                                                       |
|     ▼ (Thuật toán Ghép cạnh & Rút gọn)                      |
|  [Đồ thị đầy đủ / Đồ thị phủ rút gọn]                       |
|     │                                                       |
|     ▼ (Tối ưu hóa thực thi)                                 |
|  [Quá trình tương tranh tối ưu với BƯỚC TƯƠNG TRANH CỰC ĐẠI] |
+-------------------------------------------------------------+

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp nhuần nhuyễn 3 cấu trúc lý thuyết chính:

  • Lý thuyết Đồ thị Định hướng Gán nhãn (Labelled Directed Graphs): Đóng vai trò môi trường biểu diễn không gian trạng thái, với tập đỉnh $V$ là các trường hợp $C$ hoặc vector đánh dấu $M$, tập cung $E$ mang nhãn là các biến cố/chuyển đơn lẻ hoặc tập hợp bước tương tranh.
  • Lý thuyết Mạng Phân tán (Distributed Net Systems): Cung cấp cơ chế động lực học (firing semantics), xác định tập vào $\bullet x$ và tập ra $x \bullet$ của các phần tử nhằm thiết lập điều kiện kích hoạt không xung đột tài nguyên.
  • Lý thuyết Otomat & Ngôn ngữ Hình thức (Automata & Formal Languages): Cung cấp công cụ đánh giá độ phức tạp đoán nhận cho cả từ hữu hạn ($\Sigma^*$) và từ vô hạn ($\Sigma^\omega$).

Điều kiện biên (Boundary Conditions): Khung phân tích áp dụng cho các hệ mạng Petri đơn giản (không chứa hai phần tử có cùng tập vào và tập ra), không có phần tử cô lập, dung lượng vị trí $K(p) \ge 1$, và tập đỉnh cốt yếu $D(I)$ của nguồn là hữu hạn.

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Luận án tuân thủ thế giới quan thực chứng khoa học (positivism) kết hợp chặt chẽ với phương pháp diễn dịch toán học (mathematical deductive method) và phân tích thuật toán hình thức (formal algorithmic analysis). Thiết kế nghiên cứu được phân tầng rõ ràng qua 3 cấp độ:

  1. Cấp độ Cấu trúc Tĩnh (Structural Level): Mô tả đồ thị hai phần của mạng Petri $N = (S, T; F)$, ma trận kề $A$, danh sách kề $DK$, và ma trận biến đổi đại số tuyến tính $N(p,t)$.
  2. Cấp độ Hành vi Động (Dynamic Behavioral Level): Xây dựng không gian trạng thái thông qua quan hệ đạt được $R_N$, đồ thị các trường hợp $\Phi$, và đồ thị phủ biểu diễn vector đánh dấu $\omega$.
  3. Cấp độ Tính toán & Tối ưu hóa (Algorithmic/Complexity Level): Thiết kế các thuật toán chuyển đổi tương tranh, thuật toán đơn định hóa nguồn, và chứng minh các định lý về cận trên độ phức tạp trạng thái.

Quy trình nghiên cứu rigorous

Quy trình nghiên cứu được thực hiện qua các giao thức toán học nghiêm ngặt:

  • Giao thức biểu diễn đồ thị: Sử dụng cấu trúc danh sách kề $DK$ nhằm tối ưu hóa bộ nhớ cho các đồ thị thưa biểu diễn hệ mạng. Thuật toán tìm đường đi giữa hai đỉnh dựa trên tính lũy thừa ma trận kề $T = \sum_{k=1}^n A^k$ với độ phức tạp $O(n^4)$ được dùng làm đối sánh chuẩn để thay thế bằng thuật toán duyệt theo chiều sâu (DFS) và duyệt theo chiều rộng (BFS) đạt độ phức tạp tối ưu $O(n+m)$ ($n = |V|, m = |E|$).
  • Giao thức đơn định hóa và đầy đủ hóa nguồn: Xây dựng ánh xạ $T_I(s, a) = {u \in D(I) \mid a \in L_I(s, u)}$ trên tập các đỉnh cốt yếu $D(I)$. Sau đó mở rộng thành $H_I(C, a) = \bigcup_{s \in C} T_I(s, a)$ cho mỗi tập con $C \subseteq D(I)$. Không gian trạng thái mới của nguồn đơn định $K$ được thiết lập trên tập lũy thừa $V_K = 2^{V(I)}$, với tập kết thúc $F_K = {C \subseteq V(I) \mid C \cap F(I) \neq \emptyset}$.
  • Đảm bảo tính giá trị và độ tin cậy hình thức: Mọi thuật toán đều đi kèm chứng minh toán học hoàn chỉnh về tính dừng (termination), tính đúng đắn ngữ nghĩa (soundness), và tính đầy đủ (completeness) thông qua quy nạp toán học và lý thuyết đồ thị.
+-------------------------------------------------------------+
|            QUY TRÌNH THUẬT TOÁN ĐẦY ĐỦ HÓA ĐỒ THỊ           |
+-------------------------------------------------------------+
| 1. Khởi tạo Đồ thị các trường hợp ban đầu Φ = (C, P)        |
|    - Đỉnh: Các trường hợp c ∈ C                             |
|    - Cung: c [e> c' với e ∈ E                               |
|                                                             |
| 2. Kiểm tra điều kiện tương tranh cho cặp biến cố (e1, e2): |
|    - (•e1 ∪ e1•) ∩ (•e2 ∪ e2•) = ∅                          |
|    - c [e1> c1 [e2> c' VÀ c [e2> c2 [e1> c'                 |
|                                                             |
| 3. Thực hiện GHÉP CẠNH (Edge Merging):                      |
|    - Bổ sung cung tương tranh: c [{e1, e2}> c'              |
|                                                             |
| 4. Lặp quy trình cho đến khi đạt BƯỚC TƯƠNG TRANH CỰC ĐẠI:  |
|    - Không còn cạnh nào có thể ghép tiếp                    |
|    - Xuất Đồ thị các trường hợp đầy đủ                      |
+-------------------------------------------------------------+

Data và phân tích

Mặc dù là nghiên cứu lý thuyết tính toán, dữ liệu trong luận án được cấu trúc hóa dưới dạng các mô hình hệ mạng chuẩn (benchmarks), các ma trận trạng thái và đồ thị minh họa:

  • Bộ dữ liệu thực nghiệm mô hình: 21 hình vẽ kỹ thuật chi tiết mô tả đồ thị, mạng Petri C/E, P/T net, nguồn đơn định/bù/giao/ghép, và sơ đồ sinh.
  • Kỹ thuật phân tích ma trận: Biểu diễn hệ mạng vị trí - chuyển bằng ma trận kích thước $|P| \times |T|$:

$$\begin{pmatrix} p_1: & -2 & 1 & 0 & 0 \ p_2: & 2 & -2 & 0 & 0 \ p_3: & 5 & -4 & 2 & 1 \ p_4: & -3 & -2 & 5 & 0 \ p_5: & 1 & 2 & 1 & 0 \end{pmatrix}$$

  • Vector dung lượng $K = (3, 2, 8, 5, \infty)^T$ và vector đánh dấu ban đầu $M_0 = (3, 0, 1, 5, 1)^T$.
  • Đánh giá độ phức tạp thuật toán:
    • Thuật toán xác định đường đi ma trận: $O(n^4)$.
    • Thuật toán duyệt DFS/BFS: $O(n+m)$.
    • Thuật toán xây dựng nguồn tương đương từ Otomat: Tuyến tính theo số trạng thái và hàm chuyển $|Q| \times |\Sigma|$.
    • Cận trên độ phức tạp trạng thái DFA: $2^{|D(I)|}$.

Phát hiện đột phá và implications

Những phát hiện then chốt

  1. Phát hiện 1: Quy luật biến đổi tương tranh bảo toàn ngữ nghĩa qua ghép cạnh. Luận án chứng minh rằng việc bổ sung các cung gán nhãn tập hợp biến cố ${e_1, e_2, \dots, e_k}$ vào đồ thị các trường hợp không làm thay đổi quan hệ đạt được $R_N$, nhưng làm giảm độ dài đường đi của quá trình từ $k$ bước đơn xuống đúng 1 bước tương tranh.
  2. Phát hiện 2: Đặc trưng hình học của Hệ mạng Chu trình. Luận án thiết lập mối liên hệ tất yếu: hệ mạng C/E $\Sigma$ có tính chu trình khi và chỉ khi đồ thị các trường hợp tương ứng là liên thông mạnh. Kết quả này cho phép chuyển bài toán kiểm tra tính chu trình của hệ phân tán sang bài toán kiểm tra tính liên thông mạnh trên đồ thị với độ phức tạp $O(n+m)$ bằng thuật toán Tarjan/Kosaraju.
  3. Phát hiện 3: Tối ưu hóa Đồ thị phủ cho Hệ mạng Vị trí - Chuyển. Luận án cải tiến thuật toán xây dựng đồ thị phủ từ công trình của Juhás (1994), loại bỏ các trạng thái trùng lặp và vector đánh dấu $\omega$ thừa thông qua rút gọn đồ thị phủ, cho phép tìm bước tương tranh cực đại nhanh hơn đáng kể so với phương pháp mở rộng cây phủ truyền thống.
  4. Phát hiện 4: Cận trên chặt của độ phức tạp Otomat cho Sơ đồ sinh và Chùm đầu. Chứng minh rằng đối với các công cụ sinh ngôn ngữ chính quy phức tạp như sơ đồ sinh (generating scheme) và chùm đầu (heading bunch), số lượng trạng thái của DFA đoán nhận tối thiểu bị chặn trên bởi hàm mũ của tập các cung cốt yếu và đồ thị sinh thành phần ($l(I_1) = l(I_2) = 0$).
Công cụ sinh ngôn ngữ Không gian trạng thái ban đầu Cơ chế chuyển đổi otomat Cận trên độ phức tạp trạng thái DFA
Nguồn không đơn định ($I$) $V(I), E(I)$ Ánh xạ tập đỉnh cốt yếu $D(I)$ $O(2^{|D(I)|})$
Biểu thức chính quy ($r$) Chiều dài biểu thức $|r|$ Nguồn tương đương $\to$ DFA $O(2^{|r|})$
Sơ đồ sinh ($S$) Đồ thị sinh ${I_1, I_2, \dots}$ Tiền tố, cung bù & DFA kết hợp $O(2^{\sum |D(I_k)|})$
Chùm đầu ($B$) Tập chùm và $\omega$-ngôn ngữ Otomat hữu hạn đơn định Büchi $O(2^{|V_B|})$

Implications đa chiều

  • Về mặt Lý thuyết: Luận án hợp nhất thành công lý thuyết đồ thị cấu trúc, lý thuyết mạng Petri và lý thuyết ngôn ngữ hình thức thành một khung phân tích thống nhất, tạo cơ sở toán học để nghiên cứu các mô hình tính toán song song thế hệ mới.
  • Về mặt Phương pháp luận: Cung cấp phương pháp hình học hóa không gian trạng thái, chuyển đổi các bài toán đại số/ngữ nghĩa phân tán phức tạp thành các bài toán xử lý đồ thị hữu hạn (ghép cạnh, rút gọn đồ thị, duyệt liên thông).
  • Về mặt Ứng dụng Thực tiễn:
    • Tối ưu hóa trình biên dịch song song (parallelizing compilers): Tự động phát hiện các đoạn mã tuần tự độc lập và gom cụm thành các khối lệnh thực thi đồng thời trên vi xử lý đa lõi (multi-core CPUs/GPUs).
    • Tối ưu hóa điều phối quy trình nghiệp vụ (Workflow & Business Process Management): Rút ngắn thời gian hoàn thành các quy trình trong hệ thống ERP thông qua phát hiện các bước tương tranh cực đại giữa các phòng ban.
  • Về mặt Chính sách và Tiêu chuẩn Công nghệ: Đóng góp luận cứ khoa học cho việc chuẩn hóa các giao thức truyền thông phân tán an toàn và không xảy ra bế tắc (deadlock-free protocols).

Limitations và Future Research

Mặc dù đạt được nhiều kết quả đột phá, luận án thẳng thắn thừa nhận các giới hạn học thuật:

  • Giới hạn 1 (Không gian trạng thái hữu hạn): Kỹ thuật ghép cạnh trên đồ thị các trường hợp phụ thuộc vào giả định không gian các trường hợp $C$ là hữu hạn. Khi áp dụng cho các hệ mạng vô hạn trạng thái (unbounded nets), phương pháp đòi hỏi xấp xỉ hóa qua đồ thị phủ.
  • Giới hạn 2 (Mạng Petri cấp thấp): Luận án tập trung vào C/E nets và P/T nets thuần túy, chưa mở rộng trực tiếp sang các lớp mạng Petri cao cấp như Mạng Petri Màu (Colored Petri Nets - CPN), Mạng Petri Thời gian (Timed/Stochastic Petri Nets).
  • Giới hạn 3 (Cận trên lý thuyết): Các đánh giá độ phức tạp trạng thái otomat ($2^{|D(I)|}$) là cận trên trong trường hợp xấu nhất (worst-case upper bound), chưa tính đến các kỹ thuật tối thiểu hóa trạng thái (state minimization) thực tế như thuật toán Hopcroft.

Chương trình nghiên cứu tương lai (Future Research Agenda):

  1. Mở rộng thuật toán điều khiển tương tranh sang mô hình Mạng Petri Màu để xử lý dữ liệu phức tạp trong hệ thống phân tán hướng sự kiện.
  2. Tích hợp ràng buộc thời gian thực (Real-time constraints) vào đồ thị các trường hợp đầy đủ nhằm tối ưu hóa các hệ thống nhúng quan trọng (safety-critical embedded systems).
  3. Phát triển gói thư viện thuật toán mã nguồn mở tự động hóa việc rút gọn đồ thị phủ và ghép cạnh trên các nền tảng phân tán quy mô lớn.
  4. Nghiên cứu độ phức tạp topo sâu hơn của các lớp $\omega$-ngôn ngữ sinh bởi sơ đồ sinh trong phân cấp Borel.

Tác động và ảnh hưởng

  • Tác động Học thuật: Đóng góp trực tiếp vào dòng chảy nghiên cứu của Viện Toán học và Đại học Quốc gia Hà Nội về ngôn ngữ hình thức và hệ thống tương tranh. Kết quả nghiên cứu là tài liệu tham khảo nền tảng cho các hướng nghiên cứu tiếp nối về ngôn ngữ vết và điều khiển tối ưu.
  • Chuyển đổi Công nghiệp: Cung cấp giải thuật lõi cho việc thiết kế các công cụ phân tích tĩnh (static analysis tools), phát hiện race conditions và deadlocks trong các hệ thống phần mềm phân tán quy mô lớn (cloud computing, microservices).
  • Ý nghĩa Quốc tế: Thu hẹp khoảng cách giữa lý thuyết mạng Petri kinh điển châu Âu (Reisig, Rozenberg) và các phương pháp phân tích độ phức tạp otomat hiện đại, mở ra hướng tiếp cận hình học hiệu quả cho bài toán tương tranh.

Đối tượng hưởng lợi

  • Nghiên cứu sinh & Nhà nghiên cứu Lý thuyết: Tiếp cận khung phân tích hoàn chỉnh kết hợp mạng Petri, đồ thị gán nhãn và otomat, cùng các kỹ thuật chứng minh cận trên độ phức tạp trạng thái.
  • Kỹ sư Kiến trúc Phần mềm & Hệ thống Phân tán: Ứng dụng các nguyên lý ghép cạnh và bước tương tranh cực đại để thiết kế các bộ lập lịch (schedulers) tối ưu cho hệ thống đa tiến trình.
  • Chuyên gia Tối ưu hóa Quy trình (Business Process Architects): Sử dụng mô hình mạng P/T và thuật toán rút gọn đồ thị phủ để tái cấu trúc và loại bỏ điểm nghẽn trong các chuỗi cung ứng và quy trình sản xuất.

Câu hỏi chuyên sâu

  1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và nó mở rộng lý thuyết nào?
    • Trả lời: Đóng góp độc đáo nhất là việc thiết lập thuật toán hình học "ghép cạnh" để làm đầy đủ đồ thị các trường hợp, qua đó mở rộng trực tiếp Lý thuyết Mạng Điều kiện - Biến cố của Wolfgang Reisig (1985). Luận án giải quyết triệt để bài toán chuyển đổi hình thức từ hành vi tuần tự (chuỗi các biến cố đơn) sang hành vi tương tranh tối ưu (chuỗi các bước tương tranh cực đại) trực tiếp trên cấu trúc đồ thị trạng thái.
  2. Đột phá phương pháp luận của luận án khi so sánh với ít nhất 2 nghiên cứu quốc tế?
    • Trả lời: So với Lý thuyết Ngôn ngữ Vết Mazurkiewicz (Mazurkiewicz, 1977) vốn chỉ xử lý quan hệ độc lập tĩnh trên bảng chữ cái, luận án phân tích tương tranh động dựa trên trạng thái kích hoạt thực tế ($c[e>c'$). So với Thuật toán Cây phủ Karp-Miller (Karp & Miller, 1969) dễ gây bùng nổ tổ hợp vector $\omega$, luận án cải tiến thuật toán của Juhás (1994) để rút gọn trực tiếp đồ thị phủ, giảm thiểu đáng kể số nút dư thừa khi tìm kiếm bước tương tranh trên mạng P/T.
  3. Phát hiện bất ngờ nhất được hỗ trợ bởi dữ liệu/chứng minh toán học là gì?
    • Trả lời: Phát hiện về tính tương đương tuyệt đối giữa cấu trúc topo đồ thị và tính chất động lực học hệ thống: một hệ mạng C/E là chu trình (mọi trường hợp đều tái sản xuất được qua quan hệ đạt tới tiến $r_N^*$) khi và chỉ khi đồ thị các trường hợp của nó là đồ thị liên thông mạnh. Điều này cho phép quy giảm một bài toán ngữ nghĩa phân tán phức tạp về một thuật toán duyệt đồ thị tuyến tính $O(n+m)$.
  4. Luận án có cung cấp giao thức tái lập (Replication Protocol) rõ ràng không?
    • Trả lời: Có. Luận án cung cấp mã giả thuật toán chi tiết từng bước cho: (1) Đơn định hóa và đầy đủ hóa nguồn (Thuật toán 1.5); (2) Xây dựng nguồn bù, nguồn giao, nguồn tích ghép (Thuật toán 1.6, 1.7, 1.8); (3) Xây dựng Otomat tương đương từ Nguồn và ngược lại (Thuật toán 1.9, 1.10); (4) Thuật toán duyệt DFS/BFS trên mảng danh sách kề $DK$.
  5. Chương trình nghiên cứu 10 năm tiếp theo được định hình như thế nào?
    • Trả lời: Định hình theo 3 giai đoạn: (1) Mở rộng giải thuật tương tranh sang Mạng Petri Màu và Mạng Petri Thời gian; (2) Tích hợp vào các framework phân tích tĩnh tự động cho phần mềm song song; (3) Khảo sát độ phức tạp topo sâu hơn của các lớp $\omega$-ngôn ngữ trong phân loại đệ quy và phân cấp không gian trạng thái.

Kết luận

Luận án tiến sĩ đã hoàn thành xuất sắc các mục tiêu khoa học đề ra, đóng góp những kết quả nền tảng cho chuyên ngành Khoa học Máy tính:

  1. Hình thức hóa tường minh và giải quyết trọn vẹn bài toán điều khiển tương tranh tối ưu các quá trình trên hệ thống phân tán.
  2. Xây dựng thành công thuật toán làm đầy đủ đồ thị các trường hợp của hệ mạng điều kiện - biến cố để chiết xuất các bước tương tranh cực đại.
  3. Cải tiến và tối ưu hóa thuật toán xây dựng đồ thị phủ trên hệ mạng vị trí - chuyển, làm sáng tỏ cấu trúc hành vi tương tranh đa mức.
  4. Thiết lập công thức toán học chặt chẽ xác định cận trên độ phức tạp otomat đoán nhận ngôn ngữ sinh bởi nguồn, biểu thức chính quy, sơ đồ sinh và chùm đầu.
  5. Chứng minh các định lý cấu trúc quan trọng liên kết giữa tính chất chu trình của hệ mạng và tính liên thông mạnh của đồ thị trạng thái.
  6. Mở ra 3 hướng nghiên cứu mới: tối ưu hóa mã nguồn song song tự động, xác minh hình thức hệ thống nhúng thời gian thực, và phân loại topo độ phức tạp của $\omega$-ngôn ngữ trên các cấu trúc sinh đại số mới.