Applications biséquentielles d'un monoïde libre dans un autre
Sur les transductions reconnaissables
Deciding whether a relation defined in Presburger logic can be defined in weaker logics
We consider logics on and which are weaker than Presburger arithmetic and we settle the following decision problem: given a -ary relation on and which are first order definable in Presburger arithmetic, are they definable in these weaker logics? These logics, intuitively, are obtained by considering modulo and threshold counting predicates for differences of two variables.
Preface
Some decision problems on integer matrices
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...
Preface
Periodicity and roots of transfinite strings
This contribution extends the notions of roots and periodicity to strings of transfinite lengths. It shows that given a transfinite string, either it possesses a unique root or the set of its roots are equivalent in a strong way.
Periodicity and roots of transfinite strings
This contribution extends the notions of roots and periodicity to strings of transfinite lengths. It shows that given a transfinite string, either it possesses a unique root or the set of its roots are equivalent in a strong way.
Preface
Preface
Some decision problems on integer matrices
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...
Decision problems among the main subfamilies of rational relations
We consider the four families of recognizable, synchronous, deterministic rational and rational subsets of a direct product of free monoids. They form a strict hierarchy and we investigate the following decision problem: given a relation in one of the families, does it belong to a smaller family? We settle the problem entirely when all monoids have a unique generator and fill some gaps in the general case. In particular, adapting a proof of Stearns, we show that it is recursively decidable whether...
Preface
Page 1