Trace rewriting: Computing normal forms in time O(n log n)

DOI10.1007/3-540-60922-9_23MaRDI QIDQ4593937zbMATH OpenOpenAlexFDO

Authors Michael Bertol, Volker Diekert

Publication date 16 November 2017

Published in STACS 96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60922-9_23

zbMATH Keywords

Mazurkiewicz tracesrewriting modulo a partial commutation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42)

Recommendations

• Compact normalisation trace via lazy rewriting
• Complexity of Normal Form Properties and Reductions for Term Rewriting Problems Complexity of Normal Form Properties and Reductions for Term Rewriting Problems
• scientific article; zbMATH DE number 4199606
• Runtime complexity analysis of logically constrained rewriting
• Feasible Trace Reconstruction for Rewriting Approximations
• Transforming derivational complexity of term rewriting to runtime complexity
• Deciding confluence and normal form properties of ground term rewrite systems efficiently
• scientific article; zbMATH DE number 23844
• Normal forms and normal theories in conditional rewriting
• Normalization properties for shallow TRS and innermost rewriting

Cited in

(3)

• Confluence problems for trace rewriting systems
• scientific article; zbMATH DE number 522832 (Why is no real title available?)
• Efficient rewriting in cograph trace monoids

This page was built for publication: Trace rewriting: Computing normal forms in time O(n log n)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593937)