Spectral and combinatorial methods for efficiently computing the rank of unambiguous finite automata
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914154125721600 |
|---|---|
| author | Kiefer, Stefan Ryzhikov, Andrew |
| author_facet | Kiefer, Stefan Ryzhikov, Andrew |
| contents | A zero-one matrix is a matrix with entries from $\{0, 1\}$. We study monoids containing only such matrices. A finite set of zero-one matrices generating such a monoid can be seen as the matrix representation of an unambiguous finite automaton, an important generalisation of deterministic finite automata which shares many of their good properties.
Let $\mathcal{A}$ be a finite set of $n \times n$ zero-one matrices generating a monoid of zero-one matrices, and $m$ be the cardinality of $\mathcal{A}$. We study the computational complexity of computing the minimum rank of a matrix in the monoid generated by $\mathcal{A}$. By using linear-algebraic techniques, we show that this problem is in $\textsf{NC}$ and can be solved in $\mathcal{O}(mn^4)$ time. We also provide a combinatorial algorithm finding a matrix of minimum rank in $\mathcal{O}(n^{2 + ω} + mn^4)$ time, where $2 \le ω\le 2.4$ is the matrix multiplication exponent. As a byproduct, we show a very weak version of a generalisation of the Černý conjecture: there always exists a straight line program of size $\mathcal{O}(n^2)$ describing a product resulting in a matrix of minimum rank.
For the special case corresponding to total DFAs (that is, for the case where all matrices have exactly one 1 in each row), the minimum rank is the size of the smallest image of the set of all states under the action of a word. Our combinatorial algorithm finds a matrix of minimum rank in time $\mathcal{O}(n^3 + mn^2)$ in this case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_09703 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spectral and combinatorial methods for efficiently computing the rank of unambiguous finite automata Kiefer, Stefan Ryzhikov, Andrew Formal Languages and Automata Theory Data Structures and Algorithms Symbolic Computation A zero-one matrix is a matrix with entries from $\{0, 1\}$. We study monoids containing only such matrices. A finite set of zero-one matrices generating such a monoid can be seen as the matrix representation of an unambiguous finite automaton, an important generalisation of deterministic finite automata which shares many of their good properties. Let $\mathcal{A}$ be a finite set of $n \times n$ zero-one matrices generating a monoid of zero-one matrices, and $m$ be the cardinality of $\mathcal{A}$. We study the computational complexity of computing the minimum rank of a matrix in the monoid generated by $\mathcal{A}$. By using linear-algebraic techniques, we show that this problem is in $\textsf{NC}$ and can be solved in $\mathcal{O}(mn^4)$ time. We also provide a combinatorial algorithm finding a matrix of minimum rank in $\mathcal{O}(n^{2 + ω} + mn^4)$ time, where $2 \le ω\le 2.4$ is the matrix multiplication exponent. As a byproduct, we show a very weak version of a generalisation of the Černý conjecture: there always exists a straight line program of size $\mathcal{O}(n^2)$ describing a product resulting in a matrix of minimum rank. For the special case corresponding to total DFAs (that is, for the case where all matrices have exactly one 1 in each row), the minimum rank is the size of the smallest image of the set of all states under the action of a word. Our combinatorial algorithm finds a matrix of minimum rank in time $\mathcal{O}(n^3 + mn^2)$ in this case. |
| title | Spectral and combinatorial methods for efficiently computing the rank of unambiguous finite automata |
| topic | Formal Languages and Automata Theory Data Structures and Algorithms Symbolic Computation |
| url | https://arxiv.org/abs/2511.09703 |