1 citations · 1 across the 4 of their papers we have counts for
5 papers
Stronger bounds on the degree of ambiguity of finite automata
Stefan Kiefer, Filip Mazowiecki, Andrew Ryzhikov +1
Ambiguity measures the number of accepting runs in nondeterministic finite automata (NFA). We consider finitely ambiguous NFA, where there exists a constant such that over ever…
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…
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 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…