- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Thue trees
Annals of Pure and Applied Logic 119 (1-3):19-59 (2003)
Abstract
In this paper we introduce a new technique of proving undecidability results. This technique is based on the notion of a Thue tree. We also give examples of applications of this method to term rewriting, Horn implication problem and database dependenciesDOI
10.1016/s0168-0072(02)00032-5
My notes
Similar books and articles
On Scott and Karp trees of uncountable models.Tapani Hyttinen & Jouko Väänänen - 1990 - Journal of Symbolic Logic 55 (3):897-908.
Computable Trees of Scott Rank [image] , and Computable Approximation.Wesley Calvert, Julia F. Knight & Jessica Millar - 2006 - Journal of Symbolic Logic 71 (1):283 - 298.
Trees of Life: A Visual History of Evolution.Theodore W. Pietsch - 2012 - Johns Hopkins University Press.
Uniformization, choice functions and well orders in the class of trees.Shmuel Lifsches & Saharon Shelah - 1996 - Journal of Symbolic Logic 61 (4):1206-1227.
Computable Trees of Scott Rank $\omega _{1}^{\mathit{CK}}$ , and Computable Approximation.Wesley Calvert, Julia F. Knight & Jessica Millar - 2006 - Journal of Symbolic Logic 71 (1):283 - 298.
Gregory trees, the continuum, and Martin's axiom.Kenneth Kunen & Dilip Raghavan - 2009 - Journal of Symbolic Logic 74 (2):712-720.
Congruence of morphological and molecular phylogenies.Davide Pisani, Michael J. Benton & Mark Wilkinson - 2007 - Acta Biotheoretica 55 (3):269-281.
Recursive unsolvability of a problem of thue.Emil L. Post - 1947 - Journal of Symbolic Logic 12 (1):1-11.
A first-order axiomatization of the theory of finite trees.Rolf Backofen, James Rogers & K. Vijay-Shanker - 1995 - Journal of Logic, Language and Information 4 (1):5-39.
Results on the Generic Kurepa Hypothesis.R. B. Jensen & K. Schlechta - 1990 - Archive for Mathematical Logic 30 (1):13-27.
Analytics
Added to PP
2014-01-16
Downloads
16 (#676,879)
6 months
1 (#485,425)
2014-01-16
Downloads
16 (#676,879)
6 months
1 (#485,425)
Historical graph of downloads
References found in this work
Recursive unsolvability of a problem of thue.Emil L. Post - 1947 - Journal of Symbolic Logic 12 (1):1-11.
Review: Michael O. Rabin, Decidability of Second-order Theories and Automata on Infinite Trees. [REVIEW]Dirk Siefkes - 1972 - Journal of Symbolic Logic 37 (3):618-619.
The unsolvability of the gödel class with identity.Warren D. Goldfarb - 1984 - Journal of Symbolic Logic 49 (4):1237-1252.
Unsolvable problems for equational theories.Peter Perkins - 1967 - Notre Dame Journal of Formal Logic 8 (3):175-185.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-9c67bdf98-j9wcx N