Ứng dụng lý thuyết đồ thị để khảo sát đặc trưng một số lớp ngôn ngữ và điều khiển tương tranh

Abstract

Trình bày các khái niệm cơ sở về lý thuyết đồ thị, ngôn ngữ hình thức otomat, hệ mạng cùng các đối tượng khác liên quan đến chúng – là công cụ hữu ích để xây dựng nên các thuật toán hữu hiệu. Nghiên cứu bài toán điều khiển tương tranh các quá trình xảy ra trên một hệ thống và xây dựng hai thuật toán điều khiển tương tranh dựa trên đồ thị gán nhãn có hướng, làm rõ độ phức tạp của chúng. Kết quả của các thuật toán này có thể áp dụng cho các mô hình tương tranh khác và góp phần phát triển lý thuyết tương tranh. Trình bày kết quả nghiên cứu về độ phức tạp otomat của các thuật toán đoán nhận ngôn ngữ sinh bởi nguồn, biểu thức chính quy, sơ đồ sinh và chum – là cơ sở góp phần phát triển lý thuyết ngôn ngữ hình thức và lý thuyết thuật toán.