Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSimplified numerical form of universal finite type invariant of Gauss words
91
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In the present paper, we study the finite type invariants of Gauss words. In the Polyak algebra techniques, we reduce the determination of the group structure to transformation of a matrix into its Smith normal form and we give the simplified form of a universal finite type invariant by means of the isomorphism of this transformation. The advantage of this process is that we can implement it as a computer program. We obtain the universal finite type invariant of degree 4, 5, and 6 explicitly. Moreover, as an application, we give the complete classification of Gauss words of rank 4 and the partial classification of Gauss words of rank 5 where the distinction of only one pair remains.
rate research
Read More
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.
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.
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.
A universal cycle, or u-cycle, for a given set of words is a circular word that contains each word from the set exactly once as a contiguous subword. The celebrated de Bruijn sequences are a particular case of such a u-cycle, where a set in question is the set $A^n$ of all words of length $n$ over a $k$-letter alphabet $A$. A universal word, or u-word, is a linear, i.e. non-circular, version of the notion of a u-cycle, and it is defined similarly. Removing some words in $A^n$ may, or may not, result in a set of words for which u-cycle, or u-word, exists. The goal of this paper is to study the probability of existence of the universal objects in such a situation. We give lower bounds for the probability in general cases, and also derive explicit answers for the case of removing up to two words in $A^n$, or the case when $k=2$ and $nleq 4$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
