On Causal Equivalence by Tracing in String Rewriting

Autor:	van Oostrom, Vincent
Rok vydání:	2023
Předmět:	Computer Science - Logic in Computer Science
Zdroj:	EPTCS 377, 2023, pp. 27-43
Druh dokumentu:	Working Paper
DOI:	10.4204/EPTCS.377.2
Popis:	We introduce proof terms for string rewrite systems and, using these, show that various notions of equivalence on reductions known from the literature can be viewed as different perspectives on the notion of causal equivalence. In particular, we show that permutation equivalence classes (as known from the lambda-calculus and term rewriting) are uniquely represented both by trace graphs (known from physics as causal graphs) and by so-called greedy multistep reductions (as known from algebra). We present effective maps from the former to the latter, topological multi-sorting TM, and vice versa, the proof term algebra [[ ]]. Comment: In Proceedings TERMGRAPH 2022, arXiv:2303.14219
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2303.15783 Zobrazit plný text záznamu View this record from Arxiv