MFCS
MFCS 2000
25th International Symposium on
Mathematical Foundations of Computer Science
August 28 - September 1, 2000
Bratislava, Slovak Republic, Europe

Preliminary Schedule

SUNDAY, AUGUST 27

 14:00 - 22:00Registration


MONDAY, AUGUST 28

   9:00Opening of MFCS 2000

Session 1

   9:30Jan van Leeuwen, Jiri Wiedermann:
On Algorithms and Interaction
(Invited Lecture)
 10:30Break

Session 1A

 11:00 - 11:25David Peleg:
Informative Labeling Schemes for Graphs
 11:30 - 11:55Olivier Ly:
Automatic Graphs and Graph D0L-Systems
 12:00 - 12:25Therese Biedl, Brona Brejova, Tomas Vinar:
Simplifying Flow Networks
 12:30Lunch

Session 1B

 11:00 - 11:25Olivier Carton, Wolfgang Thomas:
The Monadic Theory of Morphic Infinite Words and Generalizations
 11:30 - 11:55Arturo Carpi, Aldo de Luca:
Periodic-like Words
 12:00 - 12:25Clelia De Felice:
Factorizing Codes and Schutzenberger Conjectures
 12:30Lunch

Session 2

 14:00Silvano Dal Zilio, Andrew D. Gordon:
Region Analysis and a $\pi$-Calculus with Groups
(Invited Lecture)
 15:00Break

Session 2A

 15:30 - 15:55Orna Kupferman, Moshe Y. Vardi:
$\mu$-Calculus Synthesis
 16:00 - 16:25Leonor Prensa Nieto, Javier Esparza:
Verifying Single and Multi-mutator Garbage Collectors with Owicki-Gries in Isabelle/HOL
 16:30 - 16:55Frank S. de Boer, Marcello M. Bonsangue:
A Compositional Model for Confluent Dynamic Data-Flow Networks
 16:55End of Session

Session 2B

 15:30 - 15:55Todd Ebert, Heribert Vollmer:
On the Autoreducibility of Random Sequences
 16:00 - 16:25Klaus Ambos-Spies:
Measure Theoretic Completeness Notions for the Exponential Time Classes
 16:30 - 16:55Gregory Lafitte, Jacques Mazoyer:
The Infinite Versions of LogSpace != P Are Consistent with the Axioms of Set Theory
 16:55End of Session
 19:00Welcome Party


TUESDAY, AUGUST 29

Session 1

 9:00Phokion Kolaitis, Moshe Y. Vardi:
0-1 Laws for Fragments of Existential Second-Order Logic: A Survey
(Invited Lecture)
 10:00Break

Session 1A

 10:30 - 10:55Giovanni Pighizzini:
Unary Pushdown Automata and Auxiliary Space Lower Bounds
 11:00 - 11:25Markus Holzer, Pierre McKenzie:
Alternating and Empty Alternating Auxiliary Stack Automata
 11:30 - 11:55Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan, Richard Kemmerer:
Counter Machines: Decidable Properties and Applications to Verification Problems
 12:00Lunch

Session 1B

 10:30 - 10:55Thomas Schwentick:
On Diving in Trees
 11:00 - 11:25Angelo Montanari, Alberto Policriti, Matteo Slanina:
Derivability in Locally Quantified Modal Logics via Translation in Set Theory
 11:30 - 11:55Alexander Rabinovich, Shahar Maoz:
Why so Many Temporal Logics Climb up the Trees?
 12:00Lunch

Session 2

 14:00Shmuel Zaks:
On the Use of Duality and Geometry in Layouts for ATM Networks
(Invited Lecture)
 15:00Break

Session 2A

 15:30 - 15:55Francesc Comellas, Margarida Mitjana, Lata Narayanan, Jaroslav Opatrny:
Optical Routing of Uniform Instances in Tori
 16:00 - 16:25D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou, P.G. Spirakis:
NP-completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs
 16:30 - 16:55Stefan Dobrev:
Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks
 16:55End of Session

Session 2B

 15:30 - 15:55Werner Kuich:
Formal Series over Algebras
 16:00 - 16:25Sabrina Mantaci, Vincent D. Blondel, Jean Mairesse:
Bilinear Functions and Trees over the (max,+) Semiring
 16:30 - 16:55Zoltan Esik:
Iteration Theories of Boolean Functions
 16:55End of Session


WEDNESDAY, AUGUST 30

Session 1

 9:00Camil Demetrescu, Giuseppe F. Italiano:
What Do We Learn from Experimental Algorithmics?
(Invited Lecture)
 10:00Break

Session 1A

 10:30 - 10:55Klaus Jansen, Lorant Porkolab:
Preemptive Scheduling on Dedicated Processors: Applications of Fractional Graph Coloring
 11:00 - 11:25Tanguy Urvoy:
Regularity of Congruential Graphs
 11:30 - 11:55Rostislav Caha, Petr Gregor:
Embedding Fibonacci Cubes into Hypercubes with $\Omega (2^{cn})$ Faulty Nodes
 12:00Lunch

Session 1B

 10:30 - 10:55Samson Abramsky, Marina Lenisa:
Axiomatizing Fully Complete Models for ML Polymorphic Types
 11:00 - 11:25Miki Tanaka:
Abstract Syntax and Variable Binding for Linear Binders
 11:30 - 11:55M. Dezani-Ciancaglini, F. Honsell, Y. Motohama:
Compositional Characterizations of $\lambda$-terms using Intersection Types
 12:00Lunch
 13:30Excursion


THURSDAY, AUGUST 31

Session 1

 9:00James H. Davenport:
Abstract Data Types in Computer Algebra
(Invited Lecture)
 10:00Break

Session 1A

 10:30 - 10:55Daniel Kral:
Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and Their Generalization
 11:00 - 11:25Beate Bollig:
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
 11:30 - 11:55Petr Savicky, Detlef Sieling:
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
 12:00Lunch

Session 1B

 10:30 - 10:55David Mix Barrington, Pierre McKenzie, Cris Moore, Pascal Tesson, Denis Therien:
Equation Satisfiability and Program Satisfiability for Finite Monoids
 11:00 - 11:25Steffen Reith, Heribert Vollmer:
Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems
 11:30 - 11:55Ondrej Klima, Jiri Srba:
Matching Modulo Associativity and Idempotency is NP-complete
 12:00Lunch

Session 2

 14:00Radu Grosu:
And/Or Hierarchies and Round Abstraction
(Invited Lecture)
 15:00Break

Session 2A

 15:30 - 15:55Arnaud Durand, Miki Hermann, Phokion G. Kolaitis:
Subtractive Reductions and Complete Problems for Counting Complexity Classes
 16:00 - 16:25Sven Kosub:
On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems
 16:30 - 16:55Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung:
Reducing the Number of Solutions of NP Functions
 16:55End of Session

Session 2B

 15:30 - 15:55Vadim V. Lozin:
On a Generalization of Bi-complement Reducible Graphs
 16:00 - 16:25Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-Wei Wang:
Balanced $k$-Colorings
 16:30 - 16:55Lali Barriere and Josep Fabrega:
Edge-Bisection of Chordal Rings
 16:55End of Session


FRIDAY, SEPTEMBER 1

Session 1

 9:00Edith Hemaspaandra, Lane A. Hemaspaandra:
Computational Politics: Electoral Systems
(Invited Lecture)
 10:00Break

Session 1A

 10:30 - 10:55Hiroaki Yamamoto:
An Automata-Based Recognition Algorithm for Semi-extended Regular Expressions
 11:00 - 11:25Klaus Wich:
Sublinear Ambiguity
 11:30 - 11:55Jean Berstel, Luc Boasson:
XML Grammars
 12:00Lunch

Session 1A

 10:30 - 10:55Ugo Montanari, Marco Pistore:
$\pi$-Calculus, Structured Coalgebras and Minimal HD-Automata
 11:00 - 11:25Philippa Gardner, Lucian Wischik:
Explicit Fusions
 11:30 - 11:55Jaco van de Pol, Hans Zantema:
Binary Decision Diagrams by Shared Rewriting
 12:00Lunch

Session 2A

 14:00 - 14:25Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P.S. Thiagarajan:
Regular Collections of Message Sequence Charts
 14:30 - 14:55Thomas Buchholz, Andreas Klein, Martin Kutrib:
Iterative Arrays with Small Time Bounds
 15:00Break
 15:30 - 15:55Holger Petersen:
Separation Results for Rebound Automata
 16:00 - 16:25Kazuo Iwama, Akihiro Matsuura, Mike Paterson:
A Family of NFA's Which Need $2^n - \alpha$ Deterministic States
 16:30 - 16:55Farid Ablayev, Aida Gainutdinova:
On the Lower Bounds for One-Way Quantum Automata
 16:55End of Session

Session 2B

 14:00 - 14:25A. Finkel, G. Sutre:
An algorithm constructing the semilinear post* for 2-dim Reset/Transfer VASS
 14:30 - 14:55Jan Friso Groote, Jaco van de Pol:
State Space Reduction Using Partial $\tau$-Confluence
 15:00Break
 15:30 - 15:55Ruggero Lanotte, Andrea Maggiolo-Schettini:
Timed Automata with Monotonic Activities
 16:00 - 16:25P. Bouyer, C. Dufourd, E. Fleury, A. Petit:
Expressiveness of Updatable Timed Automata
 16:25End of Session
 18:30Conference Dinner


Back to MFCS 2000 Home Page


Department of Computer Science, Faculty of Mathematics and Physics, Comenius University, Bratislava
All rights reserved. © 2000
Last modified: June 26, 2000