Research @ Chair of Theoretical Computer Science

Our research covers many aspects of Theoretical Computer Science, focussing on: efficient graph algorithms, parameterized algorithms and complexity, approximation algorithms and complexity, formal languages and grammar induction.

A good first impression is obtained by browsing through our publications.

In the following, you can find a list of papers of members of our research group of this year. Regarding previous years, we refer to the menu to the left. For complete lists of publications, we refer to the homepages of each of the group members.

Publications

Accepted for publication in journals:

  • Henning Fernau, Lakshmanan Kuppusamy, Rufus Oladele, Indhumathi Raman. Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars. Fundamenta Informaticae.
  • Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman. On the computational completeness of matrix simple semi-conditional grammars. Information and Computation.
  • Henning Fernau, Lakshmanan Kuppusamy, Rufus Oladele, Indhumathi Raman. Improved Descriptional Complexity Results on Generalized Forbidding Grammars. Discrete Applied Mathematics.

  • Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid. On the Complexity of the Smallest Grammar Problem over Fixed Alphabets. Theory of Computing Systems.

  • Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid, Sue Whitesides. Combinatorial Properties and Recognition of Unit Square Visibility Graphs. Discrete & Computational Geometry.