Abstract
We show that the positive existential fragment of the theory of tree embedding is decidable.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Hubert Comon. Solving symbolic ordering constraints. International Journal of Foundations of Computer Science, 1(4), 1990.
Hubert Comon. Disunification: a survey. In Jean-Louis Lassez and Gordon Plotkin, editors, Computational Logic: Essays in Honor of Alan Robinson. MIT Press, 1991.
Nachum Dershowitz and Jean-Pierre Jouannaud. Rewrite systems. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 243–309. North-Holland, 1990.
Graham Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society, 2(3):326–336, September 1952.
Jean-Pierre Jouannaud and Claude Kirchner. Solving equations in abstract algebras: A rule-based survey of unification. In Jean-Louis Lassez and Gordon Plotkin, editors, Computational Logic: Essays in Honor of Alan Robinson. MIT-Press, 1991.
Jean-Pierre Jouannaud and Mitsuhiro Okada. Satisfiability of systems of ordinal notations with the subterm property is decidable. In Proc. 18th Int. Coll. on Automata, Languages and Programming, Madrid, LNCS 510, 1991.
R. Nieuwenhuis and A. Rubio. Theorem proving with ordering constrained clauses. In Deepak Kapur, editor, Proc. 11th Int. Conf. on Automated Deduction, Saratoga Springs, NY, LNCS 607. Springer-Verlag, June 1992.
Ralf Treinen. A new method for undecidability proofs of first order theories. Tech. Report A-09/90, Universität des Saarladandes, Saarbrücken, May 1990.
Sauro Tulipani. Decidability of the existential theory of infinite terms with subterm relation. To appear in Information and Computation, 1991.
K. N. Venkataraman. Decidability of the purely existential fragment of the theory of term algebras. Journal of the ACM, 34(2):492–510, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boudet, A., Comon, H. (1993). About the theory of tree embedding. In: Gaudel, M.C., Jouannaud, J.P. (eds) TAPSOFT'93: Theory and Practice of Software Development. CAAP 1993. Lecture Notes in Computer Science, vol 668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56610-4_77
Download citation
DOI: https://doi.org/10.1007/3-540-56610-4_77
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56610-6
Online ISBN: 978-3-540-47598-9
eBook Packages: Springer Book Archive