Search results for " processing"
showing 10 items of 7549 documents
Languages with mismatches
2007
AbstractIn this paper we study some combinatorial properties of a class of languages that represent sets of words occurring in a text S up to some errors. More precisely, we consider sets of words that occur in a text S with k mismatches in any window of size r. The study of this class of languages mainly focuses both on a parameter, called repetition index, and on the set of the minimal forbidden words of the language of factors of S with errors. The repetition index of a string S is defined as the smallest integer such that all strings of this length occur at most in a unique position of the text S up to errors. We prove that there is a strong relation between the repetition index of S an…
Prototype selection for the nearest neighbour rule through proximity graphs
1997
Abstract In this paper, the Gabriel and Relative Neighbourhood graphs are used to select a suitable subset of prototypes for the Nearest Neighbour rule. Experiments and results are reported showing the effectiveness of the method and comparing its performance to those obtained by classical techniques.
Balance Properties and Distribution of Squares in Circular Words
2008
We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalised to non periodic infinite words as well.
Weak associativity and restricted rotation
2009
A restricted rotation induced by a weak associative law is introduced. The corresponding equivalence relation is identical to the Glivenko congruence on Tamari lattices, i.e. lattices of binary trees endowed by the well-known rotation operation.
Tighter Relations between Sensitivity and Other Complexity Measures
2014
The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004 [11].
Multilevel Bandwidth and Radio Labelings of Graphs
2008
This paper introduces a generalization of the graph bandwidth parameter: for a graph G and an integer k ≤ diam(G), the k-level bandwidth Bk(G)of G is defined by Bk(G) = minγ max{|γ(x)-γ(y)|-d(x, y)+1 : x, y ∈ V (G), d(x, y) ≤ k}, the minimum being taken among all proper numberings γ of the vertices of G. We present general bounds on Bk(G) along with more specific results for k = 2 and the exact value for k = diam(G). We also exhibit relations between the k-level bandwidth and radio k-labelings of graphs from which we derive a upper bound for the radio number of an arbitrary graph.
Two shortest path metrics on well-formed parentheses strings
1996
We present an analysis of two transformations on well-formed parentheses strings. Using a lattice approach, the corresponding least-move distances are computable, the first in linear time and the second in quadratic time.
S_Kernel: A New Symmetry Measure
2005
Symmetry is an important feature in vision. Several detectors or transforms have been proposed. In this paper we concentrate on a measure of symmetry. Given a transform S, the kernel SK of a pattern is defined as the maximal included symmetric sub-set of this pattern. It is easily proven that, in any direction, the optimal axis corresponds to the maximal correlation of a pattern with its flipped version. For the measure we compute a modified difference between respective surfaces of a pattern and its kernel. That founds an efficient algorithm to attention focusing on symmetric patterns.
Periodic Orbits in the Isosceles Three-Body Problem
1991
The Saturn’s satellites Janus and Epimetheus are the first known bodies in the Solar System that has horseshoe orbits in a frame that rotates with uniform angular velocity. Both satellites have similar masses and orbital elements when they are far from one another. Moreover, their orbits are nearly symmetric. In fact, in the past, they have been identify as a unique satellite and afterwards, some mathematical theories about their orbits has been necessaries to understand why they do not collide. In particular, the interest in planar three-body problem with two small masses has increased6. We assume that the two small masses have similar symmetric initial conditions. The aim of this paper is…
Lower and Upper Probability Bounds for Some Conjunctions of Two Conditional Events
2018
In this paper we consider, in the framework of coherence, four different definitions of conjunction among conditional events. In each of these definitions the conjunction is still a conditional event. We first recall the different definitions of conjunction; then, given a coherent probability assessment (x, y) on a family of two conditional events \(\{A|H,B|K\}\), for each conjunction \((A|H) \wedge (B|K)\) we determine the (best) lower and upper bounds for the extension \(z=P[(A|H) \wedge (B|K)]\). We show that, in general, these lower and upper bounds differ from the classical Frechet-Hoeffding bounds. Moreover, we recall a notion of conjunction studied in recent papers, such that the res…