Undecidable properties of flat term rewrite systems
type: Item
instance of: scholarly article
title: Undecidable properties of flat term rewrite systems
zbMATH Open document ID: 1187.68274
author: Guillem Godoy
author: Hugo Hernández
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 2009-10-19T00:00:00Z
review text: Reachability, joinability, termination or strong normalization, confluence, weak normalization, and unique normalization are some fundamental properties of term rewrite systems (TRS) that are known to be undecidable in general. Their decidablity has been investigated for some particular classes. In this paper, the authors give new simple proofs for the undecidability of reachability, joinability, and confluence for flat TRS. They also give proofs for the undecidability of weak and unique normalizations for flat TRS.
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 5617928
zbMATH Keywords: term rewriting
zbMATH Keywords: syntactic restrictions
zbMATH Keywords: undecidability
reviewed by: F. Blanchet-Sadri
MaRDI profile type: Publication
full work available at URL: s00200-009-0097-1
OpenAlex ID: W2095909184
cites work: Term Rewriting and All That
cites work: Termination of Rewriting with Right-Flat Rules
cites work: On the Normalization and Unique Normalization Properties of Term Rewrite Systems
cites work: Automated Reasoning
cites work: Computer Science Logic
cites work: Q4418639
cites work: Reachability and confluence are undecidable for flat term rewriting systems
cites work: The Confluence Problem for Flat TRSs
cites work: Decidability for left-linear growing term rewriting systems.
cites work: Q3392275
cites work: Q2723905
cites work: Decidability of Termination for Semi-constructor TRSs, Left-Linear Shallow TRSs and Related Systems
DOI: 10.1007/S00200-009-0097-1
Recommended article: Reachability and confluence are undecidable for flat term rewriting systems
Recommended article: New Undecidability Results for Properties of Term Rewrite Systems
Recommended article: Undecidable properties on length-two string rewriting systems
Recommended article: Q4362915
Recommended article: Degrees of Undecidability in Term Rewriting
Recommended article: The undecidability of self-embedding for term rewriting systems
Recommended article: Relative undecidability in term rewriting. I: The termination hierarchy
Recommended article: Total termination of term rewriting is undecidable
Recommended article: Q4065053
Recommended article: Undecidable properties of deterministic top-down tree transducers
description: scientific article; zbMATH DE number 5617928