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

Sylvain Lombardy; Jean Mairesse

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2006)

  • Volume: 40, Issue: 1, page 1-14
  • ISSN: 0988-3754

Abstract

top
Consider partial maps Σ * → ℝ 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.

How to cite

top

Lombardy, Sylvain, and Mairesse, Jean. "Series which are both max-plus and min-plus rational are unambiguous." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 40.1 (2006): 1-14. <http://eudml.org/doc/245266>.

@article{Lombardy2006,
abstract = {Consider partial maps $\Sigma ^*$$\rightarrow $$\mathbb \{R\}$ 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.},
author = {Lombardy, Sylvain, Mairesse, Jean},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {rational series; automata; unambiguous; max-plus semiring; tropical semiring},
language = {eng},
number = {1},
pages = {1-14},
publisher = {EDP-Sciences},
title = {Series which are both max-plus and min-plus rational are unambiguous},
url = {http://eudml.org/doc/245266},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Lombardy, Sylvain
AU - Mairesse, Jean
TI - Series which are both max-plus and min-plus rational are unambiguous
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2006
PB - EDP-Sciences
VL - 40
IS - 1
SP - 1
EP - 14
AB - Consider partial maps $\Sigma ^*$$\rightarrow $$\mathbb {R}$ 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.
LA - eng
KW - rational series; automata; unambiguous; max-plus semiring; tropical semiring
UR - http://eudml.org/doc/245266
ER -

References

top
  1. [1] F. Baccelli, G. Cohen, G.J. Olsder and J.P. Quadrat, Synchronization and Linearity. John Wiley & Sons, New York (1992). Zbl0824.93003MR1204266
  2. [2] J. Berstel, Transductions and context-free languages. B.G. Teubner (1979). Zbl0424.68040MR549481
  3. [3] J. Berstel and C. Reutenauer, Rational Series and their Languages. Springer-Verlag (1988). Zbl0668.68005MR971022
  4. [4] A. Bonnier-Rigny and D. Krob, A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring. Theoret. Comput. Sci. 134 (1994) 27–50. Zbl0823.68051
  5. [5] S. Eilenberg, Automata, languages and machines, volume A. Academic Press, New York (1974). Zbl0317.94045MR530382
  6. [6] S. Gaubert and J. Mairesse, Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Trans. Aut. Cont. 44 (1999) 683–698. Zbl0955.68082
  7. [7] K. Hashigushi, K. Ishiguro and S. Jimbo, Decidability of the equivalence problem for finitely ambiguous finance automata. Int. J. Algebra Comput. 12 (2002) 445–461. Zbl1007.68115
  8. [8] J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co. (1979). Zbl0426.68001MR645539
  9. [9] I. Klimann, S. Lombardy, J. Mairesse and C. Prieur, Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoret. Comput. Sci. 327 (2004) 349–373. Zbl1071.68035
  10. [10] D. Krob, The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Int. J. Algebra Comput. 4 (1994) 405–425. Zbl0834.68058
  11. [11] D. Krob, Some consequences of a Fatou property of the tropical semiring. J. Pure Appl. Algebra 93 (1994) 231–249. Zbl0806.68083
  12. [12] M. Mohri, Finite-state transducers in language and speech processing. Comput. Linguist. 23 (1997) 269–311. 
  13. [13] P. Moller, Théorie algébrique des systèmes à événements discrets. Ph.D. thesis, École des Mines, Paris (1988). 
  14. [14] J. Sakarovitch, A construction on finite automata that has remained hidden. Theoret. Comput. Sci. 204 (1998) 205–231. Zbl0913.68137
  15. [15] J. Sakarovitch, Éléments de théorie des automates. Vuibert Informatique, Paris (2003). 
  16. [16] A. Salomaa and M. Soittola, Automata Theoretic Aspects of Formal Powers Series. Springer-Verlag, Berlin (1978). Zbl0377.68039MR483721
  17. [17] M.-P. Schützenberger, Sur les relations rationnelles entre monoïdes libres. Theoret. Comput. Sci. 3 (1976/77) 243–259. Zbl0358.68129
  18. [18] I. Simon, Recognizable sets with multiplicities in the tropical semiring, in Mathematical Foundations of Computer Science, Proc. 13th Symp., Lect. Notes Comput. Sci. 324 (1988) 107–120. Zbl0656.68086
  19. [19] L. Stockmeyer and A. Meyer, Word problems requiring exponential time: preliminary report, in Fifth Annual ACM Symposium on Theory of Computing. Assoc. Comput. Mach., New York (1973) 1–9. Zbl0359.68050
  20. [20] A. Weber, Finite-valued distance automata. Theoret. Comput. Sci. 134 (1994) 225–251. Zbl0938.68709

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.