MFCS 2010 Accepted Papers

Naoyuki Kamiyama. The Prize-Collecting Edge Dominating Set Problem in Trees
Beate Bollig. Exponential space complexity for symbolic maximum flow algorithms in 0-1 networks
Julien David . The Average Complexity of Moore's State Minimization Algorithm is O( n log log n)
Alexander Okhotin . Unambiguous finite automata over a unary alphabet
Bernd Puchala and Roman Rabinovich . Parity Games with Partial Information Played on Graphs of Bounded Complexity
Alberto Carraro, Thomas Ehrhard and Antonino Salibra . Resource combinatory algebras
Janos Csirik, Leah Epstein , Csanad Imreh and Asaf Levin . Online clustering with variable sized clusters
Manuel Bodirsky , Victor Dalmau, Barnaby Martin and Michael Pinsker . Distance Constraint Satisfaction Problems
Jörg Olschewski and Michael Ummels . The Complexity of Finding Reset Words in Finite Automata
Pascal Koiran , Natacha Portier and Bruno Grenet . The multivariate resultant is NP-hard in any characteristic
Yoshifumi Manabe and Tatsuaki Okamoto. Meta-Envy-Free Cake-Cutting Protocols
Jurek Czyzowicz, Adrian Kosowski and Andrzej Pelc . Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
Yann Strozecki. Enumeration of the monomials of a polynomial and related complexity classes
Nader Bshouty and Hanna Mazzawi. Toward Deterministic Polynomial Time Algorithm with Optimal Additive Query Complexity
Ioannis Chatzigiannakis , Othon Michail , Stavros Nikolaou, Andreas Pavlogiannis and Paul Spirakis . All Symmetric Predicates in NSPACE(n^2) are Stably Computable by the Mediated Population Protocol Model
Dmitri Akatov and Georg Gottlob . Balanced Queries: Divide and Conquer
Ke Yan and Ho Lun Cheng. Meshing Deforming Smooth Manifolds with Surface Correspondences
Artur Jeż and Alexander Okhotin . Least and greatest solutions of equations over sets of integers
Samir Datta , Meena Mahajan , B. V. Raghavendra Rao , Michael Thomas and Heribert Vollmer . Counting Classes and the fine structure between NC1 and L
Krishnendu Chatterjee, Laurent Doyen and Thomas Henzinger . Qualitative Analysis of Partially-observable Markov  Decision Processes
Gero Greiner and Riko Jacob . Evaluating Non-Square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model
Sanjoy K. Baruah, Vincenzo Bonifaci , Gianlorenzo D'Angelo , Haohan Li , Alberto Marchetti-Spaccamela , Nicole Megow and Leen Stougie . Scheduling Real-Time Mixed-Criticality Jobs
Amaldev Manuel . Two orders and two variables
Laurent Boyer and Guillaume Theyssier . On Factor Universality in Symbolic Spaces
Emmanuel Filiot , Tristan Le Gall and Jean-François Raskin . Iterated Regret Minimization in Game Graphs
Gaelle Fontaine and Thomas Place . Classes of trees definable in the mu-calculus
emmanuel Filiot, Jean-Francois Raskin , Pierre-Alain Reynier , Frédéric Servais and Jean-Marc Talbot. Properties of Visibly Pushdown Transducers
Giulio Manzonetto and Paolo Tranquilli . Harnessing MLF with the Power of System F
Nadja Betzler. On Problem Kernels for Possible Winner Determination Under the k-Approval Protocol
Dariusz Dereniowski. Connected searching of weighted trees
Krishnendu Chatterjee, Laurent Doyen , Hugo Gimbert and Thomas Henzinger . Randomness for Free
Hans L. Bodlaender , Erik Jan van Leeuwen , Johan M.M. van Rooij and Martin Vatshelle. Faster Algorithms on Branch and Clique Decompositions
Szczepan Hummel , Michał Skrzypczak and Szymon Toruńczyk . On the Topological Complexity of MSO+U and Related Automata Models
Subrahmanyam Kalyanasundaram , Richard J. Lipton , Kenneth Regan and Farbod Shokrieh. Improved Simulation of Nondeterministic Turing Machines
A Baskar , R. Ramanujam and S P Suresh . A DEXPTIME-complete Dolev-Yao theory with distributive encryption
Jing He, Hongyu Liang and Jayalal M.N. Sarma . Limiting Negations in Bounded Treewidth and Upward Planar Circuits
Kenya Ueno. Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds
M. Praveen . Does Treewidth Help in Modal Satisfiability? (Extended Abstract)
Dmitry Ananichev, Vladimir Gusev and Mikhail Volkov . Slowly synchronizing automata and digraphs
Yoram Bachrach , Michael Zuckerman, Jeffrey Rosenschein and Michael Wooldridge . Transformation Games
Stefan Kratsch , Daniel Marx and Magnus Wahlström . Parameterized complexity and kernelizability of Max Ones and Exact Ones problems
Laszlo Babai, Kristoffer Arnsfelt Hansen , Vladimir Podolskii and Xiaoming Sun. Weights of Exact Threshold Functions
Davide Bilò, Luciano Gualà and Guido Proietti . Improved approximability and non-approximability results for graph diameter decreasing problems
Davide Bilò, Luciano Gualà and Guido Proietti . Finding best swap edges minimizing the routing cost of a spanning tree
Ingmar Meinecke and Manfred Droste. Describing Average- and Longtime-Behavior by Weighted MSO Logics
Bernd Puchala . Asynchronous Omega-Regular Games with Partial Information
Sylvain Guillemot and Florian Sikora . Finding and counting vertex-colored subtrees
Mohammad Torabi Dashti and Bahareh Badban . Semi-linear Parikh images of regular expressions via reduction
Marius Zimand . Counting dependent and independent strings
Marius Zimand . Impossibility of independence amplification in Kolmogorov complexity theory
Marcelo Fiore and Ola Mahmoud. Second-Order Algebraic Theories
Ivona Bezakova and Adam Friedlander. Counting minimum (s,t)-cuts in weighted planar graphs in polynomial time
Neeldhara Misra , N.S. Narayanaswamy , Venkatesh Raman and Bal Sri Shankar. Solving Minones 2SAT as fast as Vertex Cover
Olivier Bournez , Daniel S. Graça and Emmanuel Hainry . Robust computations with dynamical systems
Siamak Tazari . Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs
Philippe Schnoebelen . Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets