MFCS
MFCS 2003
28th International Symposium on
Mathematical Foundations of Computer Science
August 25 - 29, 2003
Bratislava, Slovak Republic, Europe

Conference program

Sunday August 24, 2003

16:00 - 22:00 Registration

Monday August 25, 2003

8:45 Opening
9:00 - 10:00 Invited Talk
Ingo Wegener
Towards a Theory of Randomized Search Heuristics
 
10:00 - 10:25Coffee Break
 
10:25 - 10:50A Faster FPT Algorithm for Finding Spanning Trees With
Many Leaves
Paul S. Bonsma, Tobias Brueggemann, and Gerhard J. Woeginger
10:50 - 11:15Scheduling and Trafic Allocation for Tasks with Bounded Splittability
Piotr Krysta, Peter Sanders, and Berthold Voecking
11:15 - 11:40Approximation Schemes for the Min-Max Starting Time Problem
Leah Epstein and Tamir Tassa
 
11:40 - 11:55Break
 
11:55 - 12:20Generic Algorithms for the Generation of Combinatorial Objects
Conrado Martinez and Xavier Molinero
12:20 - 12:45Starting with Nondeterminism: The Systematic Derivation of
Linear-Time Graph Layout Algorithms
Hans L. Bodlaender, Michael R. Fellows, and Dimitrios M. Thilikos
 
12:45 - 14:00Lunch
 
14:00 - 15:00Invited Talk
Roberto Gorrieri
Process Algebraic Frameworks for the Specification and Analysis
of Cryptographic Protocols (with Fabio Martinelli)
 
15:00 - 15:25Coffee Break
 
15:25 - 15:50Symbolic Analysis of Crypto-Protocols Based on Modular Exponentiation
Michele Boreale and Maria Grazia Buscemi
15:50 - 16:15The Minimal Graph Model of Lambda Calculus
Antonio Bucciarelli and Antonino Salibra
16:15 - 16:40The Approximate Well-founded Semantics for Logic Programs with Uncertainty
Yann Loyer, and Umberto Straccia
 
16:40 - 16:55Break
 
16:55 - 17:20LTL with Past and Two-Way Very-Weak Alternating Automata
Paul Gastin and Denis Oddoux
17:20 - 17:45Local LTL with Past Constants is Expressively Complete for
Mazurkiewicz Traces
Paul Gastin, Madhavan Mukund, and K. Narayan Kumar
17:45 - 18:10Relating Hierarchy of Temporal Properties to Model Checking
Ivana Cerna and Radek Pelanek
 
19:00 Welcome Dinner

Tuesday August 26, 2003

08:45 - 09:45Invited Talk
Burkhard Monien
Selfish Routing in Non-Cooperative Networks: A Survey
(with R. Feldmann, M. Gairing, T. Luecking, and M. Rode)
 
09:45 - 10:10Coffee Break
 
10:10 - 10:35Computing Average Value in Ad Hoc Networks
Miroslaw Kutylowski and Daniel Letkiewicz 
10:35 - 11:00Adversarial Models for Priority-Based Networks
C. Alvarez, M. Blesa, J. DĦaz, A. Fernandez, and M. Serna
11:00 - 11:25Two Dimensional Packing: The Power of Rotation
Leah Epstein
 
11:25 - 11:40Break
 
11:40 - 12:05A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs
(Extended Abstract)
Zhi-Zhong Chen and Mitsuharu Kouno
12:05 - 12:30Randomized Algorithms for Determining the Majority on Graphs
Gianluca De Marco and Andrzej Pelc
12:30 - 12:55Which is the Worst-Case Nash Equilibrium?
Thomas Luecking, Marios Mavronicolas, Burkhard Monien, Manuel
Rode, Paul Spirakis, and Imrich Vrto
 
12:55 - 14:00Lunch Break
 
14:00 - 15:00Invited Talk
Wolfgang Thomas
Constructing Infinite Graphs With a Decidable MSO-Theory
 
15:00 - 15:25Coffee Break
 
15:25 - 15:50On Matroid Properties Definable in the MSO Logic
Petr Hlineny
15:50 - 16:15A Unique Decomposition Theorem for Ordered Monoids with
Applications in Process Theory (Extended Abstract)
Bas Luttik
16:15 - 16:40Using Transitive-Closure Logic for Deciding Linear Properties
of Monoids
Christian Delhomme, Teodor Knapik, and D. Gnanaraj Thomas
 
16:40 - 16:55Break
 
16:55 - 17:20Probabilistic and Nondeterministic Unary Automata
Gregor Gramlich BEST STUDENT PAPER AWARD
17:20 - 17:45Characterizations of Catalytic Membrane Computing Systems
(Extended Abstract)
Oscar H. Ibarra, Zhe Dang, Omer Egecioglu, and Gaurav Saxena
17:45 - 18:10Unambiguous Automata on Bi-Infinite Words
Olivier Carton

Wednesday August 27, 2003

08:45 - 09:10Smoothed Analysis of Three Combinatorial Problems
Cyril Banderier, Rene Beier, and Kurt Mehlhorn
09:10 - 09:35Completeness in Differential Approximation Classes (Extended Abstract)
G. Ausiello, C. Bazgan, M. Demange, and V. Th. Paschos
09:35 - 10:00Faster Algorithms for k-Medians in Trees (Extended Abstract)
Robert Benkoczi, Binay Bhattacharya, Marek Chrobak,
Lawrence L. Larmore, and Wojciech Rytter
10:00 - 10:25Augmenting Local Edge-Connectivity between Vertices and Vertex
Subsets in Undirected Graphs
Toshimasa Ishii and Masayuki Hagiwara
 
