University of Illinois Urbana-Champaign

Propositional Tree Automata

Hendrix, Joe; Ohsaki, Hitoshi; Viswanathan, Mahesh

Content Files
Propositional Tree Automata.pdf

Permalink

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

Description

Title
Propositional Tree Automata
Author(s)
  • Hendrix, Joe
  • Ohsaki, Hitoshi
  • Viswanathan, Mahesh
Issue Date
2006-02
Keyword(s)
  • tree automata
  • computer science
Date of Ingest
2009-04-20T19:49:18Z
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
Genre of Resource
Technical Report
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

Research and Tech Reports - Computer Science PRIMARY