|
|
|
|
|
| Preliminary Schedule |
| 14:00 - 22:00 | Registration |
| 9:00 | Opening of MFCS 2000 |
| 9:30 | Jan van Leeuwen, Jiri Wiedermann: On Algorithms and Interaction (Invited Lecture) | |
| 10:30 | Break |
| 11:00 - 11:25 | David Peleg: Informative Labeling Schemes for Graphs | |
| 11:30 - 11:55 | Olivier Ly: Automatic Graphs and Graph D0L-Systems | |
| 12:00 - 12:25 | Therese Biedl, Brona Brejova, Tomas Vinar: Simplifying Flow Networks | |
| 12:30 | Lunch |
| 11:00 - 11:25 | Olivier Carton, Wolfgang Thomas: The Monadic Theory of Morphic Infinite Words and Generalizations | |
| 11:30 - 11:55 | Arturo Carpi, Aldo de Luca: Periodic-like Words | |
| 12:00 - 12:25 | Clelia De Felice: Factorizing Codes and Schutzenberger Conjectures | |
| 12:30 | Lunch |
| 14:00 | Silvano
Dal Zilio, Andrew D. Gordon: Region Analysis and a $\pi$-Calculus with Groups (Invited Lecture) | |
| 15:00 | Break |
| 15:30 - 15:55 | Orna Kupferman, Moshe Y. Vardi: $\mu$-Calculus Synthesis | |
| 16:00 - 16:25 | Leonor Prensa Nieto, Javier
Esparza: Verifying Single and Multi-mutator Garbage Collectors with Owicki-Gries in Isabelle/HOL | |
| 16:30 - 16:55 | Frank
S. de Boer, Marcello M. Bonsangue: A Compositional Model for Confluent Dynamic Data-Flow Networks | |
| 16:55 | End of Session |
| 15:30 - 15:55 | Todd Ebert, Heribert
Vollmer: On the Autoreducibility of Random Sequences | |
| 16:00 - 16:25 | Klaus Ambos-Spies: Measure Theoretic Completeness Notions for the Exponential Time Classes | |
| 16:30 - 16:55 | Gregory
Lafitte, Jacques Mazoyer: The Infinite Versions of LogSpace != P Are Consistent with the Axioms of Set Theory | |
| 16:55 | End of Session | |
| 19:00 | Welcome Party |
| 9:00 | Phokion Kolaitis, Moshe Y. Vardi: 0-1 Laws for Fragments of Existential Second-Order Logic: A Survey (Invited Lecture) | |
| 10:00 | Break |
| 10:30 - 10:55 | Giovanni Pighizzini: Unary Pushdown Automata and Auxiliary Space Lower Bounds | |
| 11:00 - 11:25 | Markus Holzer, Pierre McKenzie: Alternating and Empty Alternating Auxiliary Stack Automata | |
| 11:30 - 11:55 | Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan,
Richard Kemmerer: Counter Machines: Decidable Properties and Applications to Verification Problems | |
| 12:00 | Lunch |
| 10:30 - 10:55 | Thomas Schwentick: On Diving in Trees | |
| 11:00 - 11:25 | Angelo Montanari, Alberto Policriti, Matteo
Slanina: Derivability in Locally Quantified Modal Logics via Translation in Set Theory | |
| 11:30 - 11:55 | Alexander Rabinovich, Shahar Maoz: Why so Many Temporal Logics Climb up the Trees? | |
| 12:00 | Lunch |
| 14:00 | Shmuel Zaks: On the Use of Duality and Geometry in Layouts for ATM Networks (Invited Lecture) | |
| 15:00 | Break |
| 15:30 - 15:55 | Francesc
Comellas, Margarida Mitjana, Lata Narayanan, Jaroslav Opatrny: Optical Routing of Uniform Instances in Tori | |
| 16:00 - 16:25 | D.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:55 | Stefan Dobrev: Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks | |
| 16:55 | End of Session |
| 15:30 - 15:55 | Werner Kuich: Formal Series over Algebras | |
| 16:00 - 16:25 | Sabrina Mantaci, Vincent D. Blondel, Jean Mairesse: Bilinear Functions and Trees over the (max,+) Semiring | |
| 16:30 - 16:55 | Zoltan
Esik: Iteration Theories of Boolean Functions | |
| 16:55 | End of Session |
| 9:00 | Camil Demetrescu, Giuseppe F. Italiano: What Do We Learn from Experimental Algorithmics? (Invited Lecture) | |
| 10:00 | Break |
| 10:30 - 10:55 | Klaus Jansen, Lorant Porkolab: Preemptive Scheduling on Dedicated Processors: Applications of Fractional Graph Coloring | |
| 11:00 - 11:25 | Tanguy Urvoy: Regularity of Congruential Graphs | |
| 11:30 - 11:55 | Rostislav Caha, Petr Gregor: Embedding Fibonacci Cubes into Hypercubes with $\Omega (2^{cn})$ Faulty Nodes | |
| 12:00 | Lunch |
| 10:30 - 10:55 | Samson Abramsky, Marina Lenisa: Axiomatizing Fully Complete Models for ML Polymorphic Types | |
| 11:00 - 11:25 | Miki Tanaka: Abstract Syntax and Variable Binding for Linear Binders | |
| 11:30 - 11:55 | M. Dezani-Ciancaglini, F. Honsell,
Y. Motohama: Compositional Characterizations of $\lambda$-terms using Intersection Types | |
| 12:00 | Lunch | |
| 13:30 | Excursion |
| 9:00 | James H. Davenport: Abstract Data Types in Computer Algebra (Invited Lecture) | |
| 10:00 | Break |
| 10:30 - 10:55 | Daniel Kral: Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and Their Generalization | |
| 11:00 - 11:25 | Beate Bollig: Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication | |
| 11:30 - 11:55 | Petr Savicky, Detlef Sieling: A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism | |
| 12:00 | Lunch |
| 10:30 - 10:55 | David Mix Barrington, Pierre McKenzie, Cris Moore, Pascal
Tesson, Denis Therien: Equation Satisfiability and Program Satisfiability for Finite Monoids | |
| 11:00 - 11:25 | Steffen Reith, Heribert Vollmer: Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems | |
| 11:30 - 11:55 | Ondrej Klima, Jiri Srba: Matching Modulo Associativity and Idempotency is NP-complete | |
| 12:00 | Lunch |
| 14:00 | Radu Grosu: And/Or Hierarchies and Round Abstraction (Invited Lecture) | |
| 15:00 | Break |
| 15:30 - 15:55 | Arnaud Durand, Miki Hermann, Phokion G. Kolaitis: Subtractive Reductions and Complete Problems for Counting Complexity Classes | |
| 16:00 - 16:25 | Sven Kosub: On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems | |
| 16:30 - 16:55 | Lane
A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung: Reducing the Number of Solutions of NP Functions | |
| 16:55 | End of Session |
| 15:30 - 15:55 | Vadim V. Lozin: On a Generalization of Bi-complement Reducible Graphs | |
| 16:00 - 16:25 | Therese C. Biedl, Eowyn Cenek, Timothy
M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-Wei
Wang: Balanced $k$-Colorings | |
| 16:30 - 16:55 | Lali Barriere and Josep Fabrega: Edge-Bisection of Chordal Rings | |
| 16:55 | End of Session |
| 9:00 | Edith Hemaspaandra, Lane A. Hemaspaandra: Computational Politics: Electoral Systems (Invited Lecture) | |
| 10:00 | Break |
| 10:30 - 10:55 | Hiroaki Yamamoto: An Automata-Based Recognition Algorithm for Semi-extended Regular Expressions | |
| 11:00 - 11:25 | Klaus Wich: Sublinear Ambiguity | |
| 11:30 - 11:55 | Jean Berstel, Luc Boasson: XML Grammars | |
| 12:00 | Lunch |
| 10:30 - 10:55 | Ugo Montanari, Marco Pistore: $\pi$-Calculus, Structured Coalgebras and Minimal HD-Automata | |
| 11:00 - 11:25 | Philippa Gardner, Lucian Wischik: Explicit Fusions | |
| 11:30 - 11:55 | Jaco van de
Pol, Hans Zantema: Binary Decision Diagrams by Shared Rewriting | |
| 12:00 | Lunch |
| 14:00 - 14:25 | Jesper G. Henriksen, Madhavan
Mukund, K. Narayan Kumar, P.S. Thiagarajan: Regular Collections of Message Sequence Charts | |
| 14:30 - 14:55 | Thomas Buchholz,
Andreas Klein, Martin Kutrib: Iterative Arrays with Small Time Bounds | |
| 15:00 | Break | |
| 15:30 - 15:55 | Holger
Petersen: Separation Results for Rebound Automata | |
| 16:00 - 16:25 | Kazuo Iwama, Akihiro Matsuura, Mike Paterson: A Family of NFA's Which Need $2^n - \alpha$ Deterministic States | |
| 16:30 - 16:55 | Farid
Ablayev, Aida Gainutdinova: On the Lower Bounds for One-Way Quantum Automata | |
| 16:55 | End of Session |
| 14:00 - 14:25 | A. Finkel, G. Sutre: An algorithm constructing the semilinear post* for 2-dim Reset/Transfer VASS | |
| 14:30 - 14:55 | Jan Friso Groote, Jaco van de Pol: State Space Reduction Using Partial $\tau$-Confluence | |
| 15:00 | Break | |
| 15:30 - 15:55 | Ruggero
Lanotte, Andrea Maggiolo-Schettini: Timed Automata with Monotonic Activities | |
| 16:00 - 16:25 | P. Bouyer,
C. Dufourd, E. Fleury, A. Petit: Expressiveness of Updatable Timed Automata | |
| 16:25 | End of Session | |
| 18:30 | Conference Dinner |