Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-26T23:07:35.977Z Has data issue: false hasContentIssue false
  • English
  • Français

Corrigendum to our paper: How Expressions Can Code for Automata

Published online by Cambridge University Press:  28 July 2010

Sylvain Lombardy  and
Jacques Sakarovitch
Sylvain Lombardy
Affiliation:
IGM-LabInfo (UMR 8049), Université Paris-Est Marne-la-Vallée, 77454 Marne-la-Vallée Cedex 2, France; [email protected].
Jacques Sakarovitch
Affiliation:
LTCI (UMR 5141), CNRS/Télécom ParisTech, 46 rue Barrault, 75634 Paris Cedex 13, France; [email protected].
Get access

Abstract

In a previous paper, we have described the construction of an automaton from a rational expression which has the property that the automaton built from an expression which is itself computed from a co-deterministic automaton by the state elimination method is co-deterministic. It turned out that the definition on which the construction is based was inappropriate, and thus the proof of the property was flawed. We give here the correct definition of the broken derived terms of an expression which allow to define the automaton and the detailed full proof of the property.

Keywords

Finite automataregular expressionderivation of expressionsquotient of automata.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 44 , Issue 3 , July 2010 , pp. 339 - 361
Copyright
© EDP Sciences, 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

P.-Y. Angrand, S. Lombardy and J. Sakarovitch, On the number of broken derived terms of a rational expression. J. Automata, Languages and Combinatorics, to appear.
Antimirov, V., Partial derivatives of regular expressions and finite automaton constructions. Theoret. Computer Sci. 155 (1996) 291–319. CrossRef
Brzozowski, J.A., Derivatives of regular expressions. J. Assoc. Comput. Mach. 11 (1964) 481–494. CrossRef
Caron, P. and Flouret, M., Glushkov construction for series: the non commutative case. Int. J. Comput. Math. 80 (2003) 457–472. CrossRef
S. Eilenberg, Automata, Languages, and Machines. A, Academic Press (1974).
Glushkov, V., The abstract theory of automata. Russ. Math. Surv. 16 (1961) 1–53. CrossRef
Lombardy, S. and Sakarovitch, J., Derivatives of rational expressions with multiplicity. Theoret. Computer Sci. 332 (2005) 141–177. (Journal version of Proc. MFCS 02, LNCS 2420 (2002) 471–482.) CrossRef
Lombardy, S. and Sakarovitch, J., How expressions can code for automata. RAIRO – Inform. theor. appl. 39 (2005) 217–237 (Journal version Proc. LATIN, LNCS 2976 (2004) 242–251.) CrossRef
J. Sakarovitch, Éléments de théorie des automates. Vuibert (2003), Corrected English edition: Elements of Automata Theory . Cambridge University Press (2009).