A refinement of strong sequentiality for term rewriting with constructors
type: Item
instance of: scholarly article
title: A refinement of strong sequentiality for term rewriting with constructors
zbMATH Open document ID: 0628.68033
DOI: 10.1016/0890-5401(87)90050-2
author: B. George
published in: Information and Computation
publication date: 1987-01-01T00:00:00Z
full work available at URL: http://hdl.handle.net/2027.42/26861
review text: The paper introduces a refined version of strong sequentiality for term rewriting systems, and this version is called left sequentiality. The difference is that left sequentiality is based on possible rather than arbitrary sequences of reductions. The results of the paper indicate that the left and strong sequentiality coincide when considered as properties of admissible sets of left-hand sides for systems of equations, but that left sequentiality is more general when applied to individual terms. It is shown that, improving on Huet and Levy's result, there is no redex selection algorithm which is safe for all systems based on a set of left- hand sides if that set is not left sequential.
Mathematics Subject Classification ID: 68Q65
zbMATH DE Number: 4022631
zbMATH Keywords: sequential system
zbMATH Keywords: constructor system
zbMATH Keywords: redex selection algorithm
zbMATH Keywords: strong sequentiality
zbMATH Keywords: term rewriting systems
zbMATH Keywords: left sequentiality
reviewed by: Gabriel Ciobanu
MaRDI profile type: Publication
OpenAlex ID: W2064305670
cites work: Implementation of an interpreter for abstract equations
cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
cites work: Q4138147
cites work: Q5581665
cites work: Q3875320
cites work: A Machine-Oriented Logic Based on the Resolution Principle
cites work: Q3959414
cites work: On the correspondence between two classes of reduction systems
cites work: A new implementation technique for applicative languages
description: scientific article; zbMATH DE number 4022631