2026-07-22T19:33:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22886 2025-10-02T13:36:30Z ddc:004 open_access

Efficiently Computing the Minimum Rank of a Matrix in a Monoid of Zero-One Matrices Kiefer, Stefan Ryzhikov, Andrew matrix monoids minimum rank unambiguous automata 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 𝒜 be a finite set of n×n zero-one matrices generating a monoid of zero-one matrices, and m be the cardinality of 𝒜. We study the computational complexity of computing the minimum rank of a matrix in the monoid generated by 𝒜. By using linear-algebraic techniques, we show that this problem is in NC and can be solved in 𝒪(mn⁴) time. We also provide a combinatorial algorithm finding a matrix of minimum rank in 𝒪(n^{2 + ω} + mn⁴) time, where 2 ≤ ω ≤ 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 𝒪(n²) describing a product resulting in a matrix of minimum rank. For the special case corresponding to complete 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 states under the action of a word. Our combinatorial algorithm finds a matrix of minimum rank in time 𝒪(n³ + mn²) in this case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Kiefer and Andrew Ryzhikov 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.61 urn:nbn:de:0030-drops-228867 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.61 eng https://creativecommons.org/licenses/by/4.0/legalcode