{"ID":2842995,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.09703","arxiv_id":"2511.09703","title":"Spectral and combinatorial methods for efficiently computing the rank of unambiguous finite automata","abstract":"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.","short_abstract":"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 ma...","url_abs":"https://arxiv.org/abs/2511.09703","url_pdf":"https://arxiv.org/pdf/2511.09703v1","authors":"[\"Stefan Kiefer\",\"Andrew Ryzhikov\"]","published":"2025-11-12T20:00:48Z","proceeding":"cs.FL","tasks":"[\"cs.FL\",\"cs.DS\",\"cs.SC\"]","methods":"[]","has_code":false}