A final coalgebra for k-regular sequences

Helle Hvid Hansen, Clemens Kupke, Jan Rutten, Joost Winter

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Citation (Scopus)

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 languageEnglish
Title of host publicationHorizons of the Mind
Subtitle of host publicationA Tribute to Prakash Panangaden - Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday
EditorsFrank van Breugel, Elham Kashefi, Catuscia Palamidessi, Jan Rutten
Pages363-383
Number of pages21
Volume8464
DOIs
Publication statusPublished - May 2014

    Fingerprint

Keywords

  • k-regular sequences
  • coalgebra
  • k-adic numeration system

Cite this

Hansen, H. H., Kupke, C., Rutten, J., & Winter, J. (2014). A final coalgebra for k-regular sequences. In F. van Breugel, E. Kashefi, C. Palamidessi, & J. Rutten (Eds.), Horizons of the Mind: A Tribute to Prakash Panangaden - Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday (Vol. 8464, pp. 363-383) https://doi.org/10.1007/978-3-319-06880-0_19