Extending the scalars of minimizations
Duchamp, Gérard, ; Laugerotte, Eric ; Luque, Jean-Gabriel
HAL, hal-00085307 / Harvested from HAL
In the classical theory of formal languages, finite state automata allow to recognize the words of a rational subset of $\Sigma^*$ where $\Sigma$ is a set of symbols (or the alphabet). Now, given a semiring $(\K,+,.)$, one can construct $\K$-subsets of $\Sigma^*$ in the sense of Eilenberg , that are alternatively called noncommutative formal power series for which a framework very similar to language theory has been constructed Particular noncommutative formal power series, which are called rational series, are the behaviour of a family of weighted automata (or $\K$-automata). In order to get an efficient encoding, it may be interesting to point out one of them with the smallest number of states. Minimization processes of $\K$-automata already exist for $\K$ being:\\ {\bf a)} a field ,\\ {\bf b)} a noncommutative field ,\\ {\bf c)} a PID .\\ When $\K$ is the bolean semiring, such a minimization process (with isomorphisms of minimal objects) is known within the category of deterministic automata. Minimal automata have been proved to be isomorphic in cases {\bf (a)} and {\bf (b)}. But the proof given for (b) is not constructive. In fact, it lays on the existence of a basis for a submodule of $\K^n$. Here we give an independent algorithm which reproves this fact and an example of a pair of nonisomorphic minimal automata. Moreover, we examine the possibility of extending {\bf (c)}. To this end, we provide an {\em Effective Minimization Process} (or {\em EMP}) which can be used for more general sets of coefficients.
Publié le : 2001-07-05
Classification:  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],  [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],  [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
@article{hal-00085307,
     author = {Duchamp, G\'erard,  and Laugerotte, Eric and Luque, Jean-Gabriel},
     title = {Extending the scalars of minimizations},
     journal = {HAL},
     volume = {2001},
     number = {0},
     year = {2001},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00085307}
}
Duchamp, Gérard, ; Laugerotte, Eric; Luque, Jean-Gabriel. Extending the scalars of minimizations. HAL, Tome 2001 (2001) no. 0, . http://gdmltest.u-ga.fr/item/hal-00085307/