Relative undecidability in term rewriting. I: The termination hierarchy
type: Item
instance of: scholarly article
title: Relative undecidability in term rewriting. I: The termination hierarchy
zbMATH Open document ID: 1012.68096
author: Alfons Geser
author: Aart Middeldorp
author: Enno Ohlebusch
author: Hans Zantema
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 03D35
zbMATH DE Number: 1853285
MaRDI profile type: Publication
full work available at URL: inco.2002.3120
OpenAlex ID: W2312503573
cites work: Term Rewriting and All That
cites work: Q4263809
cites work: Simulation of Turing machines by a regular rewrite rule
cites work: Total termination of term rewriting
cites work: Omega-termination is undecidable for totally terminating term rewriting systems
cites work: Relative undecidability in term rewriting. II: The confluence hierarchy
cites work: Q4362915
cites work: Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
cites work: On termination of one rule rewrite systems
cites work: Q4225065
cites work: The order types of termination orderings on monadic terms, strings and multisets
cites work: Simple termination is difficult
cites work: Q4705617
cites work: Simple termination of rewrite systems
cites work: The undecidability of self-embedding for term rewriting systems
cites work: A variant of a recursively unsolvable problem
cites work: Termination of term rewriting: Interpretation and type elimination
cites work: Total termination of term rewriting is undecidable
cites work: Non-Looping String Rewriting
DOI: 10.1006/INCO.2002.3120
Recommended article: Q4362915
Recommended article: Relative undecidability in term rewriting. II: The confluence hierarchy
Recommended article: Degrees of Undecidability in Term Rewriting
Recommended article: The termination hierarchy for term rewriting
Recommended article: New Undecidability Results for Properties of Term Rewrite Systems
Recommended article: Total termination of term rewriting is undecidable
Recommended article: The undecidability of self-embedding for term rewriting systems
Recommended article: Q3336681
Recommended article: Decidability of reachability for disjoint union of term rewriting systems
Recommended article: A Hierarchy of Semantics for Non-deterministic Term Rewriting Systems ∗
description: scientific article; zbMATH DE number 1853285