Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T19:43:59.101Z Has data issue: false hasContentIssue false

Series which are both max-plus and min-plus rational are unambiguous

Published online by Cambridge University Press:  15 October 2005

Sylvain Lombardy
Affiliation:
LIAFA (UMR 7089), CNRS–Université Paris 7, 2 pl. Jussieu, 75251 Paris Cedex 05, France; lombardy@liafa.jussieu.fr, mairesse@liafa.jussieu.fr
Jean Mairesse
Affiliation:
LIAFA (UMR 7089), CNRS–Université Paris 7, 2 pl. Jussieu, 75251 Paris Cedex 05, France; lombardy@liafa.jussieu.fr, mairesse@liafa.jussieu.fr
Get access

Abstract

Consider partial maps ∑* → $\mathbb R$ with a rationaldomain. We show that two families of such series are actually thesame: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand.The decidability of equality was known to hold in both families withdifferent proofs, so the above unifies the picture. We give an effective procedure to build an unambiguous automaton froma max-plus automaton and a min-plus one that recognize the same series.

Information

Type
Research Article
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable