Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T13:25:13.855Z Has data issue: false hasContentIssue false

Theory of finite or infinite trees revisited

Published online by Cambridge University Press:  12 May 2008

KHALIL DJELLOUL
Affiliation:
Faculty of computer science, University of Ulm, Germany
THI-BICH-HANH DAO
Affiliation:
Laboratoire d'informatique fondamentale d'Orleans, Universite d'Orleans, France
THOM FRÜHWIRTH
Affiliation:
Faculty of computer science, University of Ulm, Germany
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We present in this paper a first-order axiomatization of an extended theory T of finite or infinite trees, built on a signature containing an infinite set of function symbols and a relation finite(t), which enables to distinguish between finite and infinite trees. We show that T has at least one model and prove its completeness by giving not only a decision procedure, but a full first-order constraint solver that gives clear and explicit solutions for any first-order constraint satisfaction problem in T. The solver is given in the form of 16 rewriting rules that transform any first-order constraint ϕ into an equivalent disjunction φ of simple formulas such that φ is either the formula true or the formula false or a formula having at least one free variable, being equivalent neither to true nor to false and where the solutions of the free variables are expressed in a clear and explicit way. The correctness of our rules implies the completeness of T. We also describe an implementation of our algorithm in CHR (Constraint Handling Rules) and compare the performance with an implementation in C++ and that of a recent decision procedure for decomposable theories.

Information

Type
Regular Papers
Copyright
Copyright © Cambridge University Press 2008