Abstract
This chapter presents the theory of weighted automata over graded monoids and with weights taken in arbitrary semirings. The first benefit of broadening the scope beyond free monoids is that it makes clearer the distinction between the rational and the recognisable series. As the topological machinery is set anyway, the star of series is defined in a slightly more general setting than cycle-free series. The main subjects covered in the chapter are then: the notion of covering of automata (also called bisimulation by some authors) and its relationship with the conjugacy of automata; the closure of recognisable series by Hadamard and shuffle products; the derivation of weighted rational expressions over a free monoid; the reduction theory of series over a free monoid and with weights in a (skew) field, that leads to a procedure for the decidability of equivalence (with a cubic complexity); and the basics for a theory of weighted rational relations. As a result, this chapter, among other things, lays the bases for the proof of the decidability of the equivalence of deterministic k-tape transducers which is one of the most striking examples of the application of algebra to ‘machine theory’.
This chapter is adapted from Chaps. III and IV of the book Elements of Automata Theory, Jacques Sakarovitch, 2009, ©Cambridge University Press, where missing proofs, detailed examples and further developments can be found.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
V. Antimirov. Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science, 155:291–319, 1996.
A. Arnold. Systèmes de transitions finis et sémantique des processus communiquants. Masson, Paris, 1992. Translation: Finite Transitions Systems. Prentice–Hall, New York, 1994.
M.-P. Béal, S. Lombardy, and J. Sakarovitch. On the equivalence of ℤ-automata. In ICALP 2005, volume 3580 of Lecture Notes in Computer Science, pages 397–409. Springer, Berlin, 2005.
M.-P. Béal, S. Lombardy, and J. Sakarovitch. Conjugacy and equivalence of weighted automata and functional transducers. In CSR 2006, volume 3967 of Lecture Notes in Computer Science, pages 58–69. Springer, Berlin, 2006.
J. Berstel and C. Reutenauer. Les séries rationnelles et leurs langages. Masson, Paris, 1984. Translation: Rational Series and Their Languages. Springer, Berlin, 1988. New revised English edition available from http://www-igm.univ-mlv.fr/~berstel/.
M. Bird. The equivalence problem for deterministic two-tape automata. Journal of Computer and System Sciences, 7:218–236, 1973.
S.L. Bloom and Z. Ésik. Iteration Theories. Springer, Berlin, 1993.
A. Cardon and M. Crochemore. Détermination de la représentation standard d’une série reconnaissable. Theoretical Informatics and Applications, RAIRO, 14:371–379, 1980.
P. Caron and M. Flouret. Glushkov construction for multiplicities. In A. Paun and S. Yu, editors, CIAA 2000, volume 2088 of Lecture Notes in Computer Science, pages 67–79. Springer, Berlin, 2001.
J.-M. Champarnaud and D. Ziadi. Canonical derivatives, partial derivatives and finite automaton constructions. Theoretical Computer Science, 289:137–163, 2002.
P.M. Cohn. Algebra. Wiley, New York, 1974. 2nd edition: volume I, 1982; volume II, 1989; volume III, 1991.
J.H. Conway. Regular Algebra and Finite Machines. Chapman & Hall, London, 1971.
A. Ehrenfeucht, R. Parikh, and G. Rozenberg. Pumping lemmas for regular sets. SIAM Journal on Computing, 10:536–541, 1981.
S. Eilenberg. Automata, Languages and Machines, volume A. Academic Press, San Diego, 1974.
S. Eilenberg and M.P. Schützenberger. Rational sets in commutative monoids. Journal of Algebra, 13:173–191, 1969.
C.C. Elgot and J.E. Mezei. On relations defined by generalized finite automata. IBM Journal of Research and Development, 9:47–68, 1965.
M. Fliess. Formal languages and formal power series. In Séminaire Logique et Automates, IRIA, 1971, pages 77–85.
M. Fliess. Matrices de Hankel. Journal de Mathématiques Pures et Appliquées, 53:197–222, 1974. Erratum in: Journal de Mathématiques Pures et Appliquées, 54, 1975.
M. Fliess. Sur divers produit de séries formelles. Bulletin de la Société Mathématique de France, 102:181–191, 1974.
M. Flouret and E. Laugerotte. Noncommutative minimization algorithms. Information Processing Letters, 64:123–126, 1997.
W. Gröbner. Matrizenrechnung. Oldenburg, München, 1956.
T. Harju and J. Karhumäki. The equivalence problem of multitape finite automata. Theoretical Computer Science, 78:347–355, 1991.
G. Higman. Ordering by divisibility in abstract algebra. Proceedings of the London Mathematical Society. Second Series, 2:326–336, 1952.
G. Jacob. Représentations et substitutions matricielles dans la théorie algébrique des transductions. Thèse Sci. Math. Univ. Paris VII, 1975.
G. Jacob. Sur un théorème de Shamir. Information and Control, 27:218–261, 1975.
S.C. Kleene. Representation of events in nerve nets and finite automata. In C. Shannon and J. McCarthy, editors, Automata Studies, pages 3–41. Princeton University Press, Princeton, 1956.
D. Krob. Complete systems of B-rational identities. Theoretical Computer Science, 89:207–343, 1991.
D. Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. In W. Kuich, editor, ICALP’92, volume 623 of Lecture Notes in Computer Science, pages 101–112. Springer, Berlin, 1992.
W. Kuich and A. Salomaa. Semirings, Automata, Languages. Springer, Berlin, 1986.
F.W. Levi. On semigroups. Bulletin of the Calcutta Mathematical Society, 36:141–146, 1944 and 38:123–124, 1946.
D. Lind and B. Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995.
S. Lombardy and J. Sakarovitch. Derivation of rational expressions with multiplicity. In MFCS’02, volume 2420 of Lecture Notes in Computer Science, pages 471–482. Springer, Berlin, 2002.
S. Lombardy and J. Sakarovitch. Derivation of rational expressions with multiplicity. Theoretical Computer Science, 332:141–177, 2005.
A.I. Malcev. On the embedding of group algebras in division algebras. Doklady Akademii Nauk SSSR (N.S.), 60:1409–1501, 1948 (in Russian).
J. McKnight. Kleene’s quotient theorems. Pacific Journal of Mathematics, 14:43–52, 1964.
B.H. Neumann. On ordered division ring. Transactions of the American Mathematical Society, 66:202–252, 1949.
M.O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3:125–144, 1959. Reprinted in: E. Moore, editor, Sequential Machines: Selected Papers, Addison–Wesley, Reading, 1965.
A. Restivo and C. Reutenauer. On cancellation properties of languages which are support of rational series. Journal of Computer and System Sciences, 29:153–159, 1984.
A.R. Richardson. Simultaneous linear equations over a division algebra. Proceedings of the London Mathematical Society, 28:395–420, 1928.
J.M. Rutten. Automata, power series, and coinduction: Taking input derivatives seriously. In J. Wiedermann, P. van Emde Boas, and M. Nielsen, editors, ICALP’99, volume 1644 of Lecture Notes in Computer Science, pages 645–654. Springer, Berlin, 1999.
J.M. Rutten. Behavioural differential equations: A coinductive calculus of streams, automata, and power series. Theoretical Computer Science, 308:1–53, 2003.
J. Sakarovitch. Kleene’s theorem revisited. In A. Kelemenova and K. Kelemen, editors, Trends, Techniques and Problems in Theoretical Computer Science, volume 281 of Lecture Notes in Computer Science, pages 39–50. Springer, Berlin, 1987.
J. Sakarovitch. Éléments de théorie des automates. Vuibert, Paris, 2003. Corrected English edition: Elements of Automata Theory, Cambridge University Press, Cambridge, 2009.
J. Sakarovitch. The language, the expression and the (small) automaton. In CIAA 2005, volume 3845 of Lecture Notes in Computer Science, pages 15–30. Springer, Berlin, 2005.
A. Salomaa and M. Soittola. Automata-Theoretic Aspects of Formal Power Series. Springer, Berlin, 1977.
M.P. Schützenberger. On the definition of a family of automata. Information and Control, 4:245–270, 1961.
M.P. Schützenberger. Certain elementary families of automata. In Symposium on Mathematical Theory of Automata, 1962, pages 139–153.
M.P. Schützenberger. On a theorem of R. Jungen. Proceedings of the American Mathematical Society, 13:885–889, 1962.
I. Simon. Limited subsets of a free monoid. In FOCS’78, 1978, pages 143–150.
E.D. Sontag. On some questions of rationality and decidability. Journal of Computer and System Sciences, 11:375–385, 1975.
A. Tarski. Cardinal Algebras. Oxford University Press, London, 1949.
L.G. Valiant. The equivalence problem for deterministic finite-turn pushdown automata. Information and Control, 25:123–133, 1974.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Sakarovitch, J. (2009). Rational and Recognisable Power Series. In: Droste, M., Kuich, W., Vogler, H. (eds) Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01492-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-01492-5_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01491-8
Online ISBN: 978-3-642-01492-5
eBook Packages: Computer ScienceComputer Science (R0)