2 citations · 9 across the 13 of their papers we have counts for
14 papers · 1 filter
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…
Traversing automata with current state uncertainty under LTL constraints
Andrew Ryzhikov, Petra Wolf
In this paper, we consider a problem which we call LTL model checking on paths: given a DFA and a formula in LTL on finite traces, does there exist a word …
Reachability in Fixed VASS: Expressiveness and Lower Bounds
Andrei Draghici, Christoph Haase, Andrew Ryzhikov
The recent years have seen remarkable progress in establishing the complexity of the reachability problem for vector addition systems with states (VASS), equivalently known as Petr…
The degree of a finite set of words
Dominique Perrin, Andrew Ryzhikov
We prove several results concerning finitely generated submonoids of the free monoid. These results generalize those known for free submonoids. We prove in particular that if $X=Y\…
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…
Palindromic Subsequences in Finite Words
Clemens Müllner, Andrew Ryzhikov
In 1999 Lyngsø and Pedersen proposed a conjecture stating that every binary circular word of length with equal number of zeros and ones has an antipalindromic linear subsequenc…
Finding Short Synchronizing Words for Prefix Codes
Andrew Ryzhikov, Marek Szykuła
We study the problems of finding a shortest synchronizing word and its length for a given prefix code. This is done in two different settings: when the code is defined by an arbitr…
On Automata Recognizing Birecurrent Sets
Andrew Ryzhikov
In this note we study automata recognizing birecurrent sets. A set of words is birecurrent if the minimal partial DFA recognizing this set and the minimal partial DFA recognizing t…
Subset Synchronization in Monotonic Automata
Andrew Ryzhikov, Anton Shemyakov
We study extremal and algorithmic questions of subset and careful synchronization in monotonic automata. We show that several synchronization problems that are hard in general auto…
Synchronization Problems in Automata without Non-trivial Cycles
Andrew Ryzhikov
We study the computational complexity of various problems related to synchronization of weakly acyclic automata, a subclass of widely studied aperiodic automata. We provide upper a…
Approximating the Maximum Number of Synchronizing States in Automata
Andrew Ryzhikov
We consider the problem {\sc Max Sync Set} of finding a maximum synchronizing set of states in a given automaton. We show that the decision version of this problem is PSPACE-comple…