4 papers
Spectral and combinatorial methods for efficiently computing the rank of unambiguous finite automata
Stefan Kiefer, Andrew Ryzhikov
A zero-one matrix is a matrix with entries from . We study monoids containing only such matrices. A finite set of zero-one matrices generating such a monoid can be seen a…
The asymptotic size of finite irreducible semigroups of rational matrices
Stefan Kiefer, Andrew Ryzhikov
In this paper we investigate the maximum size of finite semigroups of rational matrices, with the goal of shedding more light on their structure. Such semigroups provi…
The complexity of reachability problems in strongly connected finite automata
Stefan Kiefer, Andrew Ryzhikov
Several reachability problems in finite automata, such as completeness of NFAs and synchronisation of total DFAs, correspond to fundamental properties of sets of nonnegative matric…
The complexity of computing the period and the exponent of a digraph
Stefan Kiefer, Andrew Ryzhikov
The period of a strongly connected digraph is the greatest common divisor of the lengths of all its cycles. The period of a digraph is the least common multiple of the periods of i…