Thuật toán mới xác định độ trễ giải mã của ngô ngữ chính quy

Trong các phép giải mã thông thường, khi xâu cần giải mã được đọc từ trái qua phải, thời điểm phát hiện thấy một từ mã trong xâu và thời điểm tất cả các từ mã trong xâu được xác định một cách chắc chắn là khác nhau. Khoảng thời gian trễ này được hình thức hóa bằng khái niệm độ trễ giải mã, khái niệm này xuất hiện rất sớm trong lý thuyết mã, như trong các công trình của Gilbert and Moore (1959) (xem [9]), của Levenshtein (1964) (xem [10]). Với khái niệm độ trễ giải mã thì lớp mã prefix là lớp mã có độ trễ giải mã bằng 0. từ đó độ trễ giải mã được sir dụng trong lý thuyết mã như là một tiêu chuẩn quan trọng để phân loại mã và là một tham số phản ánh dộ khó trong quá trình giải mã. Dối với các ứng dụng, việc xác định chính xác dộ trễ giải mã của một ngôn ngữ. cho phép các chương trình mật mã tăng hiệu quả thời gian và loại bỏ dược thao tác quay lui trong quá trình giải mã. Do vai trò quan trọng của dộ trễ giải mã, nhiều tác giả đã quan tâm nghiên cứu, một loạt các công trình như của Markov (1962) (xem [12]), Schiitzenberger (1966) (xem |11]), Choffrut (1979) (xem [13]), L. Staiger (1986) (xem [5]), J. Devolder (1994) (xem [3]), Stavros Konst ant ini dis (2002) (xem |8]), P.T. Huy-V.T. Nam (2002) (xem [14]), D. L. Van - I. Litovsky (2003) (xem [17]), N.D. Han - D.Q. Thang - II.N. Vinh (2010) (xem |16]), . tập trung nghiên cứu tính chất của dộ trễ giải mã.