MFCS & CSL 2010
Petrov - Cathedral of St. Peter, Brno

Contacts

General questions about organization, registration, accomodation, etc., should be sent to

xrebok@fi.muni.cz

Program-related questions should be directed to program committee chairs.

More details

Program

Monday, August 23

8:15-8:30 Conference opening.
8:30-9:30 Invited plenary talk.
Erich Grädel. Definability in Games.
9:30-10:00 Coffee break.
10:00-10:55
CSL Invited talk. MFCS, track I.
10:00-10:55 Jan Krajíček. From Feasible Proofs to Feasible Computations 10:00-10:25 Davide Bilo, Luciano Guala, and Guido Proietti. Improved Approximability and Non-Approximability Results for Graph Diameter Decreasing Problems.
10:25-10:50 Manuel Bodirsky, Victor Dalmau, Barnaby Martin, and Michael Pinsker. Distance Constraint Satisfaction Problems.
11:10-12:00
CSL track. MFCS, track I. MFCS, track II.
11:10-11:35 Kord Eickmeyer and Martin Grohe.Randomisation and Derandomisation in Descriptive Complexity Theory. 11:10-11:35 Ivona Bezáková and Adam J. Friedlander.Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time. 11:10-11:35 Artur Jež and Alexander Okhotin. Least and Greatest Solutions of Equations over Sets of Integers.
11:35-12:00 Yijia Chen and Jörg Flum. On Slicewise Monotone Parameterized Problems and Optimal Proof Systems for TAUT. 11:35-12:00 Dariusz Dereniowski. Connected Searching of Weighted Trees. 11:35-12:00 Bahareh Badban and Mohammad Torabi Dashti. Semi-linear Parikh Images of Regular Expressions via Reduction.
12:00-14:00 Lunch.
14:00-14:55
CSL track. MFCS invited talk.
14:00-14:25 Michael Benedikt, Clemens Ley, and Gabriele Puppis. Automata vs. Logics on Data Words. 14:00-14:55 Juraj Hromkovič (joint work with Rastislav Královič and Richard Královič). Information Complexity of Online Problems.
14:25-14:50 Guillaume Bagan, Arnaud Durand, Emmanuel Filiot, and Olivier Gauwin. Efficient Enumeration for Conjunctive Queries over X-underbar Structures.
14:55-15:30 Coffee break.
15:30-16:45
CSL track. MFCS, track I. MFCS, track II.
15:30-15:55 Bob Coecke and Simon Perdrix. Environment and Classical Channels in Categorical Quantum Mechanics. 15:30-15:55 János Csirik, Leah Epstein, Csanád Imreh, and Asaf Levin. Online Clustering with Variable Sized Clusters. 15:30-15:55 Philippe Schnoebelen. Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets.
15:55-16:20 Aldric Degorre, Laurent Doyen, Raffaella Gentilini, Jean-François Raskin, and Szymon Toruńczyk. Energy and Mean-Payoff Games with Imperfect Information. 15:55-16:20 Sanjoy K. Baruah, Vincenzo Bonifaci, Gianlorenzo D’Angelo, Haohan Li, Alberto Marchetti-Spaccamela, Nicole Megow, and Leen Stougie. Scheduling Real-Time Mixed-Criticality Jobs. 15:55-16:20 Dmitry Ananichev, Vladimir Gusev, and Mikhail Volkov. Slowly Synchronizing Automata and Digraphs.
16:20-16:45 Bernd Finkbeiner and Sven Schewe. Coordination Logic. 16:20-16:45 Yoshifumi Manabe and Tatsuaki Okamoto. Meta-Envy-Free Cake-Cutting Protocols. 16:20-16:45 Jörg Olschewski and Michael Ummels. The Complexity of Finding Reset Words in Finite Automata.
17:00-18:15
CSL track. MFCS, track I. MFCS, track II.
17:00-17:25 Aditi Barthwal and Michael Norrish. Formalization of the Normal Forms of Context-Free Grammars in HOL4. 17:00-17:25 Yann Strozecki. Enumeration of the Monomials of a Polynomial and Related Complexity Classes. 17:00-17:25 Krishnendu Chatterjee, Laurent Doyen, Hugo Gimbert, and Thomas A. Henzinger. Randomness for Free.
17:25-17:50 Marcelo Fiore and Chung-Kil Hur. Second-Order Equational Logic. 17:25-17:50 Bruno Grenet, Pascal Koiran, and Natacha Portier. The Multivariate Resultant Is NP-hard in Any Characteristic. 17:25-17:50 Emmanuel Filiot, Tristan Le Gall, and Jean-François Raskin. Iterated Regret Minimization in Game Graphs.
17:50-18:15 Pierre-yves Strub. Coq Modulo Theories.
18:30-21:00 Welcome party.

