4 citations · 10 across the 4 of their papers we have counts for
Showing cs.DMShow all
3 papers · 1 filter
cs.DM2008★ 3 cited
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…
cs.DM2008★ 1 cited
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…
cs.DM2008★ 4 cited
(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…