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: 93,990

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

Local coherence.Bernhard König - 2003 - Annals of Pure and Applied Logic 124 (1-3):107-139.
Applications of cohomology to set theory II: Todorčević trees.Daniel E. Talayco - 1996 - Annals of Pure and Applied Logic 77 (3):279-299.
On the existence of indiscernible trees.Kota Takeuchi & Akito Tsuboi - 2012 - Annals of Pure and Applied Logic 163 (12):1891-1902.
Inductive theorem proving based on tree grammars.Sebastian Eberhard & Stefan Hetzl - 2015 - Annals of Pure and Applied Logic 166 (6):665-700.
A term rewriting characterization of the functions computable in polynomial space.Isabel Oitavem - 2002 - Archive for Mathematical Logic 41 (1):35-47.
A microscopic approach to Souslin-tree construction, Part II.Ari Meir Brodsky & Assaf Rinot - 2021 - Annals of Pure and Applied Logic 172 (5):102904.
Undecidability and 1-types in the recursively enumerable degrees.Klaus Ambos-Spies & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 63 (1):3-37.
Kripke models for classical logic.Danko Ilik, Gyesik Lee & Hugo Herbelin - 2010 - Annals of Pure and Applied Logic 161 (11):1367-1378.
A new characterization of supercompactness and applications.Qi Feng - 2009 - Annals of Pure and Applied Logic 160 (2):192-213.
Linear logic as a logic of computations.Max I. Kanovich - 1994 - Annals of Pure and Applied Logic 67 (1-3):183-212.

Analytics

Added to PP
2014-01-16

Downloads
23 (#672,256)

6 months
6 (#700,872)

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