Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUniversal Partial Words over Non-Binary Alphabets
90
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Chen, Kitaev, M{u}tze, and Sun recently introduced the notion of universal partial words, a generalization of universal words and de Bruijn sequences. Universal partial words allow for a wild-card character $diamond$, which is a placeholder for any letter in the alphabet. We settle and strengthen conjectures posed in the same paper where this notion was introduced. For non-binary alphabets, we show that universal partial words have periodic $diamond$ structure and are cyclic, and we give number-theoretic conditions on the existence of universal partial words. In addition, we provide an explicit construction for a family of universal partial words over alphabets of even size.
rate research
Read More
A universal word for a finite alphabet $A$ and some integer $ngeq 1$ is a word over $A$ such that every word in $A^n$ appears exactly once as a subword (cyclically or linearly). It is well-known and easy to prove that universal words exist for any $A$ and $n$. In this work we initiate the systematic study of universal partial words. These are words that in addition to the letters from $A$ may contain an arbitrary number of occurrences of a special `joker symbol $Diamond otin A$, which can be substituted by any symbol from $A$. For example, $u=0Diamond 011100$ is a linear partial word for the binary alphabet $A={0,1}$ and for $n=3$ (e.g., the first three letters of $u$ yield the subwords $000$ and $010$). We present results on the existence and non-existence of linear and cyclic universal partial words in different situations (depending on the number of $Diamond$s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer.
A word is square-free if it does not contain any square (a word of the form $XX$), and is extremal square-free if it cannot be extended to a new square-free word by inserting a single letter at any position. Grytczuk, Kordulewski, and Niewiadomski proved that there exist infinitely many ternary extremal square-free words. We establish that there are no extremal square-free words over any alphabet of size at least 17.
Goldreich suggested candidates of one-way functions and pseudorandom generators included in $mathsf{NC}^0$. It is known that randomly generated Goldreichs generator using $(r-1)$-wise independent predicates with $n$ input variables and $m=C n^{r/2}$ output variables is not pseudorandom generator with high probability for sufficiently large constant $C$. Most of the previous works assume that the alphabet is binary and use techniques available only for the binary alphabet. In this paper, we deal with non-binary generalization of Goldreichs generator and derives the tight threshold for linear programming relaxation attack using local marginal polytope for randomly generated Goldreichs generators. We assume that $u(n)in omega(1)cap o(n)$ input variables are known. In that case, we show that when $rge 3$, there is an exact threshold $mu_mathrm{c}(k,r):=binom{k}{r}^{-1}frac{(r-2)^{r-2}}{r(r-1)^{r-1}}$ such that for $m=mufrac{n^{r-1}}{u(n)^{r-2}}$, the LP relaxation can determine linearly many input variables of Goldreichs generator if $mu>mu_mathrm{c}(k,r)$, and that the LP relaxation cannot determine $frac1{r-2} u(n)$ input variables of Goldreichs generator if $mu<mu_mathrm{c}(k,r)$. This paper uses characterization of LP solutions by combinatorial structures called stopping sets on a bipartite graph, which is related to a simple algorithm called peeling algorithm.
A connected digraph in which the in-degree of any vertex equals its out-degree is Eulerian, this baseline result is used as the basis of existence proofs for universal cycles (also known as generalized deBruijn cycles or U-cycles) of several combinatorial objects. We extend the body of known results by presenting new results on the existence of universal cycles of monotone, augmented onto, and Lipschitz functions in addition to universal cycles of certain types of lattice paths and random walks.
It is well known that Universal Cycles of $k$-letter words on an $n$-letter alphabet exist for all $k$ and $n$. In this paper, we prove that Universal Cycles exist for restricted classes of words, including: non-bijections, equitable words (under suitable restrictions), ranked permutations, and passwords.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
