3 papers
cs.FL2019
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…
cs.FL2018
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…
cs.FL2017
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…