Nijmegen

After ten successful meetings in 2010, the streams seminar will be continued in 2011. It is organized by Herman Geuvers, Jan Willem Klop, Jan Rutten and Hans Zantema, at the Radboud University Nijmegen (in between the two streams Maas and Waal).

The meetings will be in the Huygens gebouw, Heyendaalseweg 135, Nijmegen How to get there?

date | time | room | speaker | title |
---|---|---|---|---|

Tuesday, January 25, 2011 | 13:30 - 15:30 | HG02.032 | Wieb Bosma | Automatic sequences slides |

Tuesday, February 22, 2011 | 10:30 - 11:15 | HG00.023 | Frits Dannenberg | On Toeplitz substitutions and transducer equivalence abstract |

11:30 - 12:30 | HG00.023 | Frank Staals | Stream equality in Coq | |

Tuesday, May 10, 2011 | 13:30 - 14:30 | HG02.028 | Rudolf Mak (TU/e) | Periodic-Drop-Take Calculus for Stream Transformers slides |

14:30 - 15:30 | HG02.028 | Joost Winter (CWI) | Context-free languages and streams slides |

Stream transformers are a formalism to specify and reason about stream processing systems. Many application specific circuits, e.g. in the area of digital signal processing , classify as such systems. We present a two operator calculus to reason about a specific class of stream operators, viz. the periodic stream samplers. The calculus is sound and complete and an algorithm using only a few rules is given to bring each operator sequence in canonical form. As an example, we apply the calculus to show FIFO behavior of a class of circuits built from three simple components exhibiting repetitive behavior. In addition, we briefly discuss an extended version of the calculus suitable to reason about linear filters. Also the usage of the calculus for periodic scheduling purposes is sketched.

The meetings are open to both students and researchers. Suggestions for talks will be welcome.

A stream over a data set A is an infinite sequence of elements from A, that is, a mapping from the natural numbers to A.

Streams form the simplest data type in which the objects themselves are infinite. Thus arises the issue of representation: where finite objects can be described by their syntax, for infinite objects such as streams, we need finite representations, together with notions of equality to state that two finite representations represent the same infinite object.

Where the natural numbers form one of the simplest (initial) algebras where an induction principle comes in, streams form a canonical example of a (final) co-algebra for which a co-induction principle holds. Thus streams form a fundamental data structure for which a basic understanding is worthwhile.

The foundations of streams will be studied and discussed from several different perspectives, including term rewriting and co-algebra. Also, we shall be interested in understanding streams in the various contexts where they are applied, in both computer science and mathematics. Examples include semantics, data flow, signal processing, analysis, real number arithmetic. Finally, tools supporting automated reasoning about streams will have our attention too.

The last years have seen several new developments in defining and understanding streams, amongst others in the context of the NWO/BRICKS project INFINITY, a collaboration of the Free University in Amsterdam, Utrecht University and CWI, and in the context of the Foundations group at the Radboud University in Nijmegen.

date | time | room | speaker | title |
---|---|---|---|---|

Monday, January 18 | 14:00 - 14:50 | HG01.058 | Jan Rutten | Streams from a co-algebraic perspective slides |

Monday, January 18 | 15:10 - 16:00 | HG01.058 | Helle Hansen | Stream functions from a co-algebraic perspective slides |

Monday, February 22 | 14:00 - 16:00 | HG00.058 | Hans Zantema | Streams from a rewriting perspective slides |

Monday, March 15 | 14:00 - 16:00 | HG00.062 | Herman Geuvers | Streams in Coq slides |

Tuesday, April 20 | 13:30 - 15:30 | HG01.058 | Dimitri Hendriks, Joerg Endrullis, Jan Willem Klop | Classifying streams slides JWK, slides DH, slides JE |

Monday, May 17 | 14:00 - 16:00 | HG02.028 | Peter Hancock (MSFP, Strathclyde Univ. Scotland) | Streams from a type-theoretic perspective slides |

Monday, June 21 | 14:00 - 16:00 | HG02.028 | Bas Spitters | Quantification over streams |

Monday, September 6 | 13:30 - 14:30 | HG00.065 | Jan Rutten | Stream differential equations |

Monday, September 6 | 14:30 - 15:30 | HG00.065 | Milad Niqui | Streams in Coq |

Monday, October 4 | 13:30 - 15:30 | HG00.065 | Joerg Endrullis and Hans Zantema | Proving equality of streams automatically |

Monday, November 1 | 13:30 - 15:30 | HG00.065 | Herman Geuvers | Representations of real numbers slides |

Tuesday, November 30 | 13:30 - 14:30 | HG02.032 | Wouter Swierstra | Stream Fusion slides |

Last change: May 11, 2011