Abstract
We study k-regular sequences from a coalgebraic perspective. Building on the observation that the set of streams over a semiring S can be turned into a final coalgebra, we obtain characterizations of k-regular sequences in terms of finite weighted automata, finite systems of behavioral differential equations, and recognizable power series. The latter characterization is obtained via an isomorphism of final coalgebras based on the k-adic numeration system.
Original language | English |
---|---|
Title of host publication | Horizons of the Mind |
Subtitle of host publication | A Tribute to Prakash Panangaden - Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday |
Editors | Frank van Breugel, Elham Kashefi, Catuscia Palamidessi, Jan Rutten |
Pages | 363-383 |
Number of pages | 21 |
Volume | 8464 |
DOIs | |
Publication status | Published - May 2014 |
Keywords
- k-regular sequences
- coalgebra
- k-adic numeration system