- Do nhu cầu thực tiễn, lý thuyết mã phát triển theo nhiều hướng khác nhau, chẳng hạn như hướng nghiên cứu liên quan đến mã độ dài cố định, điển hình là mã sửa sai, ứng dụng để phát hiện và sửa lỗi xuất hiện trên các kênh truyền tin. - hay mã độ dài biến đổi, được nghiên cứu đầu tiên bởi Schüzenberger. - Một số bài toán cơ bản trong nghiên cứu lý thuyết mã là: các tính chất liên quan đến sự phân tích một từ thành dãy các từ thuộc một tập cho trước. - tính chất không nhập nhằng của ngôn ngữ trong quan hệ với mã. - mã trong mối quan hệ với đại số, tổ hợp trên từ, lý thuyết ngôn ngữ hình thức và otomat. - Gần đây, một xu hướng mới trong nghiên cứu lý thuyết mã là các tác giả đưa vào xét các yếu tố điều khiển, nhập nhằng, đa trị để mở rộng khái niệm tích, từ đó xây dựng những lớp mã mới. - Gần đây hơn, một hướng nghiên cứu mới là việc mã hóa thông tin không chỉ phải dựa vào một mã của một ngôn ngữ trên một bảng chữ theo truyền thống. - Nam đã đề xuất các hình thức mã cặp của một cặp hai ngôn ngữ (mã luân phiên chẵn, mã luân phiên) dựa vào phân tích luân phiên của hai ngôn ngữ trên một bảng chữ. - Mã luân phiên, mã luân phiên chẵn là một phát triển mở rộng tự nhiên, nhưng không tầm thường của mã truyền thống. - Trong khi mỗi mã truyền thống là một ngôn ngữ X trên một bộ chữ nào đó thì mã luân phiên, mã luân phiên chẵn là một cặp {X,Y} của hai ngôn ngữ mà mỗi một trong chúng không nhất thiết phải là một mã truyền thống. - Mặt khác, nếu X là một mã truyền thống thì {X, X} là một mã luân phiên chẵn. - Như vậy mã luân phiên, mã luân phiên chẵn là một mở rộng thực sự của mã truyền thống, hứa hẹn một khả năng ứng dụng rộng rãi hơn và khả năng thúc đẩy phát triển các nghiên cứu mới, sâu sắc hơn về ngôn ngữ nói chung, lý thuyết mã nói riêng. - Mục đích nghiên cứu Đề tài đặt ra mục đích đi sâu nghiên cứu, mở rộng các lớp mã sử dụng biên làm ngữ cảnh để đề xuất các lớp mã mới. - Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của luận án là một số lớp mã mới sử dụng tích biên trên các từ định biên và nghiên cứu các tính chất, các bài toán cơ bản trên các lớp mã mới này trong mối liên hệ với mã truyền thống, mã dựa trên tích luân phiên. - Phạm vi nghiên cứu của luận án bao gồm: 1) Xem xét và thiết lập mới một số tính chất cùng với đặc trưng cần và đủ đối với các lớp mã dựa trên tích luân phiên. - 3) Nghiên cứu lớp ngôn ngữ của các từ định biên trên A. - đặc biệt là lớp ngôn ngữ chính quy của các từ định biên trong mối liên hệ với đại số và otomat thông qua các hình thức -otomat. - 4) Nghiên cứu các lớp mã mới dựa trên tích biên, mối quan hệ của nó với mã, mã luân phiên, mã luân phiên yếu trái (yếu phải), mã luân phiên chẵn và các bài toán cơ bản cho trường hợp lớp mã mới. - 5) Nghiên cứu độ trễ giải mã của lớp mã mới và thiết lập thuật toán xác định độ trễ giải mã cho lớp mã mới đã đề xuất ở trên. - Ý nghĩa khoa học và thực tiễn của đề tài Các tiếp cận mở rộng khái niệm tích dựa trên nhu cầu nội tại về sự phát triển của lý thuyết mã đã gợi mở hướng nghiên cứu của luận án. - Trong đó, các yếu tố biên của từ được đưa vào, làm cơ sở xây dựng tích mới theo biên của từ có tính nhập nhằng (tích biên) và từ đó đề xuất, nghiên cứu các lớp mã mới theo tích này. - Với các lớp mã mới, ngoài việc mở rộng một cách tự nhiên, các lớp mã này còn cho phép quay lại để biểu diễn các lớp mã truyền thống và đề xuất các bài toán mới trong lĩnh vực lý thuyết mã và ngôn ngữ hình thức, cũng như các lĩnh vực có liên quan như đại số, otomat. - Đóng góp thêm cho sự nghiên cứu mở rộng và làm sâu sắc thêm các kết quả của lý thuyết mã và ngôn ngữ hình thức. - Từ đó đề xuất hai lớp mã mới dựa trên tích luân phiên (mã luân phiên yếu trái, mã luân phiên yếu phải) và thiết lập mới một số tính chất của tích không nhập nhằng, mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải), mã luân phiên trong quan hệ với mã, đồng cấu mã, đặc trưng cần và đủ để một cặp ngôn ngữ X, Y cho trước có là mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải), mã luân phiên hay không. - Trong Chương 3 trình bày hình - 3 - thức tích luân phiên theo quan điểm đại số trên dạng từ mới thuộc tập các từ định biên A. - Từ đó cho phép đề xuất các khái niệm -ngôn ngữ chính quy, -otomat, -đoán nhận được và nhận được một số kết quả rất cơ bản về -ngôn ngữ chính quy trên A* (-ngôn ngữ chính quy trong quan hệ với -otomat đa định (đơn định) hữu hạn, -đồng cấu vị nhóm). - Chương 4 đề xuất bốn lớp mã mới (-mã, -mã yếu trái, -mã yếu phải, -mã chặt) dựa trên tích của các từ định biên trên A* và biểu diễn lớp mã, mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải), mã luân phiên dưới góc độ các phép toán đại số, cấu trúc đại số mới trên các từ định biên, thiết lập mối quan hệ giữa -mã, -mã yếu trái (yếu phải), -mã chặt với mã, mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải), mã luân phiên. - Trên cơ sở đó, xây dựng hai thuật toán kiểm tra tính chất mã của -mã, -mã chặt của một -ngôn ngữ chính quy cho trước cùng với đánh giá độ phức tạp của chúng. - Xây dựng hai thuật toán hiệu quả kiểm tra một cặp ngôn ngữ X, Y cho trước có là mã luân phiên chẵn, mã luân phiên hay không, với độ phức tạp thấp hơn so với hai thuật toán được thiết lập trước đó. - Từ những kết quả của luận án, lớp mã luân phiên, mã luân phiên yếu trái (yếu phải), mã luân phiên chẵn có thể mở rộng nghiên cứu về tính cực đại theo ngôn ngữ X, hoặc theo ngôn ngữ Y, hoặc theo cả ngôn ngữ X và ngôn ngữ Y, dựa trên các lớp mã mới đã được đề xuất. - Hội thảo khoa học quốc gia lần thứ IV “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin” (FAIR 2009), Hà nội . - Ta nhắc lại một số khái niệm cơ sở liên quan và tính chất cơ bản của mã, mối quan hệ giữa lý thuyết mã với cơ sở đại số, ngôn ngữ chính quy, otomat hữu hạn. - Một số khái niệm Mục này nhắc lại các khái niệm cơ bản như vị nhóm, đồng cấu, ngôn ngữ chính quy, otomat hữu hạn. - Một tập con X của vị nhóm tự do A* được gọi là mã trên A nếu ∀n, m ≥ 1 và x1, x2. - Nói cách khác, một tập X là mã nếu mọi từ trong A* có không quá một cách phân tích thành các từ trong X. - Dễ thấy rằng, mỗi tập con của một mã là mã. - Mệnh đề 1.2.2. - 38]) Nếu tập con X của A* là mã thì mọi đồng cấu β: B. - X thì X là mã. - 40]) Mọi tập prefix (suffix, bifix) khác {ε} đều là mã. - Mã X được gọi là mã prefix (t.ứng suffix, bifix) nếu nó là tập prefix (t.ứng suffix, bifix). - 108]) Cho X là mã trên A. - Khi đó, X là mã prefix (t.ứng suffix) khi và chỉ khi XA. - Mệnh đề sau là cơ sở để xây dựng thủ tục kiểm tra một tập X có là mã hay không (A. - Mệnh đề 1.2.18. - Khi đó, X là mã khi và chỉ khi X ∩ Ui. - để tìm hai phân tích khác nhau trên X của một từ w ∈A* bất kỳ. - Định lý 1.2.21. - 51]) Tập X ⊆ A+ là mã khi và chỉ khi không có tập (Ui)i ≥1 nào chứa từ rỗng. - Cho X là ngôn ngữ chính quy và đặt Y = {ε}. - 6 - 2 MÃ LUÂN PHIÊN Chương này trình bày lại khái niệm tích không nhập nhằng, mã luân phiên, mã luân phiên chẵn của hai tập ngôn ngữ X, Y thuộc A+. - Từ đó, thiết lập mới một số tính chất của tích không nhập nhằng, mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải), mã luân phiên trong quan hệ với mã truyền thống . - (ii) X là mã prefix khi và chỉ khi tích XA* là không nhập nhằng. - (iii) X là mã suffix khi và chỉ khi tích A*X là không nhập nhằng. - Qua mệnh đề 2.1.3.(i) cho ta thấy, đặc trưng của mã có thể được biểu diễn qua khái niệm tích không nhập nhằng, vì vậy có thể xem tích không nhập nhằng như trường hợp tổng quát của biểu diễn tích đối với mã. - Từ đó, dựa vào khái niệm tích không nhập nhằng, ta có thể xây dựng nhiều lớp mã mới, sẽ được trình bày trong các phần tiếp theo. - Mã luân phiên Một hình thức mở rộng khác của tích không nhập nhằng đã được đề xuất bởi P. - Từ đó cho phép thiết lập một lớp mã mới (gọi là mã luân phiên chẵn, mã luân phiên) và một số tính chất đặc trưng của mã luân phiên với cặp ngôn ngữ có tích không nhập nhằng. - Sau đây, ta sẽ trình bày lại một số kết quả đã được trình bày trong [5] và thiết lập mới một số kết quả nhằm làm phong phú thêm cho lớp mã luân phiên mới này. - Cho X, Y ⊆ A+, ta định nghĩa phân tích luân phiên theo hai tập ngôn ngữ X, Y như sau: Định nghĩa 2.2.1. - (iii) Hai phân tích luân phiên theo {X,Y} được gọi là cùng kiểu trái (t.ứng, cùng kiểu phải) nếu chúng cùng bắt đầu (t.ứng, cùng kết thúc) với các từ trong X hoặc trong Y. - (iv) Hai phân tích luân phiên theo {X,Y} được gọi là cùng kiểu nếu chúng vừa là cùng kiểu trái, vừa là cùng kiểu phải. - Dựa trên khái niệm tích không nhập nhằng và khái niệm phân tích luân phiên, cho phép ta định nghĩa lại một cách chặt chẽ đối với lớp mã luân phiên, mã luân phiên yếu trái (yếu phải) và mã luân phiên chẵn như sau: Định nghĩa 2.2.3. - Cặp {X,Y} được gọi là mã luân phiên nếu, với mỗi từ w ∈A+, w có không quá một phân tích luân phiên theo {X,Y}. - Ta ký hiệu LC là lớp mã (thông thường) và LALT là lớp mã luân phiên. - LALT thì tồn tại từ w ∈A+ sao cho các Overlap của hai phân tích của từ w là khác ε (xem Hình 2.1). - Các Overlap của hai phân tích của từ w. - Vì, với từ w = aba ∈A+ có hai phân tích luân phiên theo {X,Y}: w = (ab).(a. - dễ thấy XY = {ab, aab, aaab } là mã prefix, suy ra XY ∈ LC, nhưng {X,Y. - Vì, với từ w = aba ∈A+ có hai phân tích luân phiên khác nhau theo {X,Y} là: w = (a).(b).(a. - (ab).(a) Định nghĩa 2.2.7. - Cặp {X,Y} được gọi là mã luân phiên yếu trái (t.ứng, yếu phải) nếu không có từ nào trong A+ có hai phân tích luân phiên cùng kiểu trái (t.ứng, cùng kiểu phải) khác nhau theo {X,Y}. - Định nghĩa 2.2.8. - Cặp {X,Y} được gọi là mã luân phiên chẵn hay mã luân phiên cùng kiểu nếu không có từ nào trong A+ có hai phân tích luân phiên cùng kiểu khác nhau theo {X,Y}. - Từ Định nghĩa 2.2.7 và Định nghĩa 2.2.8 dễ thấy rằng, nếu cặp {X,Y} là mã luân phiên chẵn thì cặp {Y,X} cũng là mã luân phiên chẵn, và nếu cặp {X,Y} là mã luân phiên yếu trái (yếu phải) thì cặp {Y,X} là mã luân phiên yếu trái (yếu phải). - Gọi LWLALT (t.ứng LWRALT, LEALT) là lớp các cặp ngôn ngữ là mã luân phiên yếu trái (t.ứng. - mã luân phiên yếu phải, mã luân phiên chẵn). - Vì, với từ w = abbab ∈A+ có hai phân tích luân phiên khác nhau theo (X,Y) là: w = (ab).(b).(ab. - Vì, với từ w = bab ∈A+ có hai phân tích luân phiên khác nhau theo {X,Y} là: w = (b).(ab. - Tiếp theo, ta sẽ thiết lập một kết quả tương tự cho mã luân phiên, mã luân phiên chẵn. - Mệnh đề 2.2.12. - Mệnh đề 2.2.13. - U là tập tất cả các từ u ∈C+, u có ít nhất một phân tích luân phiên theo {A,B}, và V ⊆ U là tập tất cả các từ có dạng a1b1. - Đặc trưng của mã luân phiên, mã luân phiên chẵn Khi xây dựng các lớp mã mới, một trong các bài toán cơ bản đặt ra là bài toán kiểm định tính chất mã của ngôn ngữ (chính quy) cho trước. - Các định lý sau thể hiện đặc trưng cần và đủ đối với một cặp ngôn ngữ X, Y cho trước có là mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải), mã luân phiên hay không và các định lý này cũng tạo cơ sở cho ta thiết lập các thuật toán kiểm tra tính chất mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải), mã luân phiên. - Định lý 2.3.1. - 10 - Định lý 2.3.2. - Định lý 2.3.3. - Định lý 2.3.4. - Định lý 2.3.5. - Vì vậy, ta có trật tự của các lớp mã xét ở trên có thể được mô tả trực quan bởi sơ đồ sau: Hình 2.4. - Quan hệ của các lớp mã đã xét trên A*. - Trong trường hợp X, Y là ngôn ngữ chính quy được thỏa bởi các đồng cấu vị nhóm α : A. - N tương ứng, thì Định lý 2.3.1, Định lý 2.3.2, Định lý 2.3.3 và Định lý 2.3.4 cho phép thiết lập thuật toán kiểm định cặp {X, Y} có là mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải) hay không, có độ phức tạp cỡ O(8(|M|+|N. - cặp {X, Y} có là mã luân phiên hay không có độ phức tạp cỡ O(16(|M| +|N. - LC LWLALT∪ LWRALT LALT LWRALT LWLALT LEALT LWLALT∩ LWRALT : Quan hệ bao hàm NGÔN NGỮ CHÍNH QUY VÀ OTOMAT MỞ RỘNG Chương này đưa vào một cấu trúc ngôn ngữ mới - tập các từ định biên A. - Từ đó, cho phép trình bày tích luân phiên theo quan điểm đại số trên các từ định biên. - Cùng với việc đưa vào các khái niệm -ngôn ngữ chính quy, -otomat, -đoán nhận được, ta nhận được một số kết quả rất cơ bản về -ngôn ngữ chính quy, -đoán nhận được trên A. - tương tự như trên các đối tượng truyền thống trong lĩnh vực ngôn ngữ hình thức và otomat. - Một tập L ⊆ A* được gọi là một -ngôn ngữ trên A
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt