A Confluent Rewriting System Having No Computable, One-Step, Normalizing Strategy

DOI10.1145/2699917zbMath1354.68144OpenAlexW2085574851MaRDI QIDQ2946765

Jakob Grue Simonsen

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2699917

zbMATH Keywords

normalizationrewritingcomputabilityChurch-Rosser propertyreduction strategy

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Combinatory logic and lambda calculus (03B40)

Cites Work

• Unnamed Item
• Unnamed Item
• A sequential reduction strategy
• Simulation of Turing machines by a regular rewrite rule
• Termination of term rewriting: Interpretation and type elimination
• Sequential evaluation strategies for parallel-or and related reduction systems
• Relative undecidability in term rewriting. II: The confluence hierarchy
• Reduction Strategies and Acyclicity
• A variant of a recursively unsolvable problem

This page was built for publication: A Confluent Rewriting System Having No Computable, One-Step, Normalizing Strategy