1265646
Ôtômat cây
https://vi.wikipedia.org/wiki?curid=1265646
Title: Ôtômat cây
Có hai điểm khác biệt với ôtômat cây dưới lên: thứ nhất, formula_10, tập trạng thái đầu thay cho formula_11; thứ hai, các luật chuyển đi theo chiều ngược lại, nghĩa là viết lại một nút trạng thái thành nút với các nút con là trạng thái. Cây được chấp nhận nếu mọi nhánh đều được duyệt qua theo cách này.
Các luật viết lại khiến các ký hiệu của formula_4 'di chuyển' dọc theo các nhánh của cây.
Tính chất.
Khả năng nhận dạng.
Với một ôtômat dưới lên, một số hạng nền formula_13 (nghĩa là một cây) được đoán nhận nếu có một phép biến đổi bắt đầu từ t và kết thúc bởi q(t). Ngược lại, với ôtômat trên xuống, một số hạng nền formula_13 được đoán nhận nếu có một phép biến đổi bắt đầu từ q(t) và kết thúc bằng t, với q(t) là một trạng thái bắt đầu.
Ngôn ngữ cây formula_15 được đoán nhận bởi ôtômat cây formula_16 là tập hợp tất cả số hạng nền được đoán nhạn bởi formula_16. Một tập các số hạng nền có thể được đoán nhận nếu tồn tại một ôtômat cây đoán nhận nó.
Một thuộc tính quan trọng là "biến đổi đồng hình tuyến tính (nghĩa là bảo tồn bậc) không thay đổi tính đoán nhận được".
Tính đầy đủ và giản lược.
Một ôtômat cây hữu hạn không xác định là đầy đủ nếu có ít nhất một luật chuyển cho mỗi cặp ký hiệu-trạng thái. Một trạng thái formula_18 là đến được nếu có một số hạng nền (ground term) formula_13 sao cho có một phép biến đổi từ formula_13 đến formula_21. Một ôtômat cây hữu hạn là giản lược nếu mọi trạng thái của nó đều đến được.
Bao đóng.
Lớp các ngôn ngữ cây có thể nhận dạng được là đóng với các phép hợp, bù và giao.
Tham khảo.
Kiến thức trong trang này đều lấy từ chương một, sách "Tree automata techniques and applications" - http://tata.gforge.inria.fr