DROPS

Document

DOI: 10.4230/LIPIcs.RTA.2012.256

Turing-Completeness of Polymorphic Stream Equation Systems

Authors: Christian Sattler and Florent Balestrieri

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

Abstract

Polymorphic stream functions operate on the structure of streams, infinite sequences of elements, without inspection of the contained data, having to work on all streams over all signatures uniformly. A natural, yet restrictive class of polymorphic stream functions comprises those definable by a system of equations using only stream constructors and destructors and recursive calls. Using methods reminiscent of prior results in the field, we first show this class consists of exactly the computable polymorphic stream functions. Using much more intricate techniques, our main result states this holds true even for unary equations free of mutual recursion, yielding an elegant model of Turing-completeness in a severely restricted environment and allowing us to recover previous complexity results in a much more restricted setting.

Cite as

Christian Sattler and Florent Balestrieri. Turing-Completeness of Polymorphic Stream Equation Systems. In 23rd International Conference on Rewriting Techniques and Applications (RTA'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 15, pp. 256-271, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{sattler_et_al:LIPIcs.RTA.2012.256,
  author =	{Sattler, Christian and Balestrieri, Florent},
  title =	{{Turing-Completeness of Polymorphic Stream Equation Systems}},
  booktitle =	{23rd International Conference on Rewriting Techniques and Applications (RTA'12)},
  pages =	{256--271},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2012.256},
  URN =		{urn:nbn:de:0030-drops-34970},
  doi =		{10.4230/LIPIcs.RTA.2012.256},
  annote =	{Keywords: turing-completeness, polymorphic stream functions}
}

Search Results

Documents authored by Balestrieri, Florent

Turing-Completeness of Polymorphic Stream Equation Systems

Abstract

Cite as

Thanks for your feedback!

Could not send message