Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1085.68081
Lombardy, Sylvain; Mairesse, Jean
Series which are both max-plus and min-plus rational are unambiguous. (English)
[J] Theor. Inform. Appl. 40, No. 1, 1-14 (2006). ISSN 0988-3754; ISSN 1290-385X/e

Summary: Consider partial maps $\Sigma^*\to \bbfR$ with a rational domain. We show that two families of such series are actually the same: 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 with different proofs, so the above unifies the picture. We give an effective procedure to build an unambiguous automaton from a max-plus automaton and a min-plus one that recognize the same series.

MSC 2000:: *68Q45 Formal languages
68Q70 Algebraic theory of automata
68Q19 Descriptive complexity and finite models

Keywords: rational series; automata; unambiguous; max-plus semiring; tropical semiring

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]