4 citations · 10 across the 4 of their papers we have counts for
4 papers
A simple, polynomial-time algorithm for the matrix torsion problem
Francois Nicolas
The Matrix Torsion Problem (MTP) is: given a square matrix M with rational entries, decide whether two distinct powers of M are equal. It has been shown by Cassaigne and the author…
Asymptotic behavior of growth functions of D0L-systems
Julien Cassaigne, Christian Mauduit, Francois Nicolas
A D0L-system is a triple (A, f, w) where A is a finite alphabet, f is an endomorphism of the free monoid over A, and w is a word over A. The D0L-sequence generated by (A, f, w) is…
(Generalized) Post Correspondence Problem and semi-Thue systems
Francois Nicolas
Let PCP(k) denote the Post Correspondence Problem for k input pairs of strings. Let ACCESSIBILITY(k) denote the the word problem for k-rule semi-Thue systems. In 1980, Claus showed…
Solving the Maximum Agreement SubTree and the Maximum Compatible Tree problems on many bounded degree trees
Sylvain Guillemot, Francois Nicolas
Given a set of leaf-labeled trees with identical leaf sets, the well-known "Maximum Agreement SubTree" problem (MAST) consists of finding a subtree homeomorphically included in all…