1. Corrigendum to our paper : How Expressions can code for Automata
- Author
-
Sylvain Lombardy, Jacques Sakarovitch, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire Traitement et Communication de l'Information (LTCI), Télécom ParisTech-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)
- Subjects
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES ,Powerset construction ,General Mathematics ,010102 general mathematics ,Continuous automaton ,Timed automaton ,Pushdown automaton ,Büchi automaton ,0102 computer and information sciences ,16. Peace & justice ,Nonlinear Sciences::Cellular Automata and Lattice Gases ,01 natural sciences ,Computer Science Applications ,Algebra ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,010201 computation theory & mathematics ,Deterministic automaton ,[INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering ,Probabilistic automaton ,Two-way deterministic finite automaton ,0101 mathematics ,Algorithm ,Software ,Computer Science::Formal Languages and Automata Theory ,Mathematics - Abstract
International audience; 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.
- Published
- 2010