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).

[img]
Preview
PDF (Logical_methods_in_computer_science.pdf)
Download (223Kb) | 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.

    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
    Related URLs:
      Depositing user: Strathprints Administrator
      Date Deposited: 20 May 2010 09:43
      Last modified: 05 Sep 2014 13:30
      URI: http://strathprints.strath.ac.uk/id/eprint/18887

      Actions (login required)

      View Item

      Fulltext Downloads: