Equations in words: An algorithmic contribution.
Équations linéaires dans les anneaux de polynômes
Equations on partial words
It is well-known that some of the most basic properties of words, like the commutativity () and the conjugacy (), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation has only periodic solutions in a free monoid, that is, if holds with integers , then there exists a word such that are powers of . This result, which received a lot of attention, was first proved by Lyndon and...
Equations on partial words
It is well-known that some of the most basic properties of words, like the commutativity (xy = yx) and the conjugacy (xz = zy), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation xMyN = zP has only periodic solutions in a free monoid, that is, if xMyN = zP holds with integers m,n,p ≥ 2, then there exists a word w such that x, y, z are powers of w. This result, which received a lot...
Equations on the semidirect product of a finite semilattice by a -trivial monoid of height
Equi-partitioning of higher-dimensional hyper-rectangular grid graphs.
Equitable Probabilistic Elections in Ring Networks
Equivalence of compositional expressions and independence relations in compositional models
We generalize Jiroušek’s (right) composition operator in such a way that it can be applied to distribution functions with values in a “semifield“, and introduce (parenthesized) compositional expressions, which in some sense generalize Jiroušek’s “generating sequences” of compositional models. We say that two compositional expressions are equivalent if their evaluations always produce the same results whenever they are defined. Our first result is that a set system is star-like with centre if...
Equivalences and Congruences on Infinite Conway Games∗
Taking the view that infinite plays are draws, we study Conway non-terminating games and non-losing strategies. These admit a sharp coalgebraic presentation, where non-terminating games are seen as a final coalgebra and game contructors, such as disjunctive sum, as final morphisms. We have shown, in a previous paper, that Conway’s theory of terminating games can be rephrased naturally in terms of game (pre)congruences. Namely, various...
Equivalences and Congruences on Infinite Conway Games∗
Taking the view that infinite plays are draws, we study Conway non-terminating games and non-losing strategies. These admit a sharp coalgebraic presentation, where non-terminating games are seen as a final coalgebra and game contructors, such as disjunctive sum, as final morphisms. We have shown, in a previous paper, that Conway’s theory of terminating games can be rephrased naturally in terms of game (pre)congruences. Namely, various...
Erasing automata recognize more than context-free languages
Ergodic Properties of Certain Surjective Cellular Automata.
Errata : «Les hiérarchies de parties et leur demi-treillis»
Erratum: Equivalence of compositional expressions and independence relations in compositional models
Error frequency - regulator of the teaching algorithm
Establishing Order in Planar Subdivisions.
Estimates for H2 functions with concentration at low degrees and applications to complex symbolic computation.
Estimating composite functions by model selection
We consider the problem of estimating a function on for large values of by looking for some best approximation of by composite functions of the form . Our solution is based on model selection and leads to a very general approach to solve this problem with respect to many different types of functions and statistical frameworks. In particular, we handle the problems of approximating by additive functions, single and multiple index models, artificial neural networks, mixtures of Gaussian...
Estimating the value of contracts. A simulation study
Estimation of the algorithmic complexity of classes of computable models.