Extending the scalars of minimizations
<|reference_start|>Extending the scalars of minimizations: 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.<|reference_end|>
@article{duchamp2006extending,
    title={Extending the scalars of minimizations},
    author={G'erard Duchamp (LIPN), Eric Laugerotte (LIFAR EA2655), Jean-Gabriel
  Luque (IGM-LabInfo)},
    journal={SCI, \'{E}tats-Unis d'Am\'{e}rique (2001)},
    year={2006},
    archivePrefix={arXiv},
    eprint={math/0607411},
    primaryClass={math.CO cs.DS cs.SC}
}