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

DOI10.1051/ITA:2005042MaRDI QIDQ3374753zbMATH OpenOpenAlexFDO

Authors Sylvain Lombardy, Jean Mairesse

Publication date 22 February 2006

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0709.3257, http://www.numdam.org/item?id=ITA_2006__40_1_1_0, https://eudml.org/doc/92787

zbMATH Keywords

automatamax-plus semiringrational seriestropical semiringunambiguous

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Abstract: Consider partial maps from the free monoid into the field of real numbers 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.

Recommendations

• Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
• scientific article; zbMATH DE number 1163637
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• scientific article; zbMATH DE number 2040921
• scientific article; zbMATH DE number 7559164

Cites work

• A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring
• A construction on finite automata that has remained hidden
• DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA
• Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
• Finite-valued distance automata
• scientific article; zbMATH DE number 5643878 (Why is no real title available?)
• scientific article; zbMATH DE number 4072419 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• Modeling and analysis of timed Petri nets using heaps of pieces
• Some consequences of a Fatou property of the tropical semiring
• Sur les rélations rationnelles entre monoides libres
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE

Cited in

(7)

• Max-plus automata
• A contribution to the determinization of max-plus automata
• Supervisory control of (max,+) automata: extensions towards applications
• Coinduction in concurrent timed systems
• Comparison of max-plus automata and joint spectral radius of tropical matrices
• Unambiguity in automata theory
• Supervisory control of \((\max,+)\) automata: a behavioral approach

This page was built for publication: Series which are both max-plus and min-plus rational are unambiguous

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