Search results for "Alphabet"
showing 10 items of 68 documents
Coding Binary Trees by Words over an Alphabet with Four Letters
1992
Abstract We propose a new encoding scheme to represent binary trees with n leaves by words of length n over an alphabet with four letters. We give a characterization of these codewords.
On a Conjecture on Bidimensional Words
2003
We prove that, given a double sequence w over the alphabet A (i.e. a mapping from Z2 to A), if there exists a pair (n0, m0) ∈ Z2 such that pw(n0, m0) < 1/100n0m0, then w has a periodicity vector, where pw is the complexity function in rectangles of w.
Universal Lyndon Words
2014
A word w over an alphabet Σ is a Lyndon word if there exists an order defined on Σ for which w is lexicographically smaller than all of its conjugates (other than itself). We introduce and study universal Lyndon words, which are words over an n-letter alphabet that have length n! and such that all the conjugates are Lyndon words. We show that universal Lyndon words exist for every n and exhibit combinatorial and structural properties of these words. We then define particular prefix codes, which we call Hamiltonian lex-codes, and show that every Hamiltonian lex-code is in bijection with the set of the shortest unrepeated prefixes of the conjugates of a universal Lyndon word. This allows us t…
Balancing and clustering of words in the Burrows–Wheeler transform
2011
AbstractCompression algorithms based on Burrows–Wheeler transform (BWT) take advantage of the fact that the word output of BWT shows a local similarity and then turns out to be highly compressible. The aim of the present paper is to study such “clustering effect” by using notions and methods from Combinatorics on Words.The notion of balance of a word plays a central role in our investigation. Empirical observations suggest that balance is actually the combinatorial property of input word that ensure optimal BWT compression. Moreover, it is reasonable to assume that the more balanced the input word is, the more local similarity we have after BWT (and therefore the better the compression is).…
A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay
2012
In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers asso…
A Periodicity Theorem on Words and Applications
1995
We prove a periodicity theorem on words that has strong analogies with the Critical Factorization theorem and we show three applications of it.
Alfabēta spēļu grāmatas vizuāli stilistiskie aspekti
2019
Mūsdienās bērnus ir grūti uzrunāt ar vienkāršām grāmatām. Darba autores mērķis ir izveidot radošu bērnu grāmatu, kas spētu veicināt alfabēta apguvi. Hipotēze: Bērna motivācija apgūt alfabētu paaugstinās, ja grāmata ir radoša ar bērnam saprotamām ilustrācijām. Darba mērķis: Izveidot radošu bērnu alfabēta grāmatu, kura veicinātu tā apguvi. Darba teorētiskajā un empīriskajā daļā mērķis ir apkopot informāciju par grāmatu ilustrāciju tehnikām un to pielietojumiem alfabēta apguvē. Diplomdarbs sastāv no ievada, teorētiskās, empīriskās, radošās nodaļas un apakšnodaļām, secinājumiem un pielikuma. Darba kopējais apjoms ir 51 lapa. Literatūras sarakstā ir 13 grāmatu resursi un 14 interneta resursi.
Positioning Europe for the EPITRANSCRIPTOMICS challenge
2018
WOS: 000444092300018 PubMed ID: 29671387 The genetic alphabet consists of the four letters: C, A, G, and T in DNA and C,A,G, and U in RNA. Triplets of these four letters jointly encode 20 different amino acids out of which proteins of all organisms are built. This system is universal and is found in all kingdoms of life. However, bases in DNA and RNA can be chemically modified. In DNA, around 10 different modifications are known, and those have been studied intensively over the past 20years. Scientific studies on DNA modifications and proteins that recognize them gave rise to the large field of epigenetic and epigenomic research. The outcome of this intense research field is the discovery t…
Popularity of patterns over $d$-equivalence classes of words and permutations
2020
Abstract Two same length words are d-equivalent if they have same descent set and same underlying alphabet. In particular, two same length permutations are d-equivalent if they have same descent set. The popularity of a pattern in a set of words is the overall number of copies of the pattern within the words of the set. We show the far-from-trivial fact that two patterns are d-equivalent if and only if they are equipopular over any d-equivalence class, and this equipopularity does not follow obviously from a trivial equidistribution.
Adversary Lower Bound for the k-sum Problem
2013
We prove a tight quantum query lower bound $\Omega(n^{k/(k+1)})$ for the problem of deciding whether there exist $k$ numbers among $n$ that sum up to a prescribed number, provided that the alphabet size is sufficiently large. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.