×
Lombardy, Sylvain; Sakarovitch, Jacques

Derivatives of rational expressions with multiplicity. (English) Zbl 1070.68074

Theor. Comput. Sci. 332, No. 1-3, 141-177 (2005).
Summary: This paper addresses the problem of turning a rational (i.e. regular) expression into a finite automaton. We formalize and generalize the idea of “partial derivatives” introduced in 1995 by Antimirov, in order to obtain a construction of an automaton with multiplicity from a rational expression describing a formal power series with coefficients in a semiring.
We first define precisely what is such a rational expression with multiplicity and which hypothesis should be put on the semiring of coefficients in order to keep the usual identities.
We then define the derivative of such a rational expression as a linear combination of expressions called derived terms and we show that all derivatives of a given expression are generated by a finite set of derived terms, that yields a finite automaton with multiplicity whose behaviour is the series denoted by the expression. We also prove that this automaton is a quotient of the standard (or Glushkov) automaton of the expression. Finally, we propose and discuss some possible modifications to our definition of derivation.

Cited in 1 Review
Cited in 22 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

Rational expression; Regular expression; Automata; Automata with multiplicity

Software:

LANGAGE
PDF BibTeX XML Cite
\textit{S. Lombardy} and \textit{J. Sakarovitch}, Theor. Comput. Sci. 332, No. 1--3, 141--177 (2005; Zbl 1070.68074)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Antimirov, V., Partial derivatives of regular expressions and finite automaton constructions, Theoret. comput. sci., 155, 291-319, (1996) · Zbl 0872.68120
[2] J. Berstel, Ch. Reutenauer, Les séries rationnelles et leurs langages, Masson, 1984; Translation: Rational Series and their Languages, Springer, Berlin, 1986.
[3] Brzozowski, J.A., Derivatives of regular expressions, J. assoc. comput. Mach., 11, 481-494, (1964) · Zbl 0225.94044
[4] P. Caron, M. Flouret, Glushkov construction for multiplicities, Pre-Proceedings of CIAA ’00, M. Daley, M. Eramian, S. Yu (Eds.), University of Western Ontario, 2000, pp. 52-61. · Zbl 0989.68075
[5] Caron, P.; Flouret, M., Characterization of glushkov automata, Theoret. comput. sci., 233, 75-90, (2000) · Zbl 0952.68084
[6] P. Caron, M. Flouret, From Glushkov WFA’s to rational expressions, Proc. of DLT’03, Z. Ésik, Z. Fülöp (Eds.), Lecture Notes in Comput. Sci. 2710 (2003) 183-193. · Zbl 1037.68077
[7] J.-M. Champarnaud, G. Duchamp, Brzozowski’s derivatives extended to multiplicities, Proc. of CIAA ’01, Lecture Notes in Comput. Sci. 2494 (2001) 52-64. · Zbl 1015.68096
[8] J.-M. Champarnaud, D. Ziadi, New finite automaton constructions based on canonical derivatives, Pre-Proceedings of CIAA ’00, M. Daley, M. Eramian, S. Yu (Eds.), University of Western Ontario, 2000, pp. 36-43.
[9] Champarnaud, J.-M.; Ziadi, D., Canonical derivatives, Partial derivatives and finite automaton constructions, theoret. comput. sci., 289, 137-163, (2002) · Zbl 1061.68109
[10] Eilenberg, S., Automata, () · Zbl 0175.27902
[11] Glushkov, V., The abstract theory of automata, Russian math. surveys, 16, 1-53, (1961) · Zbl 0104.35404
[12] Kuich, W.; Salomaa, A., Semirings, automata, languages, (1986), Springer Berlin · Zbl 0582.68002
[13] S. Lombardy, J. Sakarovitch, Derivatives of rational expressions with multiplicity, in: MFCS 02, Lecture Notes in Comput. Sci. 2420 (2002) 471-482. · Zbl 1014.68085
[14] S. Lombardy, J. Sakarovitch, How expressions can code for automata, in: Latin 04, Lecture Notes in Comput. Sci. 2976 (2004) 242-251 (Journal version to appear in Theoret. Informatic and Applications). · Zbl 1196.68120
[15] McNaughton, R.; Yamada, H., Regular expressions and state graphs for automata, IRE trans. on electronic computers, 9, 39-47, (1960) · Zbl 0156.25501
[16] J.J.M.M. Rutten, Automata, power series, and coinduction: taking input derivatives seriously, in: ICALP 99, J. Wiedermann, P. van Emde Boas, M. Nielsen (Eds.), Lecture Notes in Comput. Sci. 1644 (1999) 645-654. · Zbl 0941.68638
[17] Rutten, J.J.M.M., Behavioural differential equationsa coinductive calculus of streams, automata, and power series, Theoret. comput. sci., 308, 1-53, (2003) · Zbl 1071.68050
[18] J. Sakarovitch, Eléments de théorie des automates, Vuibert, 2003; Translation: Elements of Automata Theory, Cambridge University Press, to appear. · Zbl 1178.68002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.