The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Episturmian morphisms generalize Sturmian morphisms. They are defined
as compositions of exchange morphisms and two particular morphisms
L, and R. Epistandard morphisms are the morphisms obtained without
considering R. In [14], a general study of these morphims
and of conjugacy of morphisms is given.
Here, given a decomposition of
an Episturmian morphism f
over exchange morphisms and {L,R},
we consider two problems: how to compute
a decomposition of one conjugate of f;
how to compute a...
Given a finite set of matrices with integer entries, consider the question of determining whether the semigroup they generated 1) is free; 2) contains the identity matrix; 3) contains the null matrix or 4) is a group. Even for matrices of dimension , questions 1) and 3) are undecidable. For dimension , they are still open as far as we know. Here we prove that problems 2) and 4) are decidable by proving more generally that it is recursively decidable whether or not a given non singular matrix belongs...
Given a finite set of
matrices with integer entries,
consider the question
of determining whether the semigroup they generated 1) is free; 2) contains the identity matrix; 3) contains the null matrix or 4) is a group.
Even for matrices of dimension 3,
questions 1) and 3) are undecidable.
For dimension
2, they are still open as far as we know.
Here we prove that problems 2) and 4) are decidable
by proving more generally that it is recursively
decidable whether or not a given
non singular matrix
belongs...
Vertex-degree parity in large implicit “exchange graphs” implies some EP theorems asserting the existence of a second object without evidently providing a polytime algorithm for finding a second object.
We display several infinite products with interesting continued fraction expansions. Specifically, for various small values of necessarily excluding since that case cannot occur, we display infinite products in the field of formal power series whose truncations yield their every -th convergent.
The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root...
The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root...
We prove that every Sturmian word ω has infinitely many prefixes of
the form UnVn3, where |Un| < 2.855|Vn| and
limn→∞|Vn| = ∞. In passing, we give a very simple proof of the
known fact that every Sturmian word begins in arbitrarily long squares.
We consider the position and number of occurrences of squares
in the Thue-Morse sequence, and show that the corresponding sequences
are 2-regular. We also prove that changing any finite but nonzero
number of bits in the Thue-Morse sequence creates an overlap, and any
linear subsequence of the Thue-Morse sequence (except those corresponding
to decimation by a power of 2) contains an overlap.
Currently displaying 21 –
40 of
67