Propositional Tree Automata | Zendy

Joe Hendrix | Zendy; Hitoshi Ohsaki | Zendy; Mahesh Viswanathan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Propositional Tree Automata

Author(s) -

Joe Hendrix,

Hitoshi Ohsaki,

Mahesh Viswanathan

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-36834-5

DOI - 10.1007/11805618_5

Subject(s) - undecidable problem , tree automaton , decidability , tree (set theory) , automaton , emptiness , discrete mathematics , computer science , rewriting , mathematics , automata theory , theoretical computer science , programming language , combinatorics , philosophy , theology

In the paper, we introduce a new tree automata framework, called propositional tree automata, capturing the class of tree languages that are closed under an equational theory and Boolean operations. This framework originates in work on developing a sucient completeness checker for specifications with rewriting modulo an equational theory. Propositional tree automata recognize regular equational tree languages. However, unlike regular equational tree automata, the class of proposi- tional tree automata is closed under Boolean operations. This extra ex- pressiveness does not aect the decidability of the membership problem. This paper also analyzes in detail the emptiness problem for proposi- tional tree automata with associative theories. Though undecidable in general, we present a semi-algorithm for checking emptiness based on machine learning that we have found useful in practice.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research