Displaying similar documents to “On real-time Turing machines”

On parallel deletions applied to a word

Lila Kari, Alexandru Mateescu, Gheorghe Paun, Arto Salomaa (1995)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

On the number of squares in partial words

Vesa Halava, Tero Harju, Tomi Kärki (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The theorem of Fraenkel and Simpson states that the maximum number of distinct squares that a word  of length  can contain is less than . This is based on the fact that no more than two squares can have their last occurrences starting at the same position. In this paper we show that the maximum number of the last occurrences of squares per position in a partial word containing one hole is , where is the size of the alphabet. Moreover, we prove that the number of distinct squares in...

An optimal scaling law for finite element approximations of a variational problem with non-trivial microstructure

Andrew Lorent (2001)

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

Similarity:

In this note we give sharp lower bounds for a non-convex functional when minimised over the space of functions that are piecewise affine on a triangular grid and satisfy an affine boundary condition in the second lamination convex hull of the wells of the functional.

A note on the number of squares in a partial word with one hole

Francine Blanchet-Sadri, Robert Mercaş (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length is bounded by since at each position there are at most two distinct squares whose last occurrence starts. In this paper, we investigate squares in partial words with one hole, or sequences over a finite alphabet that have a “do not know” symbol or “hole”. A square in a partial word over a given alphabet has the form where is with , and consequently, such square is compatible...