We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
HANDLING NON LEFT-LINEAR RULES WHEN COMPLETING TREE AUTOMATA.
- Authors
BOICHUT, YOHAN; COURBIS, ROMEO; HEAM, PIERRE-CYRILLE; KOUCHNARENKO, OLGA
- Abstract
This paper addresses the following general problem of tree regular model-checking: decide whether $\mathcal{R}^*(\mathcal{L})\cap \mathcal{L}_p =\emptyset$ where $\mathcal{R}^*$ is the reflexive and transitive closure of a successor relation induced by a term rewriting system $\mathcal{R}$, and $\mathcal{L}$ and $\mathcal{L}_p$ are both regular tree languages. We develop an automatic approximation-based technique to handle this – undecidable in general – problem in the case when term rewriting system rules are non left-linear.
- Subjects
TREES; LANGUAGE &; languages; MACHINE theory; THEORY of self-knowledge; REWRITING systems (Computer science); APPROXIMATION theory
- Publication
International Journal of Foundations of Computer Science, 2009, Vol 20, Issue 5, p837
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054109006917