<p>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:
<a href="https://www.mimuw.edu.pl/%7Ebojan/papers/forests-dlt.pdf" rel="noreferrer">https://www.mimuw.edu.pl/~bojan/papers/forests-dlt.pdf</a></p>
<p>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 <em>stabilization monoid</em>, which captures which runs diverge to <span class="math-container">$\infty$</span> and which stay bounded.
An application of this can be found in a work on determinization of polynomially ambiguous weighted automata, here:
<a href="https://hal.inria.fr/inria-00360205/document" rel="noreferrer">https://hal.inria.fr/inria-00360205/document</a></p>
<p>This doesn't really answer your question, but maybe these references will be useful to get the overall gist of this approach.</p>

CC BY-SA 4.0
2023-01-27T21:57:44.963Z
Thanks, very interesting references!
Nicola Gigante
CC BY-SA 4.0
2023-01-27T20:25:03.253Z
2023-01-27T20:25:03.253Z
Shaull
<p>Let <span class="math-container">$A=(Q,\Sigma, \Delta, q_0, F)$</span> be an NFA over an alphabet <span class="math-container">$\Sigma$</span>, <span class="math-container">$M(A)$</span> be its <em>transition monoid</em>.</p>
<p>For all <span class="math-container">$a\in\Sigma$</span>, let <span class="math-container">$S_a\in\mathbb{B}^{|Q|\times|Q|}$</span> be the <em>adjacency matrix</em> of <span class="math-container">$A$</span> relative to <span class="math-container">$a$</span>, <em>i.e.</em>, <span class="math-container">$S_a(i,j)=1$</span> iff <span class="math-container">$(q_i,a,q_j)\in\Delta$</span>.</p>
<p>If I'm not mistaken, <span class="math-container">$M(A)$</span> is generated by <span class="math-container">$S=\{S_a\mid a\in\Sigma\}$</span> with the usual matrix product and identity (this is also explained in <a href="https://www.irif.fr/%7Ejep/PDF/MPRI/MPRI.pdf" rel="noreferrer">Pin's book</a>, page 86, if I didn't misunderstood). This also means we can see each element of <span class="math-container">$M(A)$</span> as a matrix.</p>
<p>So are there any useful properties we can get about <span class="math-container">$M(A)$</span> from looking at the elements of <span class="math-container">$M(A)$</span> as matrices? Maybe some spectral properties?</p>

CC BY-SA 4.0
2023-01-27T18:08:30.060Z
Spectral ideas (like eigenvalues) usually assume the matrix is over a field. Have they been generalised to semirings?
Martin Berger
CC BY-SA 4.0
2023-01-27T20:08:54.023Z
Afaik yes, but I hardly know anything about these things…
Nicola Gigante
CC BY-SA 4.0
2023-01-27T21:29:36.410Z
I'd be interested in references for spectral methods on matrices over semirings.
Martin Berger
<reference-request><automata-theory>
Relationship between the transition monoid of an automaton and its adjacency matrix
Nicola Gigante
# Relationship between the transition monoid of an automaton and its adjacency matrix

(Asked by: username_0 on 2023-01-27)

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](https://www.irif.fr/%7Ejep/PDF/MPRI/MPRI.pdf), 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?

**Tags:** reference-request, automata-theory

> **Comments:**
> **username_1**: Spectral ideas (like eigenvalues) usually assume the matrix is over a field. Have they been generalised to semirings?  
> **username_0**: Afaik yes, but I hardly know anything about these things…  
> **username_1**: I'd be interested in references for spectral methods on matrices over semirings.  

---

## 1 answers

### Answer by username_2 on 2023-01-27. Score: 8

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](https://www.mimuw.edu.pl/%7Ebojan/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.

> **Comments:**
> **username_0**: Thanks, very interesting references!  

---

