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

Abstracts of Contributed Papers

The abstracts correspond to those versions of papers that were submitted originally. Papers are ordered by the time of their submission.


Formal Series over Algebras
by Werner Kuich
[View abstract]
Preemptive Scheduling with Dedicated Processors: Applications of Fractional Graph Coloring
by Klaus Jansen, Lorant Porkolab
[View abstract]
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
by Beate Bollig
[View abstract]
On a Generalization of Bi-complement Reducible Graphs
by Vadim V. Lozin
[View abstract]
Informative Labeling Schemes for Graphs
by David Peleg
[View abstract]
Simplifying Flow Networks
by Therese Biedl, Brona Brejova, Tomas Vinar
[View abstract]
Iteration Theories of Boolean Functions
by Z. Esik
[View abstract]
Binary Decision Diagrams by Shared Rewriting
by Jaco van de Pol and Hans Zantema
[View abstract]
Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems
by Steffen Reith and Heribert Vollmer
[View abstract]
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
by Petr Savicky, Detlef Sieling
[View abstract]
Embedding Fibonacci Cubes into Hypercubes with $\Omega(2^{cn})$ Faulty Nodes
by Rostislav Caha and Petr Gregor
[View abstract]
Optical Routing of Uniform Instances in Tori
by Francesc Comellas, Margarida Mitjana, Lata Narayanan, and Jaroslav Opatrny
[View abstract]
Periodic-like Words
by Arturo Carpi, Aldo de Luca
[View abstract]
On the Lower Bounds for One-way Quantum Automata
by Farid Ablayev and Aida Gainutdinova
[View abstract]
AI-matching is NP-complete
by Ondrej Klima, Jiri Srba
[View abstract]
Separation Results for Rebound Automata
by Holger Petersen
[View abstract]
Unary Pushdown Automata and Auxiliary Space Lower Bounds
by Giovanni Pighizzini
[View abstract]
$\pi$-Calculus, Structured Coalgebras and Minimal HD-Automata
by Ugo Montanari and Marco Pistore
[View abstract]
Equation Satisfiability and Program Satisfiability for Finite Monoids
by David Mix Barrington, Pierre McKenzie, Cris Moore, Pascal Tesson and Denis Therien
[View abstract]
$\mu$-calculus Synthesis
by Orna Kupferman and Moshe Y. Vardi
[View abstract]
Counter Machines: Decidable Properties and Applications to Verification Problems
by Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan, and Richard Kemmerer
[View abstract]
An Automata-based Recognition Algorithm for Semi-extended Regular Expressions
by Hiroaki Yamamoto
[View abstract]
State Space Reduction using Partial $\tau$-Confluence
by Jan Friso Groote and Jaco van de Pol
[View abstract]
On Diving in Trees
by Thomas Schwentick
[View abstract]
The Monadic Theory of Morphic Infinite Words and Generalizations
by Olivier Carton, Wolfgang Thomas
[View abstract]
Factorizing Codes and Schutzenberger Conjectures
by Clelia De Felice
[View abstract]
Timed Automata with Monotonic Activities
by Ruggero Lanotte, Andrea Maggiolo Schettini
[View abstract]
Measure Theoretic Completeness Notions for the Exponential Time Classes
by Klaus Ambos-Spies
[View abstract]
Abstract Syntax and Variable Binding for Linear Binders
by Miki Tanaka
[View abstract]
Derivability in Locally Quantified Modal Logics via Translation in Set Theory
by Angelo Montanari, Alberto Policriti, Matteo Slanina
[View abstract]
Explicit Fusions
by Philippa Gardner and Lucian Wischik
[View abstract]
Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization
by Daniel Kral
[View abstract]
On the Autoreducibility of Random Sequences
by Todd Ebert and Heribert Vollmer
[View abstract]
On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems
by Sven Kosub
[View abstract]
Subtractive Reductions and Complete Problems for Counting Complexity Classes
by Arnaud Durand, Miki Hermann, Phokion G. Kolaitis
[View abstract]
Balanced $k$-Colorings
by T.C. Biedl, E. Cenek, T.M. Chan, E.D. Demaine, M.L. Demaine, R. Fleischer, Ming-Wei Wang
[View abstract]
Verifying Single and Multi-mutator Garbage Collectors with Owicki-Gries in Isabelle/HOL
by Leonor Prensa Nieto and Javier Esparza
[View abstract]
Hardness Results and Efficient Approximations for Radiocoloring in Planar Graphs
by D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou and P.G. Spirakis
[View abstract]
The Infinite Versions of LogSpace!=P Are Consistent with the Axioms of Set Theory
by Gregory Lafitte and Jacques Mazoyer
[View abstract]
Why so many Temporal Logics Climb Up the Trees?
by A. Rabinovich and S. Maoz
[View abstract]
A Compositional Model for Confluent Dynamic Data-flow Networks
by Frank S. de Boer and Marcello M. Bonsangue
[View abstract]
Reducing the Number of Solutions of NP Functions
by Lane Hemaspaandra, Mitsunori Ogihara, and Gerd Wechsung
[View abstract]
Regularity of Congruential Graphs
by Tanguy Urvoy
[View abstract]
An algorithm constructing the semilinear post* for 2-dim Reset/Transfer VASS
by A. Finkel, G. Sutre
[View abstract]
Axiomatizing Fully Complete Models for ML Polymorphic Types
by Samson Abramsky and Marina Lenisa
[View abstract]
Sublinear Ambiguity
by Klaus Wich
[View abstract]
Alternating and Empty Alternating Auxiliary Stack Automata
by Markus Holzer and Pierre McKenzie
[View abstract]
Automatic Graphs and Graph $D0L$-Systems
by Olivier Ly
[View abstract]
A Family of NFA's which Need $2^n-\alpha$ Deterministic States
by Kazuo Iwama, Akihiro Matsuura and Mike Paterson
[View abstract]
Compositional Characterizations of $\lambda$-terms Using Intersection Types
by M.Dezani-Ciancaglini, F.Honsell and Y.Motohama
[View abstract]
Iterative Arrays with Small Time Bounds
by Thomas Buchholz, Andreas Klein, Martin Kutrib
[View abstract]
Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks
by Stefan Dobrev
[View abstract]
Expressiveness of Updatable Timed Automata
by Patricia Bouyer, Catherine Dufourd, Emmanuel Fleury, Antoine Petit
[View abstract]
Edge-bisection of Chordal Rings
by Lali Barriere and J. Fabrega
[View abstract]
XML Grammars
by Jean Berstel, Luc Boasson
[View abstract]
Bilinear Functions and Trees over the $(\max,+)$ Semiring
by Sabrina Mantaci, Vincent D. Blondel, and Jean Mairesse
[View abstract]
Regular Collections of Message Sequence Charts
by Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P.S. Thiagarajan
[View abstract]

Back to MFCS 2000 Home Page


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