8 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…
Synchronization of strongly connected partial DFAs and prefix codes
Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov +1
We study synchronizing partial DFAs, which extend the classical concept of synchronizing complete DFAs and are a special case of synchronizing unambiguous NFAs. A partial DFA is ca…
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…
Careful synchronisation and the diameter of transformation semigroups with few generators
Andrew Ryzhikov
A word is called carefully synchronising for a partial deterministic finite semi-automaton if it maps all states to the same state. Equivalently, it is a composition of partial tra…
On shortest products for nonnegative matrix mortality
Andrew Ryzhikov
Given a finite set of matrices with integer entries, the matrix mortality problem asks if there exists a product of these matrices equal to the zero matrix. We consider a special c…