Search results for "combinatoric"

Forbidden Factors and Fragment Assembly

2002

In this paper we approach the fragment assembly problem by using the notion of minimal forbidden factors introduced in previous paper. Denoting by M(w) the set of minimal forbidden factors of a word w, we first focus on the evaluation of the size of elements in M(w) and on designing of an algorithm to recover the word w from M(w). Actually we prove that for a word w randomly generated by a memoryless source with identical symbol probabilities, the maximal length m(w) of words in M(w) is logarithmic and that the reconstruction algorithm runs in linear time. These results have an interesting application to the fragment assembly problem, i.e. reconstruct a word w from a given set I of substrin…

Kontsevich–Zagier Periods

2017

We compare the set of Kontsevich–Zagier periods defined by integrals over semi-algebraic subsets of \(\mathbb {R}^n\) with cohomological periods.

On the packing sums of pairs

1993

Abstract This paper is concerned with the determination of the length of the largest interval of consecutive integers of the set hA k , where A k is a sequence of integers which is a B h -sequence.

Some Generalizations of a Simion Schmidt Bijection

2007

In 1985, Simion and Schmidt gave a constructive bijection φ from the set of all length (n-1) binary strings having no two consecutive 1s to the set of all length n permutations avoiding all patterns in {123,132,213}. In this paper, we generalize φ to an injective function from {0,1}n-1 to the set Sn of all length n permutations and derive from it four bijections φ : P →Q where P⊆{0,1}n-1 and Q ⊂ Sn. The domains are sets of restricted binary strings and the codomains are sets of pattern-avoiding permutations. As a particular case we retrieve the original Simion–Schmidt bijection. We also show that the bijections obtained are actually combinatorial isomorphisms, i.e. closeness-preserving bije…

On the number of factors of Sturmian words

1991

Abstract We prove that for m ⩾1, card( A m ) = 1+∑ m i =1 ( m − i +1) ϕ ( i ) where A m is the set of factors of length m of all the Sturmian words and ϕ is the Euler function. This result was conjectured by Dulucq and Gouyou-Beauchamps (1987) who proved that this result implies that the language (∪ m ⩾0 A m ) c is inherently ambiguous. We also give a combinatorial version of the Riemann hypothesis.

Regular k-Surfaces

2012

Roughly speaking, a regular surface in \(\mathbb{R}^3\) is a two-dimensional set of points, in the sense that it can be locally described by two parameters (the local coordinates) and with the property that it is smooth enough (that is, there are no vertices, edges, or self-intersections) to guarantee the existence of a tangent plane to the surface at each point.

On The Maximum Number of Abelian Squares in a Word

2014

Strings (aka sequences or words) form the most basic and natural data structure. They occur whenever information is electronically transmitted (as bit streams), when natural language text is spoken or written down (as words over, for example, the Latin alphabet), in the process of heredity transmission in living cells (through DNA sequences) or the protein synthesis (assequence of amino acids), and in many more different contexts

Words, Trees and Automata Minimization

2013

In this paper we explore some connections between some combinatorial properties of words and the study of extremal cases of the automata minimization process. An intermediate role is played by the notion od word trees for which some properties of words are generalized. In particular, we describe an infinite family of binary automata, called word automata and constructed by using standard sturmian words and more specifically Fibonacci words, that represent the extremal case of some well known automata minimization algorithms, such as Moore’s and Hopcroft’s methods. As well as giving an overview of the main results in this context, the main purpose of this paper is to prove that, even if a re…

Indexed Two-Dimensional String Matching

2016

A New Class of Searchable and Provably Highly Compressible String Transformations

2019

The Burrows-Wheeler Transform is a string transformation that plays a fundamental role for the design of self-indexing compressed data structures. Over the years, researchers have successfully extended this transformation outside the domains of strings. However, efforts to find non-trivial alternatives of the original, now 25 years old, Burrows-Wheeler string transformation have met limited success. In this paper we bring new lymph to this area by introducing a whole new family of transformations that have all the "myriad virtues" of the BWT: they can be computed and inverted in linear time, they produce provably highly compressible strings, and they support linear time pattern search direc…