10:25 - 10:50Coffee Break
 
10:50 - 11:15An Abduction-Based Method for Index Relaxation in Taxonomy-Based Sources
Carlo Meghini, Yannis Tzitzikas, and Nicolas Spyratos
11:15 - 11:40On the Complexity of Some Problems in Interval Arithmetic
K. Meer
11:40 - 12:05Ershov's Hierarchy of Real Numbers
Xizhong Zheng, Robert Rettinger, and Romain Gengler
 
12:05 - 13:15Lunch Break
 
13:30 - 18:00Conference trip

Thursday August 28, 2003

08:45 - 09:45Invited Talk
Giancarlo Mauri
On the Computational Complexity of Conservative Computing
(with Alberto Leporati)
 
09:45 - 10:10Coffee Break
 
10:10 - 10:35Lower Bounds for General Graph-Driven Read-Once Parity
Branching Programs
Henrik Brosenne, Matthias Homeister, and Stephan Waack
10:35 - 11:00Arithmetic Constant-Depth Circuit Complexity Classes
Hubie Chen
11:00 - 11:25On Converting CNF to DNF
Peter Bro Miltersen, Jaikumar Radhakrishnan, and Ingo Wegener
 
11:25 - 11:40Break
 
11:40 - 12:05On Optimal Merging Networks
Kazuyuki Amano and Akira Maruoka
12:05 - 12:30Symbolic Topological Sorting with OBDDs (Extended Abstract)
Philipp Woelfel
12:30 - 12:55Solving the Sabotage Game is PSPACE-Hard
Christof Loeding and Philipp Rohde
 
12:55 - 14:00Lunch Break
 
14:00 - 15:00Invited Talk
Harry Buhrmann
Distributed Quantum Computing (with Hein Roehrig)
 
15:00 - 15:25Coffee Break
 
15:25 - 15:50Quantum Testers for Hidden Group Properties
Katalin Friedl, Frederic Magniez, Miklos Santha, and Pranab Sen
15:50 - 16:15ACID-Unification is NEXPTIME-Decidable
Siva Anantharaman, Paliath Narendran, Michael Rusinowitch
16:15 - 16:40Periodicity and Transitivity for Cellular Automata in
Besicovitch Topologies
F. Blanchard, J. Cervelle, and E. Formenti
 
16:40 - 16:55Break
 
16:55 - 17:20Problems Which Cannot Be Reduced to Any Proper Subproblems
Ambos-Spies
17:20 - 17:45Error-Bounded Probabilistic Computations between MA and AM
Elmar Boehler, Christian Glayer, and Daniel Meister
17:45 - 18:10Inverse NP Problems
Hubie Chen

Friday August 29, 2003

08:45 - 09:45Invited Talk
Don Sannella
Semantic and Syntactic Approaches to Simulation Relations
(with Jo Hannay and Shin-ya Katsumata)
 
09:45 - 10:10Coffee Break
 
10:10 - 10:35On the Complexity of Some Equivalence Problems for Propositional Calculi
Steffen Reith
10:35 - 11:00On Probabilistic Quantified Satisfiability Games
Marcin Rychlik
11:00 - 11:25Generalized Satisfiability with Limited Occurrences per Variable:
a Study through Delta-Matroid Parity
Victor Dalmau and Daniel K. Ford
 
11:25 - 11:40Break
 
11:40 - 12:05Denotational Testing Semantics in Coinductive Form
Michele Boreale and Fabio Gadducci
12:05 - 12:30Quantified Mu-Calculus for Control Synthesis
Stephane Riedweg and Sophie Pinchinat
12:30 - 12:55A Polynomial-Time Algorithm for Deciding True Concurrency
Equivalences of Basic Parallel Processes
Slawomir Lasota
 
12:55 - 14:00Lunch Break
 
14:00 - 14:25Linear-Time Computation of Local Periods
Jean-Pierre Duval, Roman Kolpakov, Gregory Kucherov, Thierry
Lecroq, and Arnaud Lefebvre
14:25 - 14:50On Selection Functions that Do Not Preserve Normality
Wolfgang Merkle and Jan Reimann
14:50 - 15:15Inferring Strings from Graphs and Arrays
Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara,
and Masayuki Takeda
15:15 - 15:40Match-Bounded String Rewriting Systems
Alfons Geser, Dieter Hofbauer, and Johannes Waldmann
 
15:40 - 16:05Coffee Break
 
16:05 - 16:30A Basis of Tiling Motifs for Generating Repeated Patterns and its
Complexity for Higher Quorum
N. Pisanti, M. Crochemore, R. Grossi, and M.-F. Sagot
16:30 - 16:55On the Length of the Minimum Solution of Word Equations
in One Variable
Kensuke Baba, Satoshi Tsuruta, Ayumi Shinohara,
and Masayuki Takeda
16:55 - 17:20A Completeness Property of Wilke's Tree Algebras
Saeed Salehi
 
18:00 Busses depart for CONFERENCE DINNER