The automata complexity of the language transformation schema that contains operations with restricted degree

Chỉ số đề mục

28.25; 16.31

Lĩnh vực nghiên cứu

Dạng tài liệu

Tác giả

Nguyễn Văn Định, Nguyễn Phương Khánh⁽¹⁾

Nhan đề

The automata complexity of the language transformation schema that contains operations with restricted degree

Nhan đề tiếng anh

Nguồn trích

TC Tin học và điều khiển học

Năm xuất bản

2001

Số

2

Trang

39-44

ISSN

Từ khóa

Ô tô mát

Từ khóa tiếng anh

Tóm tắt

Dựa trên khái niệm ô tô mát có lối ra, xây dựng được lược đồ biến đổi ngôn ngữ (BĐNN). Khi các lược đồ BĐNN chứa các phép lặp không hạn chế thì độ phức tạp ô tô mát của nó không phụ thuộc vào số phép lặp và đã được đánh giá bởi BĐNN, nhưng khi phép số lặp, cũng như một số phép toán khác như phép lấy các cặp từ chẵn, lấy các cặp từ lẻ, phép bổ sung..., có bậc bị hạn chế thì độ phức tạp ô tô mát của các lược đồ BĐNN sẽ phụ thuộc vào độ sâu đặt dấu (bậc) của các phép toán. Trình bày mối liên hệ giữa độ phức tạp ô tô mát, số đỉnh cốt yếu và độ sâu đặt dấu các phép toán của một lược đồ BĐNN có chứa các phép toán có bậc được hạn chế

Tóm tắt tiếng anh

Kí hiệu kho

TTTTKHCNQG, CVv 127

File toàn văn

Xem toàn văn