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 67

Showing per page

Some algorithms to compute the conjugates of Episturmian morphisms

Gwenael Richomme (2010)

RAIRO - Theoretical Informatics and Applications

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...

Some decision problems on integer matrices

Christian Choffrut, Juhani Karhumäki (2005)

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

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...

Some decision problems on integer matrices

Christian Choffrut, Juhani Karhumäki (2010)

RAIRO - Theoretical Informatics and Applications

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...

Some graphic uses of an even number of odd nodes

Kathie Cameron, Jack Edmonds (1999)

Annales de l'institut Fourier

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.

Some infinite products with interesting continued fraction expansions

C. G. Pinner, A. J. Van der Poorten, N. Saradha (1993)

Journal de théorie des nombres de Bordeaux

We display several infinite products with interesting continued fraction expansions. Specifically, for various small values of k necessarily excluding k = 3 since that case cannot occur, we display infinite products in the field of formal power series whose truncations yield their every k -th convergent.

Square-root rule of two-dimensional bandwidth problem

Lan Lin, Yixun Lin (2011)

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

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...

Square-root rule of two-dimensional bandwidth problem∗

Lan Lin, Yixun Lin (2012)

RAIRO - Theoretical Informatics and Applications

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...

Squares and cubes in Sturmian sequences

Artūras Dubickas (2009)

RAIRO - Theoretical Informatics and Applications

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.

Squares and overlaps in the Thue-Morse sequence and some variants

Shandy Brown, Narad Rampersad, Jeffrey Shallit, Troy Vasiga (2006)

RAIRO - Theoretical Informatics and Applications

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