Corrigendum to our paper : How expressions can code for automata
Lombardy, Sylvain ; Sakarovitch, Jacques
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010), p. 339-361 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2010-01-01
DOI : https://doi.org/10.1051/ita/2010019
Classification:  68Q45,  68Q70 
@article{ITA_2010__44_3_339_0,
     author = {Lombardy, Sylvain and Sakarovitch, Jacques},
     title = {Corrigendum to our paper : How expressions can code for automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {44},
     year = {2010},
     pages = {339-361},
     doi = {10.1051/ita/2010019},
     mrnumber = {2761523},
     zbl = {1216.68148},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2010__44_3_339_0}
}

Lombardy, Sylvain; Sakarovitch, Jacques. Corrigendum to our paper : How expressions can code for automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) pp. 339-361. doi : 10.1051/ita/2010019. http://gdmltest.u-ga.fr/item/ITA_2010__44_3_339_0/

[1] 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.

[2] V. Antimirov, Partial derivatives of regular expressions and finite automaton constructions. Theoret. Computer Sci. 155 (1996) 291-319. | Zbl 0872.68120

[3] J.A. Brzozowski, Derivatives of regular expressions. J. Assoc. Comput. Mach. 11 (1964) 481-494. | Zbl 0225.94044

[4] P. Caron and M. Flouret, Glushkov construction for series: the non commutative case. Int. J. Comput. Math. 80 (2003) 457-472. | Zbl 1033.68058

[5] S. Eilenberg, Automata, Languages, and Machines. A, Academic Press (1974). | Zbl 0359.94067

[6] V. Glushkov, The abstract theory of automata. Russ. Math. Surv. 16 (1961) 1-53. | Zbl 0104.35404

[7] S. Lombardy and J. Sakarovitch, Derivatives of rational expressions with multiplicity. Theoret. Computer Sci. 332 (2005) 141-177. (Journal version of Proc. MFCS 02, LNCS 2420 (2002) 471-482.) | Zbl 1070.68074

[8] S. Lombardy and J. Sakarovitch, How expressions can code for automata. RAIRO - Inform. theor. appl. 39 (2005) 217-237 (Journal version Proc. LATIN, LNCS 2976 (2004) 242-251.) | Numdam | Zbl 1102.68070

[9] J. Sakarovitch, Éléments de théorie des automates. Vuibert (2003), Corrected English edition: Elements of Automata Theory . Cambridge University Press (2009). | Zbl 1178.68002