Source author record

Elena V. Pribavkina

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Discrete Mathematics math.CO

Catalog footprint

Research overview

8works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Synchronizing automata and principal eigenvectors of the underlying digraphs

A coloring of a digraph with a fixed out-degree k is a distribution of k labels over the edges resulting in a deterministic finite automaton. An automaton is called synchronizing if there exists a word which sends all states of the automaton to a single state. In the present paper we study connections between spectral and synchronizing properties of digraphs. We show that if a coloring of a digraph is not synchronizing, then the stationary distribution of an associated Markov chain has a partition of coordinates into blocks of equal sum. Moreover, if there exists such a partition, then there exists a non-synchronizing automaton with such stationary distribution. We extend these results to bound the number of non-synchronizing colorings for digraphs with particular eigenvectors. We also demonstrate that the length of the shortest synchronizing word of any coloring is at most $w^2 - 3w + 3$ , where $w$ is the sum of the coordinates of the integer principal eigenvector of the digraph.

preprint2014arXiv

A Coloring Problem for Infinite Words

In this paper we consider the following question in the spirit of Ramsey theory: Given $x\in A^ω,$ where $A$ is a finite non-empty set, does there exist a finite coloring of the non-empty factors of $x$ with the property that no factorization of $x$ is monochromatic? We prove that this question has a positive answer using two colors for almost all words relative to the standard Bernoulli measure on $A^ω.$ We also show that it has a positive answer for various classes of uniformly recurrent words, including all aperiodic balanced words, and all words $x\in A^ω$ satisfying $λ_x(n+1)-λ_x(n)=1$ for all $n$ sufficiently large, where $λ_x(n)$ denotes the number of distinct factors of $x$ of length $n.$

preprint2014arXiv

Reset thresholds of automata with two cycle lengths

We present several series of synchronizing automata with multiple parameters, generalizing previously known results. Let p and q be two arbitrary co-prime positive integers, q > p. We describe reset thresholds of the colorings of primitive digraphs with exactly one cycle of length p and one cycle of length q. Also, we study reset thresholds of the colorings of primitive digraphs with exactly one cycle of length q and two cycles of length p.

preprint2013arXiv

A Coloring Problem for Sturmian and Episturmian Words

We consider the following open question in the spirit of Ramsey theory: Given an aperiodic infinite word $w$ , does there exist a finite coloring of its factors such that no factorization of $w$ is monochromatic? We show that such a coloring always exists whenever $w$ is a Sturmian word or a standard episturmian word.

preprint2013arXiv

Finitely generated ideal languages and synchronizing automata

We study representations of ideal languages by means of strongly connected synchronizing automata. For every finitely generated ideal language L we construct such an automaton with at most 2^n states, where n is the maximal length of words in L. Our constructions are based on the De Bruijn graph.

preprint2013arXiv

Principal ideal languages and synchronizing automata

We study ideal languages generated by a single word. We provide an algorithm to construct a strongly connected synchronizing automaton for which such a language serves as the language of synchronizing words. Also we present a compact formula to calculate the syntactic complexity of this language.

preprint2011arXiv

On Non-Complete Sets and Restivo's Conjecture

A finite set S of words over the alphabet A is called non-complete if Fact(S*) is different from A*. A word w in A* - Fact(S*) is said to be uncompletable. We present a series of non-complete sets S_k whose minimal uncompletable words have length 5k^2 - 17k + 13, where k > 3 is the maximal length of words in S_k. This is an infinite series of counterexamples to Restivo's conjecture, which states that any non-complete set possesses an uncompletable word of length at most 2k^2.

preprint2010arXiv

On the Minimal Uncompletable Word Problem

Let S be a finite set of words over an alphabet Sigma. The set S is said to be complete if every word w over the alphabet Sigma is a factor of some element of S*, i.e. w belongs to Fact(S*). Otherwise if S is not complete, we are interested in finding bounds on the minimal length of words in Sigma* which are not elements of Fact(S*) in terms of the maximal length of words in S.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Elena V. Pribavkina

Research overview

Is this your work?

8 publications

Synchronizing automata and principal eigenvectors of the underlying digraphs

A Coloring Problem for Infinite Words

Reset thresholds of automata with two cycle lengths

A Coloring Problem for Sturmian and Episturmian Words

Finitely generated ideal languages and synchronizing automata

Principal ideal languages and synchronizing automata

On Non-Complete Sets and Restivo's Conjecture

On the Minimal Uncompletable Word Problem

See the researcher in context

Building this map preview