uni-potsdam.de

You are using an old browser with security vulnerabilities and can not use the features of this website.

Here you will see how you can easily upgrade your browser.

  • Institute for Computer Science

Talks by Prof. Dr. Victor Mitrana on 29.6. and 6.7.2017

Within the block seminar "Computational Models Inspired by Nature" organized by PD Dr. Henning Bordihn, Prof. Dr. Victor Mitrana of the University Bukarest will give two scientific talks. All those interested are cordially invited.

1. Talk: Thursday, 29.06.2017, 6:15 pm, Campus Griebnitzsee, building 4, room 0.02
A New Operation Suggested by DNA Biochemistry: Hairpin Completion

We propose a new formal operation on words and languages suggested by DNA manipulation, called hairpin completion. By this operation, that is based on the Watson-Crick complementarity, annealing and PCR, one can generate a set of words, starting from a single word.This operation is considered here as an abstract operation on formal languages. We settle the closure properties under the non-iterated version of this operation of some classes in the Chomsky hierarchy as well as some complexity classes.

Then we consider a few algorithmic problems regarding the hairpin completion. The first problem we consider is the membership problem of the completion of a language. We propose an O(nf(n)) time recognition algorithm for the hairpin completion of a language recognizable in O(f(n)) time. We show that the n factor is not needed in the case of hairpin completion of regular and context-free languages.

The iterated version of hairpin completion is then discussed. We propose an O(n2f(n)) time recognition algorithm for the iterated hairpin completion of a language recognizable in O(f(n)) time. The n2 factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n in the case of iterated hairpin completion of regular languages. We then define the hairpin completion distance between two words and present a cubic time algorithm for computing this distance. A linear time algorithm for deciding whether or not the hairpin completion distance with respect to a given word is connected is also discussed. Finally, we give a short list of open problems which appear attractive to us.

2. Talk: Thursday, 06.07.2017, 8:15 am (!), Campus Griebnitzsee, building 4, room 0.02
Computing Translocation Distances

A basic problem in the area of combinatorial algorithms for genome evolution is to determine the minimum number of large scale evolutionary events (genome rearrangements) that transform a genome into another. We consider two translocation operations suggested by the genome rearrangements. In this talk chromosomes are viewed as being linear strings that exchange each other prefixes in the translocation process. We define a distance between a pair of multichromosomal genomes and examine the complexity of computing this distance in the case of uniform translocation.

Our work differs from previous approaches in several respects: the strings representing chromosomes may have multiple occurrences of the same symbol, they may have common symbols, the number of copies of all strings in the initial set is assumed arbitrarily large. One exact algorithm and one approximation algorithms, both of them based on greedy strategies, are discussed. We present an exact polynomial algorithm when the target set is a singleton while a 2-approximation algorithm is provided when considering arbitrary target sets. Some open problems are finally formulated.


From the Institute of Computer Science

Für MINT-Fächer begeistern – Verleihung der Dr. Hans Riegel-Fachpreise an forschende Abiturienten

Herausragende Arbeiten von Schülerinnen und Schülern des Landes Brandenburg in den Fächern Biologie, Chemie, Geographie, Informatik, Mathematik und Physik werden am 16. Juni 2017 mit den Dr. Hans Riegel-Fachpreisen ausgezeichnet....
07. Jun 2017
Herausragende Arbeiten von Schülerinnen und Schülern des Landes Brandenburg in den Fächern Biologie, Chemie, Geographie, Informatik, Mathematik und Physik werden am 16. Juni 2017 mit den Dr. Hans Riegel-Fachpreisen more ...
Portrait von Prof. Dr. Christian Hammer (Foto: Karla Fritze)

Wie sicher sind unsere Daten? – Antrittsvorlesung von Prof. Dr. Christian Hammer

„Ja, wo fließen sie denn? Sind unsere Daten noch sicher zu bekommen?“ ist der Titel der Antrittsvorlesung von Prof. Dr.-Ing. Christian Hammer am 7. Juni 2017 an der Universität Potsdam. In seiner Forschung beschäftigt sich der...
01. Jun 2017
„Ja, wo fließen sie denn? Sind unsere Daten noch sicher zu bekommen?“ ist der Titel der Antrittsvorlesung von Prof. Dr.-Ing. Christian Hammer am 7. Juni 2017 an der Universität Potsdam. In seiner Forschung beschäftigt more ...

IT-Talente gesucht – Informatik-Olympiade 2017 des Landes Brandenburg an der Universität Potsdam

Noch bis zum 8. Mai können sich IT-begeisterte Schülerinnen und Schüler der 9. bis 13. Klassen für die Teilnahme an der Informatik-Olympiade 2017 des Landes Brandenburg bewerben. Sie findet am 23. und 24. Juni auf dem Campus...
03. May 2017
Noch bis zum 8. Mai können sich IT-begeisterte Schülerinnen und Schüler der 9. bis 13. Klassen für die Teilnahme an der Informatik-Olympiade 2017 des Landes Brandenburg bewerben. Sie findet am 23. und 24. Juni auf dem more ...