Mini-Workshop

Theoretical Computer Science in Dortmund

A bi-monthly mini-workshop for theoretical computer science at the University of Dortmund. In each session there will be 2-3 conference-length (25 min.) talks.

Next session

The 19th TCS mini-workshop will be hosted by Chair 1.

Time: 16.15, February 22th, 2012

Place: OH16-205

Program:

• Chris Schwiegelshohn: Solving the minimum string cover problem
  • Abstract: A string cover C of a set of strings S is a set of substrings from S such that every string in S can be written as a concatenation of the strings in C. Given costs assigned to each substring from S, the Minimum String Cover (MSC) problem asks for a cover of minimum total cost. This NP-hard problem has so far only been approached from a purely theoretical perspective. We propose a flow-based ILP formulation, whose structure is particularly favorable for a Lagrangian relaxation approach. By making use of the strong bounds obtained through a repeated shortest path computation in a branch-and-bound manner, we show for the first time that non-trivial MSC instances can be solved to provable optimality in reasonable time.
• Sven Rahmann: Welche Herausforderungen bietet die Genomanalyse der theoretischen Informatik?
  • Abstract: Wir stellen aktuelle Probleme der Genominformatik vor und diskutieren, welche grundlegenden theoretischen Fragestellungen sich dahinter verbergen (könnten).
• Ahmet Kara: Decidability Results for Infinite State Systems

  • Abstract: The positive achievements in the field of automatic verification of finite state systems motivated the research on algorithmic methods for infinite state systems.

    In this talk we will be concerned with general conditions on infinite state systems which are sufficient for the termination of several algorithmic procedures. We will introduce well-structured transition systems (WSTSs) as defined by Finkel and Schnoebelen. These are infinite state systems with a well-quasi ordering on the set of states which is compatible with the transition relation. For WSTSs it can be shown that algorithmic problems like reachability, i.e. the question whether a certain set of states is reachable from an initial state, are decidable. Many transition systems like Petri nets and lossy channel systems from various fields of computer science can be seen as WSTSs. We will give some examples from current research where the concept of WSTSs helps to get decidability results.

Previous sessions

MW 18, August 9th, 2011, Chair 1

• Gabriele Kern-Isberner: A Default Logical Semantics for Defeasible Argumentation
  (joint work with Guillermo Simari)

  • Abstract: Defeasible argumentation and default reasoning are usually perceived as two similar, but distinct approaches to commonsense reasoning. In this paper, we combine these two fields by viewing (defeasible resp. default) rules as a common crucial part in both areas. We will make use of possible worlds semantics from default reasoning to provide examples for arguments, and carry over the notion of plausibility to the argumentative framework. Moreover, we base a priority relation between arguments on the tolerance partitioning of system Z and obtain a criterion phrased in system Z terms that ensures warrancy in defeasible argumentation.

• Melanie Schmidt: Adaptive Sampling for Clustering Problems

  • Abstract: Clustering is the problem to partition a given set of objects into subsets called clusters such that objects in the same cluster are similar and objects in different clusters are dissimilar. The k-means problem is a well-known clustering problem where similarity is measured by squared Euclidean distance. The k-means algorithm is a very popular heuristic for this problem which unfortunately does not provide any guality guarantee. In this talk, we review recent improvements of the k-means algorithm by Arthur and Vassilvitzki and then consider possible directions for further research. In particular, we are interested in applications to a generalization of the k-means problem.

• Peter Padawitz: Algebraic, relational and order-based co/induction

  • Abstract: Algebraic induction is a proof rule for showing properties of initial models. Its soundness follows from the fact that initial models do not have proper substructures. Algebraic coinduction is a proof rule for showing equations in final models. Its soundness follows from the fact that final models do not have proper quotients. A proof by algebraic co/induction can be carried out by relational co/induction, which is a proof rule for showing properties of least resp. greatest - not only unary or binary - relations in arbitrary models. Relational co/induction specializes order-based co/induction to the lattice of interpretations of the predicates of the underlying signature. Order-based co/induction works in any complete lattice or co/chain-complete poset. As an example of the use of algebraic coinduction, we show how it simplifies proofs of language equivalence, in particular of conjectures stating that a given context-free grammar generates a given language.

MW 17, Mai 4th, 2011, Chair 1

• Thomas Schwentick: Two-variable logic and Key Constraints on Data Words

  • Abstract: We introduce key constraints for data words and show that it is decidable whether, for a given two-variable sentence $\varphi$ that can refer to the successor relation on positions and a set K of key constraints, there is a data string w that satisfies $\varphi$ and respects K. Here, the formula is allowed to refer to the successor relation but not to the linear order on the positions of the word. As a byproduct, a self-contained exposition of an algorithm that decides satisfiability of such formulas (without key constraints) in 2-NEXPTIME is given.

• Johannes Köster: Proteinhypernetzwerke

  • Abstract: Protein-protein interactions are the fundamental building blocks of biochemical reaction systems underlying cellular functions. Importantly, the complexity and functionality of such systems emerge not from the protein interactions themselves but from the dependencies between these interactions. However, a comprehensive approach for large scale integration of such dependencies is still rather lacking.
    
    We present an approach for endowing protein networks with interaction dependencies using propositional logic, thereby obtaining protein hypernetworks. We illustrate their potential by demonstrating that they improve protein complex prediction in yeast. By modeling the effects of protein perturbations in hypernetworks we derive a perturbation impact score, a novel measure of a protein's functional importance.

• Patrick Krümpelmann: On Influence and Contractions in Defeasible Logic Programming

  • Abstract: We investigate the problem of contraction in Defeasible Logic Programming (DeLP), a logic-based approach for defeasible argumentation. We develop different notions of contraction based on both, the different forms of entailment implicitly existent in argumentation-based formalisms and the influence literals exhibit in the reasoning process. We give translations of widely accepted rationality postulates for belief contraction to our framework. Moreover, we discuss on the applicability of contraction for defeasible argumentation and the role of influence in this matter.

MW 16, January 19th, 2011, Chair 1

MW 15, July 14th, 2010, Chair 1

MW 14, July 14th, 2010, Chair 1

MW 13, February 23th, 2010, Chair 1:

MW 12, December 17th, 2008, Chair 1:

MW 11, July 9th, 2008, Chair 1:

MW 10, May 7th, 2008, Chair 1:

MW 9, April 9th, 2008, Chair 1:

MW 8, November 21st, 2007, Chair 1:

MW 7, June 27th, 2007, Chair 2:

MW 6, February 28th, 2007, Chair 1:

MW 5, December 20th, 2006, Chair 10

MW 4, September 4th, 2006, math. dep. chair of Prof. Skutella:

MW 3, July 10th, 2006, Chair 1:

The workshop took place directly after a guest lecture of Dr. Thomas Eiter (TU Wien), a guest of Prof. Petra Mutzel. Titel: Datenintegration and answer set programming abstract

MW 2, May 22nd, 2006, Chair 11:

MW 1, March 20th, 2006, Chair 1:

Organizers:

Thomas Schwentick

Thomas Zeume

Recognizing Shuffled Languages