Propositional tree automata

Joe Hendrix, Hitoshi Ohsaki, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationTerm Rewriting and Applications - 17th International Conference, RTA 2006, Proceedings
Number of pages16
ISBN (Print)3540368345, 9783540368342
StatePublished - 2006
Event17th International Conference on Term Rewriting and Applications, RTA 2006 - Seattle, WA, United States
Duration: Aug 12 2006Aug 14 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4098 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other17th International Conference on Term Rewriting and Applications, RTA 2006
Country/TerritoryUnited States
CitySeattle, WA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Propositional tree automata'. Together they form a unique fingerprint.

Cite this