# Relationship between the transition monoid of an automaton and its adjacency matrix

Let $$A=(Q,\Sigma, \Delta, q_0, F)$$ be an NFA over an alphabet $$\Sigma$$, $$M(A)$$ be its transition monoid.

For all $$a\in\Sigma$$, let $$S_a\in\mathbb{B}^{|Q|\times|Q|}$$ be the adjacency matrix of $$A$$ relative to $$a$$, i.e., $$S_a(i,j)=1$$ iff $$(q_i,a,q_j)\in\Delta$$.

If I'm not mistaken, $$M(A)$$ is generated by $$S=\{S_a\mid a\in\Sigma\}$$ with the usual matrix product and identity (this is also explained in Pin's book, page 86, if I didn't misunderstood). This also means we can see each element of $$M(A)$$ as a matrix.

So are there any useful properties we can get about $$M(A)$$ from looking at the elements of $$M(A)$$ as matrices? Maybe some spectral properties?

• Spectral ideas (like eigenvalues) usually assume the matrix is over a field. Have they been generalised to semirings? Jan 27 at 18:08
• Afaik yes, but I hardly know anything about these things… Jan 27 at 20:08
• I'd be interested in references for spectral methods on matrices over semirings. Jan 27 at 21:29

## 1 Answer

The algebraic view has many useful properties. I think these become more evident when you move from the Boolean setting to richer semirings, e.g., tropical-weighted automata. At any rate, a celebrated result that uses this view is Simon's Factorization theorem. An excellent survey by Bojanczyk is here: https://www.mimuw.edu.pl/~bojan/papers/forests-dlt.pdf

In the tropical semiring you can get pretty far using this view, by examining the generated semigroup (which is not necessarily finite), and defining the so-called stabilization monoid, which captures which runs diverge to $$\infty$$ and which stay bounded. An application of this can be found in a work on determinization of polynomially ambiguous weighted automata, here: https://hal.inria.fr/inria-00360205/document

This doesn't really answer your question, but maybe these references will be useful to get the overall gist of this approach.

• Thanks, very interesting references! Jan 27 at 21:57