All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 79

Showing per page

Combinatorial properties of infinite words associated with cut-and-project sequences

Louis-Sébastien Guimond, Zuzana Masáková, Edita Pelantová (2003)

Journal de théorie des nombres de Bordeaux

The aim of this article is to study certain combinatorial properties of infinite binary and ternary words associated to cut-and-project sequences. We consider here the cut-and-project scheme in two dimensions with general orientation of the projecting subspaces. We prove that a cut-and-project sequence arising in such a setting has always either two or three types of distances between adjacent points. A cut-and-project sequence thus determines in a natural way a symbolic sequence (infinite word)...

Combining constraint Propagation and meta-heuristics for searching a Maximum Weight Hamiltonian Chain

Yves Caseau (2006)

RAIRO - Operations Research

This paper presents the approach that we developed to solve the ROADEF 2003 challenge problem. This work is part of a research program whose aim is to study the benefits and the computer-aided generation of hybrid solutions that mix constraint programming and meta-heuristics, such as large neighborhood search (LNS). This paper focuses on three contributions that were obtained during this project: an improved method for propagating Hamiltonian chain constraints, a fresh look at limited discrepancy...

Comparing Complexity Functions of a Language and Its Extendable Part

Arseny M. Shur (2008)

RAIRO - Theoretical Informatics and Applications

Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.

Compatibility relations on codes and free monoids

Tomi Kärki (2008)

RAIRO - Theoretical Informatics and Applications

A compatibility relation on letters induces a reflexive and symmetric relation on words of equal length. We consider these word relations with respect to the theory of variable length codes and free monoids. We define an (R,S)-code and an (R,S)-free monoid for arbitrary word relations R and S. Modified Sardinas-Patterson algorithm is presented for testing whether finite sets of words are (R,S)-codes. Coding capabilities of relational codes are measured algorithmically by finding minimal and maximal relations....

Complexité et automates cellulaires linéaires

Valérie Berthé (2010)

RAIRO - Theoretical Informatics and Applications

The aim of this paper is to evaluate the growth order of the complexity function (in rectangles) for two-dimensional sequences generated by a linear cellular automaton with coefficients in ℤ / l ℤ , and polynomial initial condition. We prove that the complexity function is quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.

Complexity of Hartman sequences

Christian Steineder, Reinhard Winkler (2005)

Journal de Théorie des Nombres de Bordeaux

Let T : x ↦ x + g be an ergodic translation on the compact group C and M ⊆ C a continuity set, i.e. a subset with topological boundary of Haar measure 0. An infinite binary sequence a : ℤ ↦ { 0 , 1 } defined by a ( k ) = 1 if T k ( 0 C ) ∈ M and a ( k ) = 0 otherwise, is called a Hartman sequence. This paper studies the growth rate of P a ( n ) , where P a ( n ) denotes the number of binary words of length n ∈ ℕ occurring in a . The growth rate is always subexponential and this result is optimal. If T is an ergodic translation x ↦ x + α ...

Currently displaying 21 – 40 of 79