MFCS 2001
26th International Symposium on |
 |
MFCS 2001
26th International Symposium on |
|
Schedule
| Monday, August 27 | |
| 9:00 - 10:30 | Opening
Dana Scott (invited speaker) A New Category for Semantics |
| 10:30 - 10:50 | Coffee break |
| 10:50 - 11:10 | Automata on linear orderings
Veronique Bruyere, Olivier Carton |
| 11:15 - 11:35 | Towards regular languages over infinite
alphabets
Frank Neven, Thomas Schwentick, Victor Vianu |
| 11:40 - 12:00 | From bidirectionality to alternation
Nir Piterman, Moshe Vardi |
| 12:05 - 12:25 | Converting two-way nondeterministic unary
automata into simpler automata
Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini |
| Lunch | |
| 14:00 - 14:50 | Georg Gottlob (invited speaker)
Hypertree decompositions |
| 15:00 - 15:20 | Quantifier rank for parity of embedded
finite models
Herve Fournier |
| 15:25 - 15:45 | The Complexity of the minimal polynomial
Thanh Minh Hoang, Thomas Thierauf |
| 15:50 - 16:10 | The complexity of tensor circuit evaluation
Martin Beaudry, Markus Holzer |
| 16:10 - 16:30 | Coffee break |
| 16:30 - 16:50 | News from the online traveling repairman
Sven O. Krumke, Willem E. de Paepe, Diana Poensgen, Leen Stougie |
| 16:55 - 17:15 | On-line scheduling with tight deadlines
Chiu-Yuen Koo, Tak-Wah Lam, Tsuen-Wan Ngan, Kar-Keung To |
| 17:20 - 17:40 | Lower bounds for on-line single-machine
scheduling
Leah Epstein, Rob van Stee |
| 17:45 - 18:05 | A 3-approximation algorithm for movement
minimization in conveyor flow shop processing
Wolfgang Espelage, Egon Wanke |
| 18:10 - 18:30 | Alignment between two RNA structures
Zhuozhi Wang, Kaizhong Zhang |
| WELCOME PARTY | |
| Tuesday, August 28 | |
| 9:00 - 9:50 | Peter Buergisser (invited speaker)
On implications between P-NP-hypotheses: Decision versus computation in algebraic complexity |
| 10:00 - 10:20 | There are no sparse NPw-hard sets
Felipe Cucker, Dimitri Grigoriev |
| 10:25 - 10:45 | The computational power of a family of
decision forests
Kazuyuki Amano, Tsukuru Hirosawa, Yusuke Watanabe, Akira Maruoka |
| 10:45 - 11:10 | Coffee break |
| 11:10 - 11:30 | Word problems for 2-homogeneous monoids
and symmetric logspace
Markus Lohrey |
| 11:35 - 11:55 | Satisfiability of systems of equations
over finite monoids
Cris Moore, Pascal Tesson, Denis Therien |
| 12:00 - 12:25 | Syntactic semiring of a language
Libor Polak |
| Lunch | |
| 14:00 - 14:50 | Thomas Wilke (invited speaker)
Linear temporal logic and finite semigroups |
| 15:00 - 15:20 | On the equational definition of the least
prefixed point
Luigi Santocanale |
| 15:25 - 15:45 | Automatic verification of recursive procedures
with one integer parameter
Ahmed Bouajjani, Peter Habermehl, Richard Mayr |
| 15:50 - 16:10 | Checking amalgamability conditions for
Casl architectural specifications
Bartek Klin, Piotr Hoffman, Andrzej Tarlecki, Lutz Schroeder, Till Mossakowski |
| 16:10 - 16:30 | Coffee break |
| 16:30 - 17:20 | Peter Hoyer (invited speaker)
Introduction to quantum algorithmics: Searching, sorting and related problems |
| 17:30 - 17:50 | Exact results for accepting probabilities
of quantum automata
Andris Ambainis, Arnolds Kikusts |
| 17:55 - 18:15 | A time hierarchy for bounded one-way
cellular automata
Andreas Klein, Martin Kutrib |
| 18:20 - 18:40 | Algorithmic information theory and cellular
automata dynamics
Julien Cervelle, Bruno Durand, Enrico Formenti |
| Wednesday, August 29 | |
| 9:00 - 9:20 | Synchronizing finite automata on Eulerian
digraphs
Jarkko Kari |
| 9:25 - 9:45 | The size of power automata
Klaus Sutner |
| 9:50 - 10:10 | Note on minimal finite automata
Galina Jiraskova |
| 10:15 - 10:35 | Rational graphs trace context-sensitive
languages
Christophe Morvan, Colin Stirling |
| 10:40 - 11:00 | Characterization of context-free languages
with polynomially bounded ambiguity
Klaus Wich |
| 11:00 - 11:20 | Coffee break |
| 11:20 - 11:40 | Improved bounds on the weak Pigeonhole
principle and infinitely many primes from weaker axioms
Albert Atserias |
| 11:45 - 12:05 | On reducibility and symmetry of disjoint
NP-pairs
Pavel Pudlak |
| 12:10 - 12:30 | Sharing one secret vs. Sharing many secrets:
Tight bounds for the MAX improvement ratio
Giovanni Di Crescenzo |
| 12:35 - 12:55 | On pseudorandom generators in NC^0
Mary Cryan, Peter Bro Miltersen |
| Lunch | |
| Excursion + Conference dinner | |
| Thursday, August 30 | |
| 9:00 - 9:50 | Martin Hofmann (invited speaker)
The strength of non-size increasing computation |
| 10:00 - 10:20 | Analysis problems for sequential dynamical
systems and communicating state machines
Chris Barrett, Harry B. Hunt III, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Richard E. Stearns |
| 10:25 - 10:45 | Partial information and special case
algorithms
Arfst Nickelsen |
| 10:45 - 11:10 | Coffee break |
| 11:10 - 11:30 | On the computational complexity of infinite
words
Pavol Duris, Jan Manuch |
| 11:35 - 11:55 | On the periods of partial words
Arseny M. Shur, Yulia V. Konovalova |
| 12:00 - 12:20 | Variations on a theme of Fine and Wilf
Filippo Mignosi, Jeffrey Shallit, Ming-wei Wang |
| Lunch | |
| 14:00 - 14:50 | Dana Randall (invited speaker)
Decomposition methods for Markov chain analysis |
| 15:00 - 15:20 | The complexity of computing the number
of self-avoiding walks in two-dimensional grid graphs and in hypercube
graphs
Mitsunori Ogihara, Seinosuke Toda |
| 15:25 - 15:45 | Complexity note on mixed hypergraphs
Daniel Kral, Jan Kratochvil, Heinz-Juergen Voss |
| 15:50 - 16:10 | (H,C,K)-Coloring: Fast, easy, and hard
cases
Josep Diaz, Maria Serna, Dimitrios M. Thilikos |
| 16:10 - 16:30 | Coffee break |
| 16:30 - 17:20 | Erik Demaine (invited speaker)
Playing games with algorithms: Algorithmic combinatorial game theory |
| 17:30 - 17:50 | On the approximability of the Steiner
tree problem
Martin Thimm |
| 17:55 - 18:15 | Refined search tree techniques for dominating
set on planar graphs
Jochen Alber, Hongbing Fan, Michael R. Fellows, Henning Fernau, Rolf Niedermeier, Fran Rosamond, Ulrike Stege |
| 18:20 - 18:40 | Space hierarchy theorem revised
Viliam Geffert |
| Friday, August 31 | |
| 9:00 - 9:50 | Uwe Schoening (invited speaker)
New algorithms for k-SAT using the local search principle |
| 10:00 - 10:20 | Graph-driven free parity BDDs: Algorithms
and lower bounds
Henrik Brosenne, Matthias Homeister, Stephan Waack |
| 10:25 - 10:45 | Computing reciprocals of bivariate power
series
Markus Blaeser |
| 10:45 - 11:10 | Coffee break |
| 11:10 - 11:30 | Randomness and reducibility
Rod G. Downey, Denis R. Hirschfeldt, Geoff LaForte |
| 11:35 - 11:55 | Computable versions of Baire's category
theorem
Vasco Brattka |
| 12:00 - 12:20 | Hierarchy of monotonically computable
real numbers
Robert Rettinger, Xizhong Zheng |
| Lunch | |
| 14:00 - 14:50 | Amos Fiat (invited speaker)
Some Recent Results on Data Mining and Search |
| 15:00 - 15:20 | Approximation algorithms and complexity
results for path problems in trees of rings
Thomas Erlebach |
| 15:25 - 15:45 | The k-median problem for directed trees
Marek Chrobak, Lawrence Larmore, Wojciech Rytter |
| 15:50 - 16:10 | Upper bounds on the bisection width of
3- and 4-regular graphs
Burkhard Monien, Robert Preis |