4 citations
- University of ChileCL8 papers
- Centre National de la Recherche ScientifiqueFR4 papers
- Centre de Recherche en Mathématiques de la DécisionFR3 papers
- École Normale Supérieure de LyonFR2 papers
- Institut Universitaire de FranceFR2 papers
- Laboratoire d’Analyse et de Mathématiques AppliquéesFR2 papers
- Adolfo Ibáñez UniversityCL1 paper
- Charles UniversityCZ1 paper
- Chinese University of Hong KongHK1 paper
- Delhi Integrated Multi-Modal Transit SystemIN1 paper
- Georgia Institute of TechnologyUS1 paper
- Institute of Mathematical SciencesIN1 paper
6 papers · 1 filter
Expected length of the longest common subsequence for large alphabets
Marcos Kiwi, Martin Loebl, Jiri Matousek
We consider the length L of the longest common subsequence of two randomly uniformly and independently chosen n character words over a k-ary alphabet. Subadditivity arguments yield…
Universality and Decidability of Number-Conserving Cellular Automata
Andres Moreira
Number-conserving cellular automata (NCCA) are particularly interesting, both because of their natural appearance as models of real systems, and because of the strong restrictions…
Complexity of Langton's Ant
Anahi Gajardo, Andres Moreira, Eric Goles
The virtual ant introduced by C. Langton has an interesting behavior, which has been studied in several contexts. Here we give a construction to calculate any boolean circuit with…
On Conservative and Monotone One-dimensional Cellular Automata and Their Particle Representation
Andres Moreira, Nino Boccara, Eric Goles
Number-conserving (or {\em conservative}) cellular automata have been used in several contexts, in particular traffic models, where it is natural to think about them as systems of…
Genetic Algorithms for the Imitation of Genomic Styles in Protein Backtranslation
Andres Moreira
Several technological applications require the translation of a protein into a nucleic acid that codes for it (``backtranslation''). The degeneracy of the genetic code makes this t…
Domino tilings and related models: space of configurations of domains with holes
Sebastien Desreux, Martin Matamala, Ivan Rapaport +1
We first prove that the set of domino tilings of a fixed finite figure is a distributive lattice, even in the case when the figure has holes. We then give a geometrical interpretat…