Page 1 Next

Displaying 1 – 20 of 41

Showing per page

Sets with two associative operations

Teimuraz Pirashvili (2003)

Open Mathematics

In this paper we consider duplexes, which are sets with two associative binary operations. Dimonoids in the sense of Loday are examples of duplexes. The set of all permutations carries a structure of a duplex. Our main result asserts that it is a free duplex with an explicitly described set of generators. The proof uses a construction of the free duplex with one generator by planary trees.

Solving word equations

Habib Abdulrab (1990)

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

Some decidable congruences of free monoids

Jaroslav Ježek (1999)

Czechoslovak Mathematical Journal

Let W be the free monoid over a finite alphabet A . We prove that a congruence of W generated by a finite number of pairs a u , u , where a A and u W , is always decidable.

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

Currently displaying 1 – 20 of 41

Page 1 Next