Forschungsseminar Informatik und Mathematik (SS 2010)

Abstract: The non-associative bracketing problem asks for the number of distinct ways of inserting parentheses into a string of symbols. It was considered by Eugene Charles Catalan (1814--1894), giving rise to the eponymous Catalan numbers, although Segneur, Euler, and Fuss had encountered the same sequence earlier in connection with the triangulation of convex polygons with non-crossing chords. There is a nice bijection between the two problem, so they are essentially the same, but bracketing is clearly of greater interest in informatics and theoretical computer science. For more on Catalan, please see http://www-history.mcs.st-and.ac.uk/~history/Mathematicians/Catalan.html; and for very much more on the Catalan numbers, please see Chap. 6 at http://www-math.mit.edu/~rstan/ec. If now, the symbols are the binary digits 0 and 1, then for each of the sixteen truth tables, and for each bracketing, we have an evaluation for strings of n symbols yielding 0 or 1. So, for each truth table, and for each test string, how many outcomes are there of each type ranging over all bracketings of the string? It seems that this type of problem was first considered by a group of research students in Denmark, but the asymptotics of a particular case is discussed as Examples 11.3 (pp. 312--313) and 11.31 (pp. 351--352) in the on-line text, ``Foundations of Combinatorics with Applications'', by E.A. Bender and S.G. Williamson, avialable at http://www.math.ucsd.edu/~ebender/CombText/. In fact, for the test strings consisting of 0s, the answer can be expressed exactly in all cases in terms of the ballot numbers.

Abstract: Analytic information theory aims at studying problems of information theory using analytic techniques of computer science and combinatorics. Following Hadamard's precept, we tackle these problems by complex analysis methods such as generating functions, Mellin transform, Fourier series, saddle point method, analytic poissonization and depoissonization, and singularity analysis. This approach lies at the crossroad of computer science and information theory. In this talk, we concentrate on one facet of information theory (i.e., source coding better known as data compression), namely the redundancy rate problem. The redundancy rate problem for a class of sources is the determination of how far the actual code length exceeds the optimal (ideal) code length. In a minimax scenario one finds the maximal redundancy over all sources within a certain class while in the average scenario one computes the average redundancy over all possible sources. The redundancy rate problem is typical of a situation where second-order asymptotics play a crucial role (since the leading term of the optimal code length is known to be the entropy of the source). This problem is an ideal candidate for ``analytic information theory''. We survey our recent results on the redundancy rate problem obtained by analytic methods. In particular, we present our findings for the redundancy of Shannon codes, Huffman codes, minimax redundancy for memoryless sources, Markov sources, and renewal processes. In the second part of the talk, we discuss the limitations of classical Shannon information theory, and argue that there is need for post-Shannon information theory.

Abstract: Phylogenies (phylogenetic trees) are an important tool for representing the evolutionary history of a set of species under the assumption that each species inherits its genetic material "vertically" from one ancestor. However, the non-vertical acquisition of genetic material through reticulation events, such as lateral gene transfer or hybridization, play an important role in the ability of species to rapidly adapt to new environments. As a result of these processes, the evolutionary stories told by phylogenies obtained by analyzing different genes of a set of species may be quite different, and a number of distance measures between pairs of phylogeies have been defined that help to identify reticulation events in the history of a set of species.

While biologically meaningful, these distance measures are NP-hard to compute. In this talk, we present new fixed-parameter algorithms for computing these distance measures based on the closely related notion of maximum agreement forests of pairs of phylogenies. In addition to the new theoretical results we have obtained, we also present an experimental evaluation of our algorithms on real and synthetic phylogenetic trees. Our experiments show that our algorithms outperform the best previous methods for computing these distances by over 3 orders of magnitude, allowing the analysis of phylogenies on much larger sets of species, as well as of pairs of more dissimilar phylogenies.

Joint work with Chris Whidden and Robert Beiko (Dalhousie University)

Abstract: We study two types of iterative 0/1-vertex-labeling processes on graphs where in each round every vertex
--- either never changes its label from 1 to 0, and changes its label from 0 to 1 if sufficiently many neighbours have label 1,
--- or changes its label if sufficiently many neighbours have a different label.
In both scenarios the number of neighbours required for a change depends on individual threshold values of the vertices. Such processes model spread of rumour or of disease, fault propagation, and consensus issues and have been studied under names such as iterative polling processes, irreversible threshold processes, and local majority processes, as well as in a large variety of contexts in distributed computing. Our contributions concern computational aspects related to the sets with minimum cardinality of vertices with initial label 1 such that during the process all vertices eventually change their label to 1 and remain with 1 as label. Such sets are known as dynamic monopolies or catastrophic fault patterns. We establish hardness results for the general case and describe efficient algorithms for restricted instances.

Authors: M.C. Dourado, L. Draque Penso, D. Rautenbach, and J.L. Szwarcfiter.

Abstract: Ein Pattern ist ein Wort aus Variablen und Terminalsymbolen. Die von einem Pattern p erzeugte Patternsprache ist die Menge aller Terminalwörter, die durch eine uniforme Ersetzung der Variablen in p durch Terminalwörter erzeugt werden können. So beschreibt das Pattern p = ax y ax (wobei x und y Variablen sind und a ein Terminal ist) die Menge aller Wörter, die ein Wort der Form ax sowohl als Präfix, als auch als Suffix haben. Wegen ihrer einfachen Definition besitzen Patternsprachen eine Vielzahl von Verbindungen zu verschiedenen anderen Gebieten der theoretischen Informatik und Mathematik, unter anderem zur Wortkombinatorik, Logik und der Theorie freier Halbgruppen. Andererseits führen viele der üblichen sprachtheoretischen Fragestellungen bei Patternsprachen zu kombinatorischen Problemen von überraschender Schwierigkeit. Im Vortrag werden zuerst einige dieser Verbindungen vorgestellt. Der Hauptteil des Vortrags widmet sich verschiedenen Aspekten des Inklusionsproblems von Patternsprachen und zeigt unter anderem einen (wahrscheinlich unpraktikablen) Ansatz, mittels dieses Problems einen Teil der Collatz-Vermutung zu beweisen oder zu widerlegen.

Abstract: Any imaging system, irrespective of its design, can be decomposed into two elements, its optics, which direct and focus light, and its sensing area, or retina, where incoming light energy is measured. Since light travels along straight lines in homogeneous media, it is geometrically convenient and often physically reasonable to model the behavior of a camera as a "bag of lines".

Essentially two classes of "bags of lines" representing imaging systems have been studied in the past -- linear sections of the Grassmanniann manifold and sets of lines of the form {x \vee Ax | x \in P^3(R)\} where A is some linear map. In this talk, I will show that these two formulations capture in fact the same sets of lines, and that they lead to simple formulas for direct/inverse projection and multi-view geometry.

This is a joint work with Guillaume Batog and Jean Ponce.