Weighted Automata and Recurrence Equations for Regular Languages

MaRDI QIDQ6219628zbMATH OpenFDO

Authors Edoardo Carta-Gerardino, Parisa Babaali

Publication date 7 July 2010

Abstract: Let $mathcalP(Sigm{a}^{\ast })$ be the semiring of languages, and consider its subset $mathcalP(Sigma)$. In this paper we define the language recognized by a weighted automaton over $mathcalP(Sigma)$ and a one-letter alphabet. Similarly, we introduce the notion of language recognition by linear recurrence equations with coefficients in $mathcalP(Sigma)$. As we will see, these two definitions coincide. We prove that the languages recognized by linear recurrence equations with coefficients in $mathcalP(Sigma)$ are precisely the regular languages, thus providing an alternative way to present these languages. A remarkable consequence of this kind of recognition is that it induces a partition of the language into its cross-sections, where the $n$th cross-section contains all the words of length $n$ in the language. Finally, we show how to use linear recurrence equations to calculate the density function of a regular language, which assigns to every $n$ the number of words of length $n$ in the language. We also show how to count the number of successful paths of a weighted automaton.

This page was built for publication: Weighted Automata and Recurrence Equations for Regular Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6219628)