Coalgebraic Characterizations of Automata-Theoretic Classes

Joost Winter

Promotor: prof.dr. J.J.M.M. Rutten (RU and CWI)
Co-promotor: dr. M.M. Bonsangue (UL)
Radboud Universiteit Nijmegen
Date: 1 July, 2014, 14:30


Automata theory is the area within theoretical computer science in which abstract machines, or automata, are studied. Automata theory is closely connected with the study of formal languages, and the classes of formal languages that can be described or recognized by various types of automata or formal grammars. Important instances of such classes are the regular and context-free languages, which together form the first two levels of the Chomsky hierarchy.

In this dissertation, various automata-theoretic classes are studied from a coalgebraic point of view. Coalgebra offers an abstract view on a variety of state based systems, rooted in category theory, the field of mathematics abstractly studying the structural correspondences between various mathematical theories.

Another example of automata-theoretic classes studied in this dissertation, besides formal languages, is constituted by streams, i.e. infinite sequences that are described coinductively. On an even more general level, we study classes of formal power series in non-commuting variables, of which both formal languages and streams can be seen as instances. Such coinductive descriptions, in general, take the shape of behavioural differential equations. Commonly, direct correspondences can be given between the various formats of behavioural differential equations, and the various automata-theoretical classes.

Such classes include the regular languages (generalizing to the rational power series), of which we recall the (already existing) coalgebraic presentation in Chapter 2; the context-free languages (generalizing to algebraic power series), presented in Chapter 3, and the k-automatic and k-regular sequences, which have been introduced by Allouche and Shallit, in Chapter 5.

Furthermore, we approach a part of the earlier material from a bialgebraic perspective, and establish a connection to the abstract framework of lambda-bialgebras and distributive laws. In particular, we look at several methods in which we can synthesize the work in Chapter 3 and the bialgebraic approach from Jacobs, Bartels et al., and discuss the problems encountered when doing this.

Finally, an implementation of the coinductive calculus of streams in the functional programming language Haskell is given, in which the formats presented in the earlier chapters can be described. Connecting to this, in Appendix C the material from the earlier chapters is illustrated by a variety of examples of infinite sequences, which can be described coinductively as streams.