16 citations · 48 across the 12 of their papers we have counts for
12 papers
Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More
Julien Cassaigne, Vesa Halava, Tero Harju +1
We study the decidability of three well-known problems related to integer matrix multiplication: Mortality (M), Zero in the Left-Upper Corner (Z), and Zero in the Right-Upper Corne…
Intractability of the Minimum-Flip Supertree problem and its variants
Sebastian Böcker, Quang Bao Anh Bui, Francois Nicolas +1
Computing supertrees is a central problem in phylogenetics. The supertree method that is by far the most widely used today was introduced in 1992 and is called Matrix Representatio…
Various complexity results for computational mass spectrometry problems
Francois Nicolas, Sebastian Böcker
Define Minimum Soapy Union (MinSU) as the following optimization problem: given a -tuple of finite integer sets, find a -tuple of…
On polynomial growth functions of D0L-systems
Julien Cassaigne, Francois Nicolas
The aim of this paper is to prove that every polynomial function that maps the natural integers to the positive integers is the growth function of some D0L-system.
On the Morse-Hedlund complexity gap
Julien Cassaigne, Francois Nicolas
In 1938, Morse and Hedlund proved that the subword complexity function of an infinite word is either bounded or at least linearly growing. In 1982, Ehrenfeucht and Rozenberg proved…
On the decidability of semigroup freeness
Julien Cassaigne, Francois Nicolas
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 of S, decide whether ea…