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

Finite automata
Differential equations

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
Hansen, Helle Hvid ; Kupke, Clemens ; Rutten, Jan ; Winter, Joost. / A final coalgebra for k-regular sequences. Horizons of the Mind: A Tribute to Prakash Panangaden - Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday. editor / Frank van Breugel ; Elham Kashefi ; Catuscia Palamidessi ; Jan Rutten. Vol. 8464 2014. pp. 363-383
@inbook{41acbbdc4ab746c1b482eaa5f9a67c8e,
title = "A final coalgebra for k-regular sequences",
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.",
keywords = "k-regular sequences, coalgebra, k-adic numeration system",
author = "Hansen, {Helle Hvid} and Clemens Kupke and Jan Rutten and Joost Winter",
year = "2014",
month = "5",
doi = "10.1007/978-3-319-06880-0_19",
language = "English",
isbn = "978-3-319-06879-4",
volume = "8464",
pages = "363--383",
editor = "{van Breugel}, Frank and Kashefi, {Elham } and Catuscia Palamidessi and Jan Rutten",
booktitle = "Horizons of the Mind",

}

Hansen, HH, 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

A final coalgebra for k-regular sequences. / Hansen, Helle Hvid; Kupke, Clemens; Rutten, Jan; Winter, Joost.

Horizons of the Mind: A Tribute to Prakash Panangaden - Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday. ed. / Frank van Breugel; Elham Kashefi; Catuscia Palamidessi; Jan Rutten. Vol. 8464 2014. p. 363-383.

Research output: Chapter in Book/Report/Conference proceedingChapter

TY - CHAP

T1 - A final coalgebra for k-regular sequences

AU - Hansen, Helle Hvid

AU - Kupke, Clemens

AU - Rutten, Jan

AU - Winter, Joost

PY - 2014/5

Y1 - 2014/5

N2 - 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.

AB - 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.

KW - k-regular sequences

KW - coalgebra

KW - k-adic numeration system

UR - http://link.springer.com/chapter/10.1007/978-3-319-06880-0_19

U2 - 10.1007/978-3-319-06880-0_19

DO - 10.1007/978-3-319-06880-0_19

M3 - Chapter

SN - 978-3-319-06879-4

VL - 8464

SP - 363

EP - 383

BT - Horizons of the Mind

A2 - van Breugel, Frank

A2 - Kashefi, Elham

A2 - Palamidessi, Catuscia

A2 - Rutten, Jan

ER -

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