MFCS
MFCS 2003
28th International Symposium on
Mathematical Foundations of Computer Science
August 25 - 29, 2003
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.


On Matroid Properties Definable in the MSO Logic
by Petr Hlineny
[View abstract]
Two dimensional packing: the power of rotation
by Leah Epstein
[View abstract]
Approximation Schemes for the Min-Max Starting Time Problem
by Leah Epstein and Tamir Tassa
[View abstract]
A Linear Time Algorithm For 7-Coloring 1-Planar Graphs
by Zhi-Zhong Chen, Mitsuharu Kouno
[View abstract]
Scheduling and Traffic Allocation for Tasks with Bounded Splittability
by Piotr Krysta and Peter Sanders and Berthold Voecking
[View abstract]
Computing Average Value in ad hoc Networks
by Miroslaw Kutylwski and Daniel Letkiewicz
[View abstract]
Quantified mu-calculus for control synthesis
by Stephane Riedweg and Sophie Pinchinat
[View abstract]
On the complexity of some problems in interval arithmetic
by Klaus Meer
[View abstract]
Lower Bounds for General Graph-Driven Read-Once Parity Branching Programs
by Henrik Brosenne, Matthias Homeister and Stephan Waack
[View abstract]
Symbolic Topological Sorting with OBDDs
by Philipp Wolfel
[View abstract]
A completeness property of Wilkes tree algebras
by Saeed Salehi
[View abstract]
Augmenting Local Edge-Connectivity between Vertices and Vertex Subsets in Undirected Graphs
by Toshimasa Ishii and Masayuki Hagiwara
[View abstract]
On converting CNF to DNF
by Peter Bro Miltersen, Jaikumar Radhakrishnan and Ingo Wegener
[View abstract]
Completeness in differential approximation classes
by Giorgio Ausiello, Cristina Bazgan, Marc Demange and Vangelis Th. Paschos
[View abstract]
Linear-Time Computation of Local Periods
by Jean-Pierre Duval, Roman Kolpakov, Gregory Kucherov, Thierry Lecroq, Arnaud Lefebvre
[View abstract]
Solving the Sabotage Game is PSPACE-hard
by Christof Loding and Philipp Rohde
[View abstract]
Inverse NP Problems
by Hubie Chen
[View abstract]
Arithmetic Constant-Depth Circuit Complexity Classes
by Hubie Chen
[View abstract]
AC(U)ID-Unification is NEXPTIME-Decidable
by Siva Anantharaman, Paliath Narendran and Michael Rusinowitch
[View abstract]
The minimal graph model of lambda calculus
by Antonio Bucciarelli and Antonino Salibra
[View abstract]
Probabilistic and Nondeterministic Unary Automata
by Gregor Gramlich
[View abstract]
A polynomial-time algorithm for deciding true concurrency equivalences of Basic Parallel Processes
by Slawomir Lasota
[View abstract]
An Abduction-based Method for Index Relaxation in Taxonomy-based Sources
by Carlo Meghini, Yannis Tzitzikas and Nicolas Spyratos
[View abstract]
Periodicity and transitivity for cellular automata in Besicovitch topologies
by F. Blanchard, J. Cervelle and E. Formenti
[View abstract]
Using Transitive-closure Logic for Deciding Linear Properties of Monoids
by Christian Delhomme, Teodor Knapik and D. Gnanaraj Thomas
[View abstract]
The Approximate Well-founded Semantics for Logic Programs with Uncertainty
by Yann Loyer and Umberto Straccia
[View abstract]
Local LTL with past constants is expressively complete for Mazurkiewicz traces
by Paul Gastin and Madhavan Mukund and K. Narayan Kumar
[View abstract]
Inferring Strings from Graphs and Arrays
by Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda
[View abstract]
On selection functions that do not preserve normality
by Wolfgang Merkle and Jan Reimann
[View abstract]
LTL with past and two-way very-weak alternating automata
by Paul Gastin and Denis Oddoux
[View abstract]
A Unique Decomposition Theorem for Ordered Monoids with Applications in Process Theory
by Bas Luttik
[View abstract]
On the Length of the Minimum Solution of Word Equations in One Variable
by Kensuke Baba, Satoshi Tsuruta, Ayumi Shinohara, and Masayuki Takeda
[View abstract]
Smoothed Analysis of Three Combinatorial Problems
by Cyril Banderier, Kurt Mehlhorn and Rene Beier
[View abstract]
Error-Bounded Probabilistic Computations between MA and AM
by Elmar Boehler, Christian Glasser, and Daniel Meister
[View abstract]
Ershov's Hierarchy of Real Numbers
by Xizhong Zheng, Robert Rettinger and Romain Gengler
[View abstract]
On Probabilistic Quantified Satisfabilty Games
by Marcin Rychlik
[View abstract]
Match-Bounded String Rewriting Systems
by Alfons Geser, Dieter Hofbauer and Johannes Waldmann
[View abstract]
On the Complexity of some Equivalence Problems for Propositional Calculi
by Steffen Reith
[View abstract]
A faster FPT algorithm for finding spanning trees with many leaves
by P.S. Bonsma and T. Brueggemann and G.J. Woeginger
[View abstract]
Generalized satisfiability with \( k \) occurrences per variable: A - Study through Delta-matroid Parity
by Victor Dalmau and Daniel Ford
[View abstract]
On the Symbolic Analysis of Low-Level Cryptographic Primitives: Modular Exponentiation and the Diffie-Hellman Protocol
by Michele Boreale and Marzia Buscemi
[View abstract]
Randomized algorithms for determining the majority on graphs
by Gianluca De Marco, Andrzej Pelc
[View abstract]
Starting with nondeterminism: the systematic derivation of linear-time graph layout algorithms
by ans L. Bodlaender, Michael R. Fellows, and Dimitrios M. Thilikos
[View abstract]
Characterizations of Catalytic Membrane Computing Systems
by Oscar H. Ibarra, Zhe Dang, Omer Egecioglu and Gaurav Saxena
[View abstract]
Adversarial models for priority-based networks
by C. Alvarez, M.Blesa, J. Diaz, A. Fernandez, and M. Serna
[View abstract]
On Optimal Merging Networks
by Kazuyuki Amano and Akira Maruoka
[View abstract]
Relating Hierarchy of Temporal Properties to Model Checking
by Ivana Cerna and Radek Pelanek
[View abstract]
Which is the Worst-case Nash Equilibrium?
by Thomas Luecking, Marios Mavronicolas, Burkhard Monien, Manuel Rode, Paul Spirakis, Imrich Vrto
[View abstract]
Unambiguous automata on bi-infinite words
by Olivier Carton
[View abstract]
Problems which cannot be reduced to any proper subproblems
by Klaus Ambos-Spies
[View abstract]
Generic Algorithms for the Generation of Combinatorial Objects
by Conrado Martinez and Xavier Molinero
[View abstract]
A Basis of Tiling Motifs for Generating Repeated Patterns and its Complexity for Higher Quorum
by N. Pisanti, M. Crochemore, R. Grossi, M.-F. Sagot
[View abstract]
Denotational testing semantics in coinductive form
by Michele Boreale and Fabio Gadducci
[View abstract]
Quantum testers for hidden group properties
by Katalin Friedl, Frederic Magniez, Miklos Santha, Pranab Sen
[View abstract]
Faster Algorithms for k-Median Problems in Trees
by Robert R. Benkoczi, Binay K. Bhattacharya, Marek Chrobak, Lawrence L. Larmore, and Wojciech Rytter
[View abstract]

Back to MFCS 2003 Home Page


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