TY - GEN
T1 - Propositional tree automata
AU - Hendrix, Joe
AU - Ohsaki, Hitoshi
AU - Viswanathan, Mahesh
PY - 2006
Y1 - 2006
N2 - 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 sufficient 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 propositional tree automata is closed under Boolean operations. This extra expressiveness does not affect the decidability of the membership problem. This paper also analyzes in detail the emptiness problem for propositional 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.
AB - 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 sufficient 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 propositional tree automata is closed under Boolean operations. This extra expressiveness does not affect the decidability of the membership problem. This paper also analyzes in detail the emptiness problem for propositional 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.
UR - http://www.scopus.com/inward/record.url?scp=33749399606&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33749399606&partnerID=8YFLogxK
U2 - 10.1007/11805618_5
DO - 10.1007/11805618_5
M3 - Conference contribution
AN - SCOPUS:33749399606
SN - 3540368345
SN - 9783540368342
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 50
EP - 65
BT - Term Rewriting and Applications - 17th International Conference, RTA 2006, Proceedings
PB - Springer
T2 - 17th International Conference on Term Rewriting and Applications, RTA 2006
Y2 - 12 August 2006 through 14 August 2006
ER -