Term rewriting systems as topological dynamical systems

TY - GEN

T1 - Term rewriting systems as topological dynamical systems

AU - Andersen, Søren Bjerg

AU - Simonsen, Jakob Grue

N1 - Conference code: 23

PY - 2012

Y1 - 2012

N2 - Topological dynamics is, roughly, the study of phenomena related to iterations of continuous maps from a metric space to itself. We show how the rewrite relation in term rewriting gives rise to dynamical systems in two distinct, natural ways: (A) One in which any deterministic rewriting strategy induces a dynamical system on the set of finite and infinite terms endowed with the usual metric, and (B) one in which the unconstrained rewriting relation induces a dynamical system on sets of sets of terms, specifically the set of compact subsets of the set of finite and infinite terms endowed with the Hausdorff metric. For both approaches, we give sufficient criteria for the induced systems to be well-defined dynamical systems and for (A) we demonstrate how the classic topological invariant called topological entropy turns out to be much less useful in the setting of term rewriting systems than in symbolic dynamics.

AB - Topological dynamics is, roughly, the study of phenomena related to iterations of continuous maps from a metric space to itself. We show how the rewrite relation in term rewriting gives rise to dynamical systems in two distinct, natural ways: (A) One in which any deterministic rewriting strategy induces a dynamical system on the set of finite and infinite terms endowed with the usual metric, and (B) one in which the unconstrained rewriting relation induces a dynamical system on sets of sets of terms, specifically the set of compact subsets of the set of finite and infinite terms endowed with the Hausdorff metric. For both approaches, we give sufficient criteria for the induced systems to be well-defined dynamical systems and for (A) we demonstrate how the classic topological invariant called topological entropy turns out to be much less useful in the setting of term rewriting systems than in symbolic dynamics.

U2 - 10.4230/LIPIcs.RTA.2012.53

DO - 10.4230/LIPIcs.RTA.2012.53

M3 - Article in proceedings

SN - 978-3-939897-38-5

SP - 53

EP - 68

BT - 23rd International Conference on Rewriting Techniques and Applications (RTA'12)

A2 - Tiwari, Ashish

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 23rd International Conference on Rewriting Techniques and Applications

Y2 - 28 May 2012 through 2 June 2012

ER -