Coinductive counting with weighted automata
A general methodology is developed to compute the solution of a wide variety of basic counting problems in a uniform way: (1) the objects to be counted are enumerated by means of an infinite weighted automaton; (2) the automaton is reduced by means of the quantitative notion of stream bisimulation; (3) the reduced automaton is used to compute an expression (in terms of stream constants and operators) that represents the stream of all counts.
|COMPUTATION BY ABSTRACT DEVICES (acm F.1), LOGICS AND MEANINGS OF PROGRAMS (acm F.3)|
|Exact enumeration problems, generating functions (msc 05A15), Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (msc 68Q10), Semantics (msc 68Q55), Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (msc 68Q85)|
|Software (theme 1)|
|Software Engineering [SEN]|
Rutten, J.J.M.M. (2002). Coinductive counting with weighted automata. Software Engineering [SEN]. CWI.