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. [email protected]; [email protected]; [email protected]

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