Displaying 301 – 320 of 456

Showing per page

On the decidability of semigroup freeness∗

Julien Cassaigne, Francois Nicolas (2012)

RAIRO - Theoretical Informatics and Applications

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. 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....

On the decidability of semigroup freeness

Julien Cassaigne, Francois Nicolas (2012)

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

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. 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

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. 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....

On the Delta set of a singular arithmetical congruence monoid

Paul Baginski, Scott T. Chapman, George J. Schaeffer (2008)

Journal de Théorie des Nombres de Bordeaux

If a and b are positive integers with a b and a 2 a mod b , then the set M a , b = { x : x a mod b or x = 1 } is a multiplicative monoid known as an arithmetical congruence monoid (or ACM). For any monoid M with units M × and any x M M × we say that t is a factorization length of x if and only if there exist irreducible elements y 1 , ... , y t of M and x = y 1 y t . Let ( x ) = { t 1 , ... , t j } be the set of all such lengths (where t i < t i + 1 whenever i < j ). The Delta-set of the element x is defined as the set of gaps in ( x ) : Δ ( x ) = { t i + 1 - t i : 1 i < k } and the Delta-set of the monoid M is given by x M M × Δ ( x ) . We consider the Δ ( M ) when M = M a , b is an ACM with...

Currently displaying 301 – 320 of 456