1 Search Results for "Andersen, Soren Bjerg"

Document
DOI: 10.4230/LIPIcs.RTA.2012.53
Term Rewriting Systems as Topological Dynamical Systems

Authors: Soren Bjerg Andersen and Jakob Grue Simonsen

Published in: LIPIcs, Volume 15, 23rd International Conference on Rewriting Techniques and Applications (RTA'12) (2012)

Abstract
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.
Cite as

Soren Bjerg Andersen and Jakob Grue Simonsen. Term Rewriting Systems as Topological Dynamical Systems. In 23rd International Conference on Rewriting Techniques and Applications (RTA'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 15, pp. 53-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{andersen_et_al:LIPIcs.RTA.2012.53,
  author =	{Andersen, Soren Bjerg and Simonsen, Jakob Grue},
  title =	{{Term Rewriting Systems as Topological Dynamical Systems}},
  booktitle =	{23rd International Conference on Rewriting Techniques and Applications (RTA'12)},
  pages =	{53--68},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-38-5},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{15},
  editor =	{Tiwari, Ashish},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2012.53},
  URN =		{urn:nbn:de:0030-drops-34841},
  doi =		{10.4230/LIPIcs.RTA.2012.53},
  annote =	{Keywords: Term rewriting, dynamical systems, topology, symbolic dynamics}
}
  • Refine by Author
  • 1 Andersen, Soren Bjerg
  • 1 Simonsen, Jakob Grue

  • Refine by Classification

  • Refine by Keyword
  • 1 Term rewriting
  • 1 dynamical systems
  • 1 symbolic dynamics
  • 1 topology

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2012

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact