Displaying similar documents to “ Some decision problems on integer matrices”

On the decidability of semigroup freeness

Julien Cassaigne, Francois Nicolas (2012)

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

Similarity:

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup is defined as: given a finite subset  ⊆ , decide whether each element of has at most one factorization over . To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In 1991, Klarner, Birget and Satterfield proved the undecidability...

On the decidability of semigroup freeness

Julien Cassaigne, Francois Nicolas (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup is defined as: given a finite subset  ⊆ , decide whether each element of has at most one factorization over . To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free...

On the decidability of semigroup freeness

Julien Cassaigne, Francois Nicolas (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup is defined as: given a finite subset  ⊆ , decide whether each element of has at most one factorization over . To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free...

Block Factorization of Hankel Matrices and Euclidean Algorithm

S. Belhaj (2010)

Mathematical Modelling of Natural Phenomena

Similarity:

It is shown that a real Hankel matrix admits an approximate block diagonalization in which the successive transformation matrices are upper triangular Toeplitz matrices. The structure of this factorization was first fully discussed in [1]. This approach is extended to obtain the quotients and the remainders appearing in the Euclidean algorithm applied to two polynomials () and () of degree and , respectively, whith < ...

Strongly locally testable semigroups with commuting idempotents and related languages

Carla Selmi (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

If we consider words over the alphabet which is the set of all elements of a semigroup , then such a word determines an element of : the product of the letters of the word. is strongly locally testable if whenever two words over the alphabet have the same factors of a fixed length , then the products of the letters of these words are equal. We had previously proved [19] that the syntactic semigroup of a rational language is strongly locally testable if and only if is both locally...