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. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
  Try with proxy. Try with proxy. Try with proxy. |
| Through your library | Only published papers are available at libraries |
Similar books and articlesMatthias Scheutz (2001). Computational Vs. Causal Complexity. Minds And Machines 11 (4):543-566.
Arto Salomaa (1985). Computation and Automata. Cambridge University Press.
Marcin Mostowski & Jakub Szymanik (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. The Bulletin of Symbolic Logic 13:281--282.
Theodor Leiber (1999). Deterministic Chaos and Computational Complexity: The Case of Methodological Complexity Reductions. Journal for General Philosophy of Science 30 (1):87-101.
Jakub Szymanik (2010). Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language. Linguistics and Philosophy 33 (3):215-250.
P. H. Rodenburg (1998). Termination and Confluence in Infinitary Term Rewriting. Journal of Symbolic Logic 63 (4):1286-1296.
Jakub Szymanik (2009). The Computational Complexity of Quantified Reciprocals. 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.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads9 ( #114,063 of 549,088 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
