Lecture notes on term rewriting and computational complexity

Abstract

The main powerful method for establishing termination of term rewriting systems was discovered by Nachum Dershowitz through the introduction of certain natural well founded orderings (lexicographic path orderings). This leads to natural decision problems which may be of the highest computational complexity of any decidable problems appearing in a natural established computer science context.

Categories

Keywords

Reprint years

Links

PhilArchive



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

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

My notes

Similar books and articles

Computational vs. causal complexity.Matthias Scheutz - 2001 - Minds and Machines 11 (4):543-566.
The Computational Complexity of Quantified Reciprocals.Jakub Szymanik - 2009 - In Peter Bosch, David Gabelaia & Jérôme Lang (eds.), Lecture Notes on Artificial Intelligence 5422, Logic, Language, and Computation 7th International Tbilisi Symposium on Logic, Language, and Computation. Springer.
Termination and confluence in infinitary term rewriting.P. H. Rodenburg - 1998 - Journal of Symbolic Logic 63 (4):1286-1296.
Complexity and postmodernism: understanding complex systems.Paul Cilliers - 1998 - New York: Routledge.
Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language.Jakub Szymanik - 2010 - Linguistics and Philosophy 33 (3):215-250.
Deterministic chaos and computational complexity: The case of methodological complexity reductions. [REVIEW]Theodor Leiber - 1999 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 30 (1):87-101.
A general theorem on termination of rewriting.Jeremy E. Dawson - unknown
Computational complexity of some Ramsey quantifiers in finite models.Marcin Mostowski & Jakub Szymanik - 2007 - Bulletin of Symbolic Logic 13:281--282.
Computation and automata.Arto Salomaa - 1985 - New York: Cambridge University Press.
Some decision problems of enormous complexity.Harvey Friedman - manuscript

Analytics

Added to PP
2009-01-28

Downloads
242 (#79,169)

6 months
1 (#1,346,405)

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

No references found.

Add more references