On rational series in one variable over certain dioids - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1994

On rational series in one variable over certain dioids

Résumé

We give a characterization of rational series in one variable over certain idempotent semirings (commutative dioids) such as for instance the ``$(\max,+)$ ''semiring. We show that a series is rational iff it is merge of ultimately geometric series. As a by-product, we obtain a new proof of the periodicity theorem for powers of irreducible matrices and also some more general auxiliary results. We apply this characterization of rational series to the minimal realization problem for which we obtain an upper bound. We also obtain a lower bound in terms of minors in a symmetrized semiring

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-2162.pdf (368.57 Ko) Télécharger le fichier

Dates et versions

inria-00074510 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074510 , version 1

Citer

Stéphane Gaubert. On rational series in one variable over certain dioids. [Research Report] RR-2162, INRIA. 1994. ⟨inria-00074510⟩
80 Consultations
130 Téléchargements

Partager

Gmail Facebook X LinkedIn More