MEMICS 2005 1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science October 14 - 17
Basic info
Invited Talks

Invited Talks

Probabilistic Omega-Automata.
by Christel Baier
Institute of Computer Science, Rheinische Friedrich-Wilhelms-Universität, Bonn

Probabilistic finite automata as acceptors for languages over finite words have been studied by many researchers. In this talk, we discuss probabilistic automata as acceptors for languages over infinite words. The idea is to resolve the choices in a nondeterministic omega-automaton by probabilities and to require positive probabilities for the accepting runs. Surprisingly, probabilistic Büchi automata are more expressive than non-deterministic omega-automata. However, a certain subclass of probabilistic Büchi automata can be identified that has exactly the power of omega-regular languages.

The talk will introduce the formal notion of probabilistic automata with Büchi and other acceptance conditions, discuss their expressiveness and efficiency and some basic properties.

Regular Symbolic Analysis of Dynamic Networks of Pushdown Systems.
by Ahmed Bouajjani
Laboratoire d'Informatique Algorithmique, Fondements et Applications, Paris 7 University, Paris

We introduce abstract models for multithreaded programs based on dynamic networks of pushdown systems. We address the problem of symbolic reachability analysis for these models. More precisely, we consider the problem of computing effective representations of their reachability sets using (finite-state) automata-based techniques. We show that, while forward reachability sets are not regular in general (but context-free), backward reachability sets starting from regular sets of configurations are always regular. We provide algorithms for computing backward reachability sets using word/tree automata, and show how these algorithms can be applied for flow analysis of multithreaded programs. This is a joint work with Markus Mueller-Olm (Univ. of Dortmund) and Tayssir Touili (LIAFA, CNRS)

Production Quality Grid Middleware - Challenges and Techniques.
by Erwin Laure
CERN, European Organization for Nuclear Research, Geneva

The EU-funded EGEE (Enabling Grids for E-SciencE - has the aim to deliver a reliable and dependable world-wide production quality Grid infrastructure for advanced e-Science applications like High Energy Physics, Biomedical applications, Earth sciences etc. With an infrastructure spanning more than 150 sites in over 30 countries EGEE currently operates one of largest Grid infrastructures in the world.

A production quality Grid infrastructure requires advanced middleware that builds the backbone of the infrastructure. In this talk we will discuss some of the main challenges we meet in the development of Grid middleware and how these are being addressed in the EGEE middleware stack, called gLite, as well as in some related projects. The focus will be on Workload and Data management issues, discussing gLite's strategies for providing production quality middleware and pointing out future research directions.

Grammatical Generation of Languages under Various Context Conditions.
by Alexander Meduna
Faculty of Information Technology, Brno University of Technology, Brno

The talk summarizes the author’s recent results about grammars with context conditions. Based upon the types of context conditions, it classifies them into grammars with context conditions placed on the domains of grammatical derivations, the use of grammatical productions, and the neighborhood of the rewritten symbols. The main attention is paid to the results concerning grammatical generative power, important properties, simplification, reduction, and applications. Most of the applications are related to microbiology

Design and Analysis of Intuitive Algorithms.
by Peter Rossmanith
Computer Science Department, RWTH Aachen University, Aachen