Ôtômat cây

Ôtômat cây (tiếng Anh: tree automaton) là một loại máy trạng thái. Ôtômat cây xử lý cấu trúc cây, thay vì xâu như các máy trạng thái thường gặp.

Bài viết này đề cập đến ôtômat phân nhánh cây, tương đương với các ngôn ngữ chính quy của cây. Một khái niệm ôtômat cây khác có thể tìm thấy là ôtômat duyệt cây. 

Tương tự ôtômat cổ điển, ôtômat cây hữu hạn có thể xác định (ÔHX) hoặc không (ÔHK). Theo cách xử lý cây đầu vào, ôtômat cây hữu hạn có thể thuộc vào hai loại: (a) dưới lên, (b) trên xuống. Đây là vấn đề quan trọng vì mặc dù ôtômat ÔHK trên xuống và ÔHK dưới lên tương đương về khả năng biểu diễn nhưng ÔHX trên xuống kém hơn hẳn ôtômat dưới lên tương ứng vì tính chất của cây xác định bởi ÔHX trên xuống chỉ có thể phụ thuộc vào tính chất của đường đi. ÔHX dưới lên mạnh ngang với ÔHK.

==Định nghĩa==
Một bảng chữ cái xếp hạng là một cặp bảng chữ cái formula_1 và hàm bậc (arity) sao cho có thể xây dựng một số hạng. Các thành tố trống (bậc bằng không) còn được gọi là hằng. Toán hạng được xây dựng bằng các ký hiện bậc một và hằng có thể được coi là xâu. Bậc cao hơn tạo ra cây.

Một ôtômat cây hữu hạn trên formula_2 được định nghĩa là:
formula_3

Ở đây, formula_4 là tập các trạng thái, formula_2 là một bảng chữ cái xếp hạng formula_6 là một tập các trạng thái kết thúc và formula_7 là tập luật chuyển trạng thái, nghĩa là các luật viết lại một nút có các con là trạng thái thành nút trạng thái mới.

Không có trạng thái bắt đầu nhưng các luật chuyển cho ký hiệu hằng (nút lá) có thể được coi là các luật bắt đầu. Cây được chấp nhận nếu trạng thái ở gốc là một trạng thái chấp nhận.

Một ôtômat hữu hạn trên xuống trên formula_2 được định nghĩa bởi:
formula_9

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

==Liên kết ngoài==
- (OCaml) Grappa - Ranked and Unranked Tree Automata Libraries (http://www.grappa.univ-lille3.fr/~filiot/tata/)
- (OCaml) Timbuk - Tools for Reachability Analysis and Tree Automata Calculations (http://www.irisa.fr/celtique/genet/timbuk/)
- (Java) LETHAL - Library for working with finite tree and hedge automata (http://lethal.sf.net/)
- (Isabelle [OCaml, SML, Haskell]) - Machine-Checked Tree Automata Library (http://afp.sourceforge.net/entries/Tree-Automata.shtml )
- (C++) VATA: A Library for Efficient Manipulation of Non-Deterministic Tree Automata - (http://www.fit.vutbr.cz/research/groups/verifit/tools/libvata/)