All my research interests (and chronological paper list)

Here is an IN PROGRESS listing of every area I have worked on, roughly in the order of adoption (most ancient first) :

1. Formal Languages and Combinatorics on Words

[-]
[+]

Results in formal language theory.

 

1. Contextual languages.

to write.

2. Structural equivalence notions for L-systems.

to write

[-]
[+]

Results in Combinatorics on Words.

1. Self-reading sequences.

to write.

2. Recursive function theory, later Computational Complexity

[-]
[+]

Effective category in recursive function theory.

 

1. Approximability of the Minimum Entropy Set Cover on sparse instances.

MESC is a problem initially studied by Halperin and Karp (and Cardinal et al.), initially motivated by a problem from computational biology (haplotype resolution)In paper [2] we give a better approximation guarantee for sparse instances of MESC.

2. The Minimum Entropy Submodular Set Cover problem and its approximability.

In paper [9] (chronologically the first we wrote on this topic) we generalize the problem to Minimal Entropy Submodular Set Cover (MESSC), a framework that captures many interesting combinatorial subproblems.We give a guarantee for the performance approximation guarantee of the GREEDY algorithm that is almost as good as the one available for (the same algorithm on) MESC