Annual Doctoral Workshop on Mathematical and
Engineering Methods in Computer Science
organized jointly by the Masaryk University
and the Brno University of Technology, Czechia
January 6, 2010
Have a look at MEMICS 2009 photos.
December 23, 2009
Selected MEMICS'09 papers have just appeared in a distinguished workshop postproceedings published by Dagstuhl Research Online Publication Server DROPS.
November 13—15, 2009    Prestige Hotel    Znojmo    Czechia

Invited Speakers
The programme will include invited talks by distinguished researchers, namely M. Bojanczyk, R. Freivalds, G. Raidl, and P. Habermehl. Titles and abstracts of the talks are given below.

Automata for XML
Mikolaj Bojanczyk (University of Warsaw, Poland)
Since XML documents look like trees, people have used tree automata to analyze them. However, a tree automaton ignores some of the important additional structure in an XML document, such as attribute values. Recently, there has been a burst of research on automata models that capture this additional structure. There are a lot of questions that are still not well understood. What is the correct automaton model for XML documents? What happens to typical results on automata (determinization, complementation)? What is decidable?

Randomization and other ways to overcome determinism in algorithms
Rūsiņš Freivalds (University of Latvia)
Probabilistic algorithms are used widely. For instance, in spite of discovery of a polynomial time deterministic algorithm for primality testing of large integers, much simpler and more efficient probabilistic algorithm is still widely used in practice.
Quantum algorithms sometimes are more efficient but practically usable quantum computers are still not available, and nowadays the only practical application of quantum computation is quantum cryptography. Recently spectacular quantum algorithms have been constructed. Practically all of them use so-called quantum walk being a modification of random walk well-known during many decades.
The talk is devoted to discussion of all kinds of "indeterministic" types of algorithms, what they have in common and at what circumstances they can be used.

Angluin-style learning of non-deterministic finite-state automata
Peter Habermehl (University Paris 7, France)
We introduce NL*, a learning algorithm for inferring non-deterministic finite-state automata using membership and equivalence queries. More specifically, residual finite-state automata (RFSA) are learned similar as in Angluin's popular L* algorithm, which however learns deterministic finite-state automata (DFA). As RFSA can be exponentially more succinct than DFA, RFSA are the preferable choice for many learning applications. The implementation of our algorithms is applied to a collection of examples and confirms the expected advantage of NL* over L*. This talk is based on joint work with B. Bollig (LSV, ENS Cachan), C. Kern (RWTH Aachen) and M. Leucker (TU Munich).

Combining Metaheuristics with Mathematical Programming Techniques for Solving Difficult Network Design Problems
Günther Raidl (Vienna University of Technology, Austria)
While mathematical programming techniques are powerful approaches for solving hard combinatorial optimization problems appearing in the area of network design, their application is usually limited to instances of small or moderate size due to their exhaustive running time and memory requirements. In practice, one usually has to turn to heuristic and metaheuristic approaches for approximately solving larger instances. Over the last years so-called hybrid optimization techniques have become more popular. They combine concepts of different optimization strategies and try to exploit their individual benefits. Various examples illustrate that often such hybrids are indeed able to outperform their "pure" counterparts. This talk gives an overview on successful hybridization techniques with a particular focus on combinations of metaheuristics and integer linear programming (ILP) methods. We will then consider a few case studies, including approaches where very large neighborhoods are searched by means of ILP methods, a Lagrangian decomposition approach collaborates with variable neighborhood search, and a column generation algorithm is sped up by means of metaheuristics. These examples document the usefulness and large potential such combinations have.

Copyright © FI MU
Copyright © FIT VUT
Brno, 2005–2009
Photos and Design