Tuesday, August 24

8:30-9:30 Invited plenary talk.
Herbert Edelsbrunner (joint work with Paul Bendich, Michael Kerber, and Amit Patel). Persistent Homology under Non-uniform Error
9:30-10:00 Coffee break.
10:00-10:55
CSL Invited talk. MFCS, track I.
10:00-10:55 Andrey Rybalchenko. Constraint Solving for Program Verification: Theory and Practice by Example. 10:00-10:25 Stefan Kratsch, Dániel Marx, and Magnus Wahlström. Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems.
10:25-10:50 Siamak Tazari. Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs.
11:10-12:00
CSL track. MFCS, track I. MFCS, track II.
11:10-11:35 Alessandro Bianco, Fabio Mogavero, and Aniello Murano. Graded Computation Tree Logic with Binary Coding. 11:10-11:35 Hans L. Bodlaender, Erik Jan van Leeuwen, Johan M. M. van Rooij, and Martin Vatshelle. Faster Algorithms on Branch and Clique Decompositions. 11:10-11:35 Marius Zimand. Impossibility of Independence Amplification in Kolmogorov Complexity Theory.
11:35-12:00 Thomas Schwentick and Thomas Zeume. Two-variable Logic with Two Order Relations. 11:35-12:00 Jing He, Hongyu Liang, and Jayalal M. N. Sarma. Limiting Negations in Bounded Treewidth and Upward Planar Circuits. 11:35-12:00 Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Qualitative Analysis of Partially-Observable Markov Decision Processes.
12:00-14:00 Lunch.
14:00-14:55
CSL track. MFCS invited talk.
14:00-14:25 Fredrik Nordvall Forsberg and Anton Setzer. Inductive-inductive definitions. 14:00-14:55 Daniel Lokshtanov. Algorithmic Lower Bounds for Problems on Decomposable Graphs.
14:25-14:50 Neil Ghani, Patricia Johann, and Clément Fumex. Fibrational Induction Rules for Initial Algebras.
14:55-15:30 Coffee break.
15:30-16:45
CSL track. MFCS, track I. MFCS, track II.
15:30-15:55 Delia Kesner and Beniamino Accattoli. The structural lambda-calculus. 15:30-15:55 Davide Bilo, Luciano Guala, and Guido Proietti. Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree. 15:30-15:55 Marius Zimand. Counting Dependent and Independent Strings.
15:55-16:20 Regis Alenda, Nicola Olivetti, Camilla Schwind, and Dmitry Tishkovsky. Tableau calculi for !CSL over minspaces. 15:55-16:20 Sylvain Guillemot and Florian Sikora. Finding and Counting Vertex-Colored Subtrees. 15:55-16:20 Alberto Carraro, Thomas Ehrhard, and Antonino Salibra. Resource Combinatory Algebras.
16:20-16:45 Martin Churchill and James Laird. A Logic of Sequentiality. 16:20-16:45 Naoyuki Kamiyama. The Prize-Collecting Edge Dominating Set Problem in Trees. 16:20-16:45 Marcelo Fiore and Ola Mahmoud. Second-Order Algebraic Theories.
17:00-17:50
CSL track. MFCS, track I. MFCS, track II.
17:00-17:25 Andreas Blass, Nachum Dershowitz and Yuri Gurevich. Exact Exploration and Hanging Algorithms. 17:00-17:25 Gero Greiner and Riko Jacob. Evaluating Non-square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model. 17:00-17:25 Jurek Czyzowicz, Adrian Kosowski, and Andrzej Pelc. Deterministic Rendezvous of Asynchronous Bounded-Memory Agents in Polygonal Terrains.
17:25-17:50 Yavor Nenov and Ian Pratt-Hartmann. On the Computability of Region-based Euclidean Logics. 17:25-17:50 Beate Bollig. Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks. 17:25-17:50 Ho-Lun Cheng and Ke Yan. Mesh Deformation of Dynamic Smooth Manifolds with Surface Correspondences.
18:00-19:00 EACSL General Assembly.

