Zobrazeno 1 - 10
of 46
pro vyhledávání: '"Pribavkina, Elena V."'
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 sin
Externí odkaz:
http://arxiv.org/abs/1511.09079
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 w
Externí odkaz:
http://arxiv.org/abs/1403.3992
In this paper we consider the following question in the spirit of Ramsey theory: Given $x\in A^\omega,$ 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
Externí odkaz:
http://arxiv.org/abs/1307.2828
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
Externí odkaz:
http://arxiv.org/abs/1305.0336
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 calcu
Externí odkaz:
http://arxiv.org/abs/1304.3307
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 ex
Externí odkaz:
http://arxiv.org/abs/1301.5263
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^
Externí odkaz:
http://arxiv.org/abs/1104.0388
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 findin
Externí odkaz:
http://arxiv.org/abs/1002.1928
Publikováno v:
In Journal of Combinatorial Theory, Series A July 2014 125:306-332
Autor:
Pribavkina, Elena V., Rodaro, Emanuele
Publikováno v:
In Information and Computation March 2011 209(3):568-579