Thue trees

&
Annals of Pure and Applied Logic 119 (1-3):19-59 (2003)
  Copy   BIBTEX

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 dependencies

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(02)00032-5

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Afscheid van Jaco.Jan van Eijck - unknown
Game Trees For Decision Analysis.Prakash P. Shenoy - 1998 - Theory and Decision 44 (2):149-171.
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 - Baltimore: 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.
Analytic cut trees.Carlo Cellucci - 2000 - Logic Journal of the IGPL 8 (6):733-750.
Trees and Family Trees in the Aeneid.Emily Gowers - 2011 - Classical Antiquity 30 (1):87-118.
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
20 (#747,345)

6 months
3 (#992,474)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Recursive unsolvability of a problem of thue.Emil L. Post - 1947 - Journal of Symbolic Logic 12 (1):1-11.
The classical decision problem.Egon Boerger - 1997 - New York: Springer. Edited by Erich Grädel & Yuri Gurevich.
Unsolvable problems for equational theories.Peter Perkins - 1967 - Notre Dame Journal of Formal Logic 8 (3):175-185.
The unsolvability of the gödel class with identity.Warren D. Goldfarb - 1984 - Journal of Symbolic Logic 49 (4):1237-1252.
The decision problem for standard classes.Yuri Gurevich - 1976 - Journal of Symbolic Logic 41 (2):460-464.

View all 10 references / Add more references