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.