Wednesday, August 25

8:30-9:30 Invited plenary talk.
Joseph Sifakis. Embedded Systems Design – Scientific Challenges and Work Directions.
9:30-10:00 Coffee break.
10:00-10:55 CSL Invited talk.
Peter O’Hearn. Abductive, Inductive and Deductive Reasoning about Resources.
11:05-12:00 CSL Invited talk.
Andrei Krokhin. Tree Dualities for Constraint Satisfaction.
12:00-14:00 Lunch.
14:00-22:00 Conference trip and dinner.

Thursday, August 26

8:30-9:30 Invited plenary talk.
David Basin. Degrees of Security: Protocol Guarantees in the Face of Compromising Adversaries.
9:30-10:00 Coffee break.
10:00-10:55
CSL Invited talk. MFCS, track I.
10:00-10:55 Viktor Kuncak. Ordered Sets in the Calculus of Data Structures. 10:00-10:25 Subrahmanyam Kalyanasundaram, Richard J. Lipton, Kenneth W. Regan, and Farbod Shokrieh. Improved Simulation of Nondeterministic Turing Machines.
10:25-10:50 László Babai, Kristoffer Arnsfelt Hansen, Vladimir Podolskii, and Xiaoming Sun. Weights of Exact Threshold Functions.
11:10-12:00
CSL track. MFCS, track I. MFCS, track II.
11:10-11:35 Peter Lohmann and Heribert Vollmer. Complexity Results for Modal Dependence Logic. 11:10-11:35 Nadja Betzler. On Problem Kernels for Possible Winner Determination under the k-Approval Protocol. 11:10-11:35 Emmanuel Filiot, Jean-François Raskin, Pierre-Alain Reynier, Frédéric Servais, and Jean-Marc Talbot. Properties of Visibly Pushdown Transducers.
11:35-12:00 Barnaby Martin and Jos Martin. The complexity of positive first-order logic without equality II: The four-element case. 11:35-12:00 Neeldhara Misra, N. S. Narayanaswamy, Venkatesh Raman, and Bal Sri Shankar. Solving MINONES-2-SAT as Fast as VERTEX COVER. 11:35-12:00 Alexander Okhotin. Unambiguous Finite Automata over a Unary Alphabet.
12:00-14:00 Lunch.
14:00-14:55
CSL track. MFCS invited talk.
14:00-14:25 Stephen Cook and Lila Fontes. Formal Theories for Linear Algebra. 14:00-14:55 Andris Ambainis. New Developments in Quantum Algorithms.
14:25-14:50 Guillaume Burel. Embedding Deduction Modulo into a Prover.
14:55-15:30 Coffee break.
15:30-16:45
CSL track. MFCS, track I. MFCS, track II.
15:30-15:55 Jose Espirito Santo. Towards a canonical classical natural deduction system. 15:30-15:55 Nader H. Bshouty and Hanna Mazzawi. Toward a Deterministic Polynomial Time Algorithm with Optimal Additive Query Complexity. 15:30-15:55 Bernd Puchala. Asynchronous Omega-Regular Games with Partial Information.
15:55-16:20 Matthias Baaz and Christian Fermüller. A Resolution Mechanism for Prenex Gödel Logic. 15:55-16:20 Laurent Boyer and Guillaume Theyssier. On Factor Universality in Symbolic Spaces. 15:55-16:20 Yoram Bachrach, Michael Zuckerman, Michael Wooldridge, and Jeffrey S. Rosenschein. Proof Systems and Transformation Games.
16:20-16:45 Stefan Hetzl. A Sequent Calculus with Implicit Term Representation. 16:20-16:45 Olivier Bournez, Daniel S. Graça, and Emmanuel Hainry. Robust Computations with Dynamical Systems. 16:20-16:45 Bernd Puchala and Roman Rabinovich. Parity Games with Partial Information Played on Graphs of Bounded Complexity.
17:00-18:15
CSL track. MFCS, track I. MFCS, track II.
17:00-17:25 Dietrich Kuske, Jiamou Liu, and Markus Lohrey. The Isomorphism Problem for omega-Automatic Trees. 17:00-17:25 Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, Andreas Pavlogiannis, and Paul G. Spirakis. All Symmetric Predicates in NSPACE(n2) Are Stably Computable by the Mediated Population Protocol Model. 17:00-17:25 Amaldev Manuel. Two Variables and Two Successors.
17:25-17:50 Lukasz Kaiser and Tobias Ganzow. New Algorithm for Weak Monadic Second-Order Logic on Inductive Structures. 17:25-17:50 Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, and Heribert Vollmer. Counting Classes and the Fine Structure between NC1 and L. 17:25-17:50 Gaëlle Fontaine and Thomas Place. Frame Definability for Classes of Trees in the μ-calculus.
17:50-18:15 Andre Platzer. Quantified Differential Dynamic Logic for Distributed Hybrid Systems.

