Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the realization of double occurrence words
522
0
0.0
(
0
)
Authors
Blerta Shtylla
Ask ChatGPT about the research
No Arabic abstract
Let S be a double occurrence word, and let M_S be the words interlacement matrix, regarded as a matrix over GF(2). Gauss addressed the question of which double occurrence words are realizable by generic closed curves in the plane. We reformulate answers given by Rosenstiehl and by de Fraysseix and Ossona de Mendez to give new graph-theoretic and algebraic characterizations of realizable words. Our algebraic characterization is especially pleasing: S is realizable if and only if there exists a diagonal matrix D_S such that M_S+D_S is idempotent over GF(2).
rate research
Read More
A double occurrence word (DOW) is a word in which every symbol appears exactly twice; two DOWs are equivalent if one is a symbol-to-symbol image of the other. We consider the so called repeat pattern ($alphaalpha$) and the return pattern ($alphaalpha^R$), with gaps allowed between the $alpha$s. These patterns generalize square and palindromic factors of DOWs, respectively. We introduce a notion of inserting repeat/return words into DOWs and study how two distinct insertions into the same word can produce equivalent DOWs. Given a DOW $w$, we characterize the structure of $w$ which allows two distinct insertions to yield equivalent DOWs. This characterization depends on the locations of the insertions and on the length of the inserted repeat/return words and implies that when one inserted word is a repeat word and the other is a return word, then both words must be trivial (i.e., have only one symbol). The characterization also introduces a method to generate families of words recursively.
In this paper, we investigate statistics on alternating words under correspondence between ``possible reflection paths within several layers of glass and ``alternating words. For $v=(v_1,v_2,cdots,v_n)inmathbb{Z}^{n}$, we say $P$ is a path within $n$ glass plates corresponding to $v$, if $P$ has exactly $v_i$ reflections occurring at the $i^{rm{th}}$ plate for all $iin{1,2,cdots,n}$. We give a recursion for the number of paths corresponding to $v$ satisfying $v in mathbb{Z}^n$ and $sum_{igeq 1} v_i=m$. Also, we establish recursions for statistics around the number of paths corresponding to a given vector $vinmathbb{Z}^n$ and a closed form for $n=3$. Finally, we give a equivalent condition for the existence of path corresponding to a given vector $v$.
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.
We show that, in an alphabet of $n$ symbols, the number of words of length $n$ whose number of different symbols is away from $(1-1/e)n$, which is the value expected by the Poisson distribution, has exponential decay in $n$. We use Laplaces method for sums and known bounds of Stirling numbers of the second kind. We express our result in terms of inequalities.
Stankova and West showed that for any non-negative integer $s$ and any permutation $gamma$ of ${4,5,dots,s+3}$ there are as many permutations that avoid $231gamma$ as there are that avoid $312gamma$. We extend this result to the setting of words.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
