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

Article type: Research Article

Authors: Champarnaud, Jean-Marc | Ouardi, Faissal | Ziadi, Djelloul

Affiliations: University of Rouen, LITIS, 76800 Saint-Etienne du Rouvray – France. jean-marc.champarnaud@univ-rouen.fr; faissal.ouardi@univ-rouen.fr; djelloul.ziadi@univ-rouen.fr

Note: [] Address for correspondence: University of Rouen, LITIS, 76800 Saint-Etienne du Rouvray – France

Abstract: 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.

Keywords: regular K-expression, K-automaton, equation K-automaton, c-continuation

DOI: 10.3233/FI-2009-0001

Journal: Fundamenta Informaticae, vol. 90, no. 1-2, pp. 1-16, 2009