Streams Seminar


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?

Presentations in 2011:

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

Abstract of presentation on May 10 by Rudolf Mak:
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.

The subject:

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.

Past presentations in 2010:

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