An Efficient Computation of the Equation K-automaton of a Regular K-expression

• Autorzy: Champarnaud J-M. , Ouardi F. , Ziadi D.
• Języki publikacji: EN

Abstrakty

EN

The aim of this paper is to describe a quadratic algorithm for computing the equation K-automaton of a regular K-expression as defined by Lombardy and Sakarovitch. Our construction is based on an extension to regular K-expressions of the notion of c-continuation that we introduced to compute the equation automaton of a regular expression as a quotient of its position automaton.

Słowa kluczowe

EN

regular K-expression; K-automaton; equation K-automaton; c-continuation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 90, nr 1-2
• Strony: 1--16
• Opis fizyczny: bibliogr. 28 poz.

Twórcy

autor

Champarnaud J-M.

autor

Ouardi F.

autor

Ziadi D.

• University of Rouen, LITIS 76800 Saint-Etienne du Rouvray - France,

Bibliografia

• [1] C. Allauzen and M. Mohri. A Unified Construction of the Glushkov, Follow, and Antimirov Automata. In MFCS-2006, Lecture Notes in Computer Science, R. Kralovic and P. Urzyczyn eds., 4162:110-121, 2006.
• [2] V. Antimirov. Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci., 155:291-319, 1996.
• [3] A. Brüggemann-Klein, Regular Expressions into Finite Automata. Theoret. Comput. Sci., 120(1993), 197-213.
• [4] J. Berstel and C. Reutenauer, Les séries rationnelles et leurs langages, Études et recherches en informatique. Masson, Paris, 1984. English version: Rational series and their languages, Springer, 1988.
• [5] P. Caron and M. Flouret, Glushkov construction for series : The non commutative case, Intern. Journ. Comput. Maths, 80(4): 457-472, 2003.
• [6] J.-M. Champarnaud, E. Laugerotte, F. Ouardi, and D. Ziadi, From Regular Weighted Expressions to Finite Automata, Intern. Journ. of Found. Comput. Sci., (15)5: 687-700, 2004.
• [7] J.-M. Champarnaud, F. Nicart and D. Ziadi. From the ZPC -structure of a regular expression to its follow automaton, Intern. Journ. of Alg. and Comp., 16(1): pp 17-34, 2006.
• [8] J.-M. Champarnaud, F. Ouardi and D. Ziadi. Follow automaton versus equation automaton, In: DCFS-2004, Descriptional Complexity of Formal Systems Workshop, Proceedings, L. Ilie and D. Wotschke (eds.), pp. 145-153, 2004.
• [9] J.-M. Champarnaud, F. Ouardi and D. Ziadi. Normalized expressions and finite automata, Intern. Journ. Of Alg. and Comp., 17-1(2007), 141-154.
• [10] J.-M. Champarnaud and D. Ziadi. From Mirkin-s Prebases to Antimirov-s Word Partial Derivatives. Informatica Fundamentae, 45(3):195-205, 2001.
• [11] J.-M. Champarnaud and D. Ziadi. Canonical derivatives and finite automaton constructions, Theoret. Compt. Sci., 289:137-163, 2002.
• [12] J.-M. Champarnaud and D. Ziadi. Fromc-continuations to new quadratic algorithms for automaton synthesis, Intern. Journ. of Alg. and Comp., 11(6), 707-735, 2001.
• [13] J.-M. Champarnaud, F. Ouardi and D. Ziadi. An efficient computation of the equation K-automaton of a regularK-expression, in DLT-2007, Lecture Notes in Computer Science, T. Harju, J. Karhumäki and A. Lepistö eds., Springer-Verlag Berlin Heidelberg, 4588(2007), 145-156.
• [14] C.-H. Chang and R. Paige. From Regular Expressions to DFA-s Using Compressed NFA-s, Theoret. Comput. Sci., 178, 1-36, 1997.
• [15] T. Claveirole, S. Lombardy, S. O-Connor, L.-N. Pouchet, and J. Sakarovitch, Inside Vaucanson, Proc. Of CIAA-2005 (J. Farré, I. Litovsky and S. Schmitz eds.), Lect. Notes in Comp. Sci., 3845, Springer (2006), 116-128.
• [16] V.-M. Glushkov. The abstract theory of automata, Russian Mathematical Surveys, 16, 1-53, 1961.
• [17] U. Hebisch and H. J. Weinert. Semirings: algebraic theory and applications in computer science, World Scientific, Singapore, 1993.
• [18] L. Ilie and S. Yu. Follow automata, Information and computation, 186, 140-162, 2003.
• [19] W. Kuich and A. Salomaa. Semirings, automata, languages. EATCS Monographs on Theoretical Computer Science, Volume 5. Springer-Verlag, Berlin, 1986. Princeton U. Press.
• [20] S. Lombardy and J. Sakarovitch. Derivations of Rational Expressions with Multiplicity. MFCS-2002, K. Diks andW. Ritter, eds., Lect. Notes in Comp. Sci., Springer, 2420: 471-482, 2002.
• [21] S. Lombardy and J. Sakarovitch. Derivatives of Rational Expressions with Multiplicity. Theoret. Comput. Sci., 332: 141-177, 2005.
• [22] R. F. McNaughton and H. Yamada, Regular expressions and state graphs for automata, IEEE Trans. Electronic Comput. 9: 39-47, 1960.
• [23] B. G. Mirkin. An algorithm for constructing a base in a language of regular expressions. Engineering Cybernetics, 5:110-116, 1966.
• [24] J. Sakarovitch. Éléments de la théorie des automates. Les classiques de l-informatique., Vuibert Paris, 2003.
• [25] M. P. Schützenberger. On the definition of a family of automata. Information and control, 6:245-270, (1961).
• [26] K. Thompson. Regular expression search algorithm, Comm. ACM, 11, 6, 419-422, 1968.
• [27] D. Ziadi, J.-L. Ponty, and J.-M. Champarnaud. Passage d-une expression rationnelle à un automate fini non-déterministe. Bull. Belg. Math. Soc., 4:177-203, 1997.
• [28] D. Ziadi, Quelques aspects théoriques et algorithmiques des automates. Thèse d-habilitation à diriger des recherches, Université de Rouen, 2002.