Friday, August 27

8:30-9:30 Invited plenary talk.
Bojan Mohar. Do We Really Understand the Crossing Numbers?
9:30-10:00 Coffee break.
10:00-11:00
CSL track. MFCS, track I. MFCS, track II.
10:00-10:25 Christian Sternagel and René Thiemann. Signature Extensions Preserve Termination: An Alternative Proof via Dependency Pairs. 10:00-10:25 Kenya Ueno. Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds. 10:00-10:25 Giulio Manzonetto and Paolo Tranquilli. Harnessing MLF with the Power of System F.
10:25-10:50 Alberto Carraro, Thomas Ehrhard and Antonino Salibra. Exponentials with Infinite Multiplicities 10:25-10:50 A. Baskar, R. Ramanujam, and S. P. Suresh. A DEXPTIME-Complete Dolev-Yao Theory with Distributive Encryption. 10:25-10:50 Manfred Droste and Ingmar Meinecke. Describing Average- and Longtime-Behavior by Weighted MSO Logics.
11:10-12:00
CSL track. MFCS, track I. MFCS, track II.
11:10-11:35 Damien Pous. Untyping Typed Algebraic Structures and Colouring Proof Nets of Cyclic Linear Logic. 11:10-11:35 Dmitri Akatov and Georg Gottlob. Balanced Queries: Divide and Conquer. 11:10-11:35 Szczepan Hummel, Michał Skrzypczak, and Szymon Toruńczyk. On the Topological Complexity of MSO+U and Related Automata Models.
11:35-12:00 Kaustuv Chaudhuri. Classical and Intuitionistic Subexponential Logics are Equally Expressive. 11:35-12:00 M. Praveen. Does Treewidth Help in Modal Satisfiability? 11:35-12:00 Julien David. The Average Complexity of Moore’s State Minimization Algorithm Is O(n log(log(n))).
12:00-14:00 Lunch.
The End of MFCS and CSL 2010.