Propositional Tree Automata

Hendrix, Joe; Ohsaki, Hitoshi; Viswanathan, Mahesh

Permalink

https://hdl.handle.net/2142/11168 Copy

Description

Title

Propositional Tree Automata

Author(s)

• Hendrix, Joe
• Ohsaki, Hitoshi
• Viswanathan, Mahesh

Issue Date

2006-02

Keyword(s)

• tree automata
• computer science

Abstract

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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11168

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections