Search results for "Combinatorics"

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…

Abelian antipowers in infinite words

2019

Abstract An abelian antipower of order k (or simply an abelian k-antipower) is a concatenation of k consecutive words of the same length having pairwise distinct Parikh vectors. This definition generalizes to the abelian setting the notion of a k-antipower, as introduced in Fici et al. (2018) [7] , that is a concatenation of k pairwise distinct words of the same length. We aim to study whether a word contains abelian k-antipowers for arbitrarily large k. S. Holub proved that all paperfolding words contain abelian powers of every order (Holub, 2013 [8] ). We show that they also contain abelian antipowers of every order.

Fuzzy Smoothed Composition of Local Mapping Transformations for Non-rigid Image Registration

2009

This paper presents a novel method for medical image regis- tration. The global transformation is obtained by composing affine trans- formations, which are recovered locally from given landmarks. Transfor- mations of adjacent regions are smoothed to avoid blocking artifacts, so that a unique continuous and differentiable global function is obtained. Such composition is operated using a technique derived from fuzzy C- means clustering. The method was successfully tested on several datasets; results, both qualitative and quantitative, are shown. Comparisons with other methods are reported. Final considerations on the efficiency of the technique are explained.

Random Stability of an Additive-Quadratic-Quartic Functional Equation

2010

Using the fixed point method, we prove the generalized Hyers-Ulam stability of the following additive-quadratic-quartic functional equation f(x+2y)+f(x−2y)=2f(x+y)+2f(−x−y)+2f(x−y)+2f(y−x)−4f(−x)−2f(x)+f(2y)+f(−2y)−4f(y)−4f(−y) in complete random normed spaces.

Computing the Arrangement of Circles on a Sphere, with Applications in Structural Biology

2009

International audience; Balls and spheres are the simplest modeling primitives after affine ones, which accounts for their ubiquitousness in Computer Science and Applied Mathematics. Amongst the many applications, we may cite their prevalence when it comes to modeling our ambient 3D space, or to handle molecular shapes using Van der Waals models. If most of the applications developed so far are based upon simple geometric tests between balls, in particular the intersection test, a number of applications would obviously benefit from finer pieces of information. Consider a sphere $S_0$ and a list of circles on it, each such circle stemming from the intersection between $S_0$ and another spher…

Homeomorphic graph manifolds: A contribution to the μ constant problem

1999

Abstract We give a characterization, in terms of homological data in covering spaces, of those maps between (3-dimensional) graph manifolds which are homotopic to homeomorphisms. As an application we give a condition on a cobordism between graph manifolds that guarantees that they are homeomorphic. This in turn is applied to give a partial result on the μ -constant problem in (complex) dimension three.