Representations of stream processors using nested fixed points

Tools

Hancock, Peter and Pattinson, Dirk and Ghani, Neil (2009) Representations of stream processors using nested fixed points. Logical Methods in Computer Science, 5 (3). pp. 1-17. 9. (https://doi.org/10.2168/LMCS-5(3:9)2009)

[thumbnail of Logical_methods_in_computer_science.pdf]
Preview
 PDF. Filename: Logical_methods_in_computer_science.pdf
Accepted Author Manuscript
Download (228kB)| Preview

Abstract

We define representations of continuous functions on infinite streams of discrete values, both in the case of discrete-valued functions, and in the case of stream-valued functions. We define also an operation on the representations of two continuous functions between streams that yields a representation of their composite. In the case of discrete-valued functions, the representatives are well-founded (finite-path) trees of a certain kind. The underlying idea can be traced back to Brouwer's justification of bar-induction, or to Kreisel and Troelstra's elimination of choice-sequences. In the case of stream-valued functions, the representatives are non-wellfounded trees pieced together in a coinductive fashion from well-founded trees. The definition requires an alternating fixpoint construction of some ubiquity.

ORCID iDs

Hancock, Peter, Pattinson, Dirk and Ghani, Neil ORCID logoORCID: https://orcid.org/0000-0002-3988-2560;
CORE (COnnecting REpositories)