Search results for "LYN"
showing 10 items of 910 documents
On generalized Lyndon words
2018
Abstract A generalized lexicographical order on infinite words is defined by choosing for each position a total order on the alphabet. This allows to define generalized Lyndon words. Every word in the free monoid can be factorized in a unique way as a nonincreasing factorization of generalized Lyndon words. We give new characterizations of the first and the last factor in this factorization as well as new characterization of generalized Lyndon words. We also give more specific results on two special cases: the classical one and the one arising from the alternating lexicographical order.
Classical and Quantum Annealing in the Median of Three Satisfiability
2011
We determine the classical and quantum complexities of a specific ensemble of three-satisfiability problems with a unique satisfying assignment for up to N = 100 and 80 variables, respectively. In the classical limit, we employ generalized ensemble techniques and measure the time that a Markovian Monte Carlo process spends in searching classical ground states. In the quantum limit, we determine the maximum finite correlation length along a quantum adiabatic trajectory determined by the linear sweep of the adiabatic control parameter in the Hamiltonian composed of the problem Hamiltonian and the constant transverse field Hamiltonian. In the median of our ensemble, both complexities diverge e…
PRINCIPAL POLYNOMIAL ANALYSIS
2014
© 2014 World Scientific Publishing Company. This paper presents a new framework for manifold learning based on a sequence of principal polynomials that capture the possibly nonlinear nature of the data. The proposed Principal Polynomial Analysis (PPA) generalizes PCA by modeling the directions of maximal variance by means of curves instead of straight lines. Contrarily to previous approaches PPA reduces to performing simple univariate regressions which makes it computationally feasible and robust. Moreover PPA shows a number of interesting analytical properties. First PPA is a volume preserving map which in turn guarantees the existence of the inverse. Second such an inverse can be obtained…
A permutation code preserving a double Eulerian bistatistic
2016
Visontai conjectured in 2013 that the joint distribution of ascent and distinct nonzero value numbers on the set of subexcedant sequences is the same as that of descent and inverse descent numbers on the set of permutations. This conjecture has been proved by Aas in 2014, and the generating function of the corresponding bistatistics is the double Eulerian polynomial. Among the techniques used by Aas are the M\"obius inversion formula and isomorphism of labeled rooted trees. In this paper we define a permutation code (that is, a bijection between permutations and subexcedant sequences) and show the more general result that two $5$-tuples of set-valued statistics on the set of permutations an…
On prefix normal words and prefix normal forms
2016
A $1$-prefix normal word is a binary word with the property that no factor has more $1$s than the prefix of the same length; a $0$-prefix normal word is defined analogously. These words arise in the context of indexed binary jumbled pattern matching, where the aim is to decide whether a word has a factor with a given number of $1$s and $0$s (a given Parikh vector). Each binary word has an associated set of Parikh vectors of the factors of the word. Using prefix normal words, we provide a characterization of the equivalence class of binary words having the same set of Parikh vectors of their factors. We prove that the language of prefix normal words is not context-free and is strictly contai…
Bayesian inference for the extremal dependence
2016
A simple approach for modeling multivariate extremes is to consider the vector of component-wise maxima and their max-stable distributions. The extremal dependence can be inferred by estimating the angular measure or, alternatively, the Pickands dependence function. We propose a nonparametric Bayesian model that allows, in the bivariate case, the simultaneous estimation of both functional representations through the use of polynomials in the Bernstein form. The constraints required to provide a valid extremal dependence are addressed in a straightforward manner, by placing a prior on the coefficients of the Bernstein polynomials which gives probability one to the set of valid functions. The…
Determinantal sets, singularities and application to optimal control in medical imagery
2016
International audience; Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast between two biological matters on the pictures. Geometric optimal control leads us here to analyze mero-morphic vector fields depending upon physical parameters , and having their singularities defined by a deter-minantal variety. The involved matrix has polynomial entries with respect to both the state variables and the parameters. Taking into account the physical constraints of the problem, one needs to classify, with respect to the parameters, the number of real singularities lying in som…
The graded identities of upper triangular matrices of size two
2002
AbstractLet UT2 be the algebra of 2×2 upper triangular matrices over a field F. We first classify all possible gradings on UT2 by a group G. It turns out that, up to isomorphism, there is only one non-trivial grading and we study all the graded polynomial identities for such algebra. In case F is of characteristic zero we give a complete description of the space of multilinear graded identities in the language of Young diagrams through the representation theory of the hyperoctahedral group. We finally establish a result concerning the rate of growth of the identities for such algebra by proving that its sequence of graded codimensions has almost polynomial growth.
POLYNOMIAL IDENTITIES ON SUPERALGEBRAS AND ALMOST POLYNOMIAL GROWTH
2001
Let A be a superalgebra over a field of characteristic zero. In this paper we investigate the graded polynomial identities of A through the asymptotic behavior of a numerical sequence called the sequence of graded codimensions of A. Our main result says that such sequence is polynomially bounded if and only if the variety of superalgebras generated by A does not contain a list of five superalgebras consisting of a 2-dimensional algebra, the infinite dimensional Grassmann algebra and the algebra of 2 × 2 upper triangular matrices with trivial and nontrivial gradings. Our main tool is the representation theory of the symmetric group.
Almost polynomial growth: Classifying varieties of graded algebras
2015
Let G be a finite group, V a variety of associative G-graded algebras and c (V), n = 1, 2, …, its sequence of graded codimensions. It was recently shown by Valenti that such a sequence is polynomially bounded if and only if V does not contain a finite list of G-graded algebras. The list consists of group algebras of groups of order a prime number, the infinite-dimensional Grassmann algebra and the algebra of 2 × 2 upper triangular matrices with suitable gradings. Such algebras generate the only varieties of G-graded algebras of almost polynomial growth, i.e., varieties of exponential growth such that any proper subvariety is polynomially bounded. In this paper we completely classify all sub…