6
$\begingroup$

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?

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

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks, very interesting references! $\endgroup$ Jan 27, 2023 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.