Article
Full entry |
PDF
(1.5 MB)
Feedback
PDF
(1.5 MB)
Feedback
Keywords:
idempotent semirings; recognizable series
idempotent semirings; recognizable series
Summary:
In this article, we compare different types of representations for series with coefficients in complete idempotent semirings. Each of these representations was introduced to solve a particular problem. We show how they are or are not included one in the other and we present a common generalization of them.
References:
[1] Berstel J.: Transductions and Context–Free Languages. Teubner, Stuttgart 1979 MR 0549481 | Zbl 0424.68040
[2] Berstel J., Reutenauer C.: Les séries rationnelles et leurs langages. Masson, Paris 1984. English translation: Rational Series and Their Languages, Springer–Verlag, Berlin 1988 MR 0971022 | Zbl 0573.68037
[3] Blyth T. S., Janowitz M. F.: Residuation Theory. Pergamon Press, Oxford 1972 MR 0396359 | Zbl 0301.06001
[4] Eilenberg S.: Automata, Languages and Machines, vol. A. Academic Press, New York 1974 MR 0530382 | Zbl 0359.94067
[5] Gunawardena J.: An introduction to idempotency, in idempotency. Chapter 1 (J. Gunawardena, ed.), Cambridge University Press, Cambridge 1998 MR 1608370
[6] Klimann I.: New types of automata to solve fixed point problems. Theoret. Comput. Sci. 259 (2001), 1–2, 183–197 DOI 10.1016/S0304-3975(99)00335-7 | MR 1832790 | Zbl 0973.68122
[7] Klimann I.: A solution to the problem of $(A,B)$-invariance for series. Theoret. Comput. Sci. 293 (2003), 1, 115–139 DOI 10.1016/S0304-3975(02)00234-7 | MR 1957615 | Zbl 1025.68050
[8] Kobayashi N.: The closure under division and a characterization of the recognizable ${\mathcal Z}$-subsets. RAIRO Inform. Théor. Appl. 30 (1996), 3, 209–230 MR 1415829
[9] Pin J.-E., Sakarovitch J.: Une application de la représentation matricielle des transductions. Theoret. Comp. Sci. 35 (1985), 271–293 DOI 10.1016/0304-3975(85)90019-2 | MR 0785156 | Zbl 0563.68064
[10] Salomaa A., Soittola M.: Automata–Theoretical Aspects of Formal Power Series. Springer–Verlag, Berlin 1978 MR 0483721
Search
Partner of
