Levels of undecidability in rewriting
type: Item
instance of: scholarly article
title: Levels of undecidability in rewriting
zbMATH Open document ID: 1210.68064
author: Jörg Endrullis
author: Herman Geuvers
author: Jakob Grue Simonsen
author: Hans Zantema
published in: Information and Computation
publication date: 2011-02-21T00:00:00Z
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 03D35
zbMATH DE Number: 5853780
zbMATH Keywords: first order term rewriting systems
zbMATH Keywords: classification
zbMATH Keywords: hierarchy
zbMATH Keywords: properties related to normalization
zbMATH Keywords: properties related to confluence
MaRDI profile type: Publication
full work available at URL: j.ic.2010.09.003
OpenAlex ID: W2128968863
cites work: Q4520528
cites work: Termination of term rewriting using dependency pairs
cites work: Conditional rewrite rules: Confluence and termination
cites work: THE WORD PROBLEM
cites work: Q3795205
cites work: Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
cites work: Degrees of Undecidability in Term Rewriting
cites work: Models of computation. An introduction to computability theory
cites work: Omega-termination is undecidable for totally terminating term rewriting systems
cites work: Relative undecidability in term rewriting. I: The termination hierarchy
cites work: Relative undecidability in term rewriting. II: The confluence hierarchy
cites work: Logic for Programming, Artificial Intelligence, and Reasoning
cites work: Strong Computability and Variants of the Uniform Halting Problem
cites work: Q4146722
cites work: Decidable approximations of term rewriting systems
cites work: Reachability and confluence are undecidable for flat term rewriting systems
cites work: Conditional rewrite rules
cites work: Undecidable properties of syntactic theories
cites work: Recursive Predicates and Quantifiers
cites work: Arithmetical Predicates and Function Quantifiers
cites work: Hierarchies of number-theoretic predicates
cites work: Q4023825
cites work: Q3012528
cites work: Q4942157
cites work: Q5583066
cites work: Simple termination is difficult
cites work: Decidability for left-linear growing term rewriting systems.
cites work: Q5573961
cites work: Q5537599
cites work: The $\Pi^0_2$ -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)
cites work: Q3392275
cites work: Q4799892
cites work: Q4938608
cites work: A new decidability technique for ground term rewriting systems with applications
cites work: Termination of term rewriting: Interpretation and type elimination
cites work: Total termination of term rewriting is undecidable
cites work: Normalization of Infinite Terms
DOI: 10.1016/J.IC.2010.09.003
description: scientific article; zbMATH DE number 5853780