Shuffle-Rational Series and Doubly-Rational Series

Speaker(s)

Subbarao Venkatesh Guggilam

Affiliation

UiT- The Arctic University of Norway

Language of the talk

English

Date

Aug. 20, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Shuffle-Rational Series and Doubly-Rational Series

Seminar

Seminar Automata Theory

---

    Formal power series have long played a central role in both Mathematical Systems Theory and Automata
Theory. A foundational result by Marcel-Paul Schützenberger established that recognizable series (the
semantics of weighted automata) are precisely the rational series, where rationality is defined via the rational
closure under the Cauchy product of non-commutative polynomials.
    This connection extends into systems theory through the framework of Chen–Fliess series, where rational
series correspond to canonical realizations of bilinear systems.
    Motivated by this interplay, a natural question arises: What if we replace the Cauchy product with the
shuffle product in forming the rational closure? This leads to the notion of shuffle-rational series. In this talk,
we will introduce the concept of shuffle recognizability, and present a Schützenberger-type result showing the
equivalence between shuffle rationality and shuffle recognizability. We will also explore the implications of
these ideas in the context of nonlinear systems theory.
    In a related direction, Schützenberger also proved that rational series are closed under the shuffle product.
This observation leads to a second construction: the rational closure of rational series under shuffle—giving
rise to doubly-rational series. If time permits, we will discuss the notion of doubly-recognizable series as well.

    The talk is intended to be self-contained and assumes no prior background in systems theory or Chen–
Fliess series.

---

     Formal power series have long played a central role in both Mathematical Systems Theory and Automata
Theory. A foundational result by Marcel-Paul Schützenberger established that recognizable series (the
semantics of weighted automata) are precisely the rational series, where rationality is defined via the rational
closure under the Cauchy product of non-commutative polynomials.
    This connection extends into systems theory through the framework of Chen–Fliess series, where rational
series correspond to canonical realizations of bilinear systems.
    Motivated by this interplay, a natural question arises: What if we replace the Cauchy product with the
shuffle product in forming the rational closure? This leads to the notion of shuffle-rational series. In this talk,
we will introduce the concept of shuffle recognizability, and present a Schützenberger-type result showing the
equivalence between shuffle rationality and shuffle recognizability. We will also explore the implications of
these ideas in the context of nonlinear systems theory.
    In a related direction, Schützenberger also proved that rational series are closed under the shuffle product.
This observation leads to a second construction: the rational closure of rational series under shuffle—giving
rise to doubly-rational series. If time permits, we will discuss the notion of doubly-recognizable series as well.

    The talk is intended to be self-contained and assumes no prior background in systems theory or Chen–
Fliess series.

---