Propositional tree automata

Joe Hendrix; Hitoshi Ohsaki; Mahesh Viswanathan

doi:10.1007/11805618_5

Propositional tree automata

Joe Hendrix, Hitoshi Ohsaki, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Term Rewriting and Applications - 17th International Conference, RTA 2006, Proceedings
Publisher	Springer
Pages	50-65
Number of pages	16
ISBN (Print)	3540368345, 9783540368342
DOIs	https://doi.org/10.1007/11805618_5
State	Published - 2006
Event	17th International Conference on Term Rewriting and Applications, RTA 2006 - Seattle, WA, United States Duration: Aug 12 2006 → Aug 14 2006

Publication series

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

Other

Other	17th International Conference on Term Rewriting and Applications, RTA 2006
Country/Territory	United States
City	Seattle, WA
Period	8/12/06 → 8/14/06

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/11805618_5

Library availability

Discover UIUC Full Text

Cite this

Hendrix, J., Ohsaki, H., & Viswanathan, M. (2006). Propositional tree automata. In Term Rewriting and Applications - 17th International Conference, RTA 2006, Proceedings (pp. 50-65). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4098 LNCS). Springer. https://doi.org/10.1007/11805618_5

Propositional tree automata. / Hendrix, Joe; Ohsaki, Hitoshi; Viswanathan, Mahesh.
Term Rewriting and Applications - 17th International Conference, RTA 2006, Proceedings. Springer, 2006. p. 50-65 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4098 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hendrix, J, Ohsaki, H & Viswanathan, M 2006, Propositional tree automata. in Term Rewriting and Applications - 17th International Conference, RTA 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4098 LNCS, Springer, pp. 50-65, 17th International Conference on Term Rewriting and Applications, RTA 2006, Seattle, WA, United States, 8/12/06. https://doi.org/10.1007/11805618_5

@inproceedings{56841b78d09344dca1d0087eb26dcc3d,

title = "Propositional tree automata",

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.",

author = "Joe Hendrix and Hitoshi Ohsaki and Mahesh Viswanathan",

year = "2006",

doi = "10.1007/11805618_5",

language = "English (US)",

isbn = "3540368345",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "50--65",

booktitle = "Term Rewriting and Applications - 17th International Conference, RTA 2006, Proceedings",

address = "Germany",

note = "17th International Conference on Term Rewriting and Applications, RTA 2006 ; Conference date: 12-08-2006 Through 14-08-2006",

}

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 -

Propositional tree automata

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this