2 citations · 9 across the 13 of their papers we have counts for
Showing 2025Show all
3 papers · 1 filter
cs.FL2025
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…
cs.DM2025
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…
cs.FL2025
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…