|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc040301,
author = {Cassaigne, Julien},
title = {Double Sequences with Complexity $mn+1$},
journal = jalc,
year = 1999,
volume = 4,
number = 3,
pages = {153--170},
keywords = {infinite words, Sturmian sequences, double sequences},
abstract = {For usual infinite words, a classical result of
{\sc Morse} and {\sc Hedlund} states that if the complexity
function satisfies $p(n)\leq n$ for some value of $n$, then
the word is eventually periodic. To generalize this result
to two dimensions (in a way which is still to be precised)
is an open problem.\par
We will focus here on the limit case. In one dimension, the
non-periodic sequences with lowest possible complexity are
Sturmian sequences, for which $p(n)=n+1$ for all $n$; their
structure has been extensively studied. In two dimensions, it
seems that this r\^{o}le could be played by double sequences
with a rectangle complexity equal to $p(m,n)=mn+1$. We give
an exhaustive description of these sequences, showing that
they can be of three different types; in two of these types,
one-dimensional Sturmian sequences are used to code the
boundary between two parts of the plane.}
}