Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Representations of stream processors using nested fixed points

Hancock, P. and Pattinson, D. and Ghani, N. (2009) Representations of stream processors using nested fixed points. Logical Methods in Computer Science, 5 (3).

PDF (Logical_methods_in_computer_science.pdf)

Download (228kB) | Preview


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.

Item type: Article
ID code: 18887
Keywords: streams, continuous functions, initial algebras, final coalgebras, Electronic computers. Computer science, Computer Science(all), Theoretical Computer Science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Depositing user: Strathprints Administrator
Date Deposited: 20 May 2010 08:43
Last modified: 21 Jul 2015 14:36

Actions (login required)

View Item View Item