Complete axiomatizations of the algebras of finite, rational and infinite trees
Top Cited Papers
- 6 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 348-357
- https://doi.org/10.1109/lics.1988.5132
Abstract
Complete axiomizations for the algebras of infinite trees and infinite trees are presented. The axiomizations are parameterized by the alphabet of function symbols for both the finite trees and infinite trees. There are two main cases, depending on whether the number of function symbols is finite or infinite. In the former case an extra axiom is necessary to obtain completeness. The method of proof is an elimination of quantifiers. Although a full elimination of quantifiers is not possible, the method forms the basis of decision procedures for the theories of the corresponding algebras. As a corollary to the results in infinite trees, the elementary equivalence of the algebra of rational trees and the algebra of infinite trees is obtained.Keywords
This publication has 0 references indexed in Scilit: