Coinductive counting with weighted automata and continued fractions - part 1

We shall elaborate on Sections 13-17 of the recently appeared CWI report

Elements of stream calculus (an extensive exercise in coinduction) SEN-R0120

by treating a number of additional examples of what could be called `coinductive counting'.

The main ideas are to enumerate the structures to be counted (such as binary trees, subset partitions, and the like) in the form of a tree-shaped weighted automaton; then to simplify that automaton (up to stream bisimulation); in order to finally obtain a closed expression for the stream of counts (for instance, the stream of natural numbers of possible partitions of sets consisting of 0,1,2, ... elements).

In contrast to this operational-semantics type of counting, we shall also look briefly at an alternative approach, which is in some respect analogous to the denotational or domain-theoretic style of semantics.  

hosted by

social