Extending the scalars of minimizations

Details Extending the scalars of minimizations Extending the scalars of minimizations

2006-07-18

arxiv.org/abs/math/0607411v1

SCI, \'{E}tats-Unis d'Am\'{e}rique (2001)

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Extending the scalars of minimizations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extending the scalars of minimizations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extending the scalars of minimizations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-122335