From automata theory to coinduction with Haskell

Prelegent(ci)

Joost Winter

Termin

27 maja 2020 14:15

Informacje na temat wydarzenia

Online seminar

Seminarium

Seminarium „Teoria automatów”

---

In this talk I will approach a topic from classical automata theory, 
power series in a single input variable, from the point of view of
coinductive specifications in the functional language Haskell,
which are easy to specify and use due to Haskell's feature of lazy
evaluation. In this coinductive world, these power series become
known as streams. We will show two ways in which traditional
specifications of rational and recognizable series can be transformed
into single line specifications in Haskell. One of these ways is based
on Gérard Jacob's characterization of recognizable series as those
power series which are an element of a finitely generated and stable
subspace of the space of all power series. The second way is directly
based on rational expressions, and makes use of the duality between
the star and inverse operators. If time allows, I will tell a bit about
extensions of algebraic power series, which relate to context-free
languages in the same way that rational power series relate to regular languages.

 

---