FSTTCS 2011 Accepted Papers

Main Page FSTTCS 2011 Call for Papers Program Committee Organization Invited Speakers Accepted Papers Workshops Programme Proceedings Sponsors Local Arrangements Archives	FSTTCS 2011 Accepted Papers FSTTCS 2011 Accepted Papers Philippe Darondeau, Stéphane Demri, Roland Meyer and Christophe Morvan, Petri Net Reachability Graphs: Decidability Status of FO Properties Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Frances Rosamond, Stephan Thomasse and Anders Yeo, Simultaneously Satisfying Linear Equations Over $\mathbb{F}_2$: MaxLin2 and Max-$r$-Lin2 Parameterized Above Average Abhijin Adiga, L. Sunil Chandran and Rogers Mathew, Cubicity, Degeneracy, and Crossing Number Hongfei Fu and Joost-Pieter Katoen, Deciding Probabilistic Simulation between Probabilistic Pushdown Automata and Finite-State Systems Mohamed Faouzi Atig and Pierre Ganty, Approximating Petri Net Reachability Along Context-free Traces Fedor V. Fomin, Geevarghese Philip and Yngve Villanger, Minimum Fill-in of Sparse Graphs: Kernelization and Approximation Johannes Ebbing, Arnaud Durand, Juha Kontinen and Heribert Vollmer, Dependence logic with a majority quantifier Yang Cai and Ting Zhang, A Tight Lower Bound for Streett Complementation Matthew Hague, Parameterised Pushdown Systems with Non-Atomic Writes Jakub Michaliszyn, Emanuel Kieroński and Jan Otop, Modal Logics Definable by Universal Three-Variable Formulas Bruno Grenet, Pascal Koiran, Natacha Portier and Yann Strozecki, The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent Denis Kuperberg and Michael Vanden Boom, Quasi-Weak Cost Automata: A New Variant of Weakness Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier and Frédéric Servais, Streamability of Nested Word Transductions Prabhanjan Ananth, Meghana Nasre and Kanthi Sarpatwar, Rainbow Connectivity: Hardness and Tractability John Fearnley, Markus Rabe, Sven Schewe and Lijun Zhang, Efficient Approximation of Optimal Control for Continuous-Time Markov Games Frédéric Herbreteau, Dileep Kini, B Srivathsan and Igor Walukiewicz, Using non-convex approximations for efficient analysis of timed automata Oren Ben-Kiki, Philip Bille, Dany Breslauer, Roberto Grossi and Oren Weimann, Optimal Packed String Matching Ocan Sankur, Patricia Bouyer and Nicolas Markey, Shrinking Timed Automata Pinar Heggernes, Pim Van 'T Hof, Daniel Lokshtanov and Christophe Paul, Obtaining a bipartite graph by contracting few edges Raghavendra Rao B V and Jayalal M.N. Sarma, Isomorphism testing of read-once functions and polynomials Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk and Piotr Sankowski, Approximation Algorithms for Union and Intersection Covering Problems Stefan Göller and Markus Lohrey, The First-Order Theory of Ground Tree Rewrite Graphs Christian Glasser, Christian Reitwießner and Maximilian Witek, Applications of Discrepancy Theory in Multiobjective Approximation Saverio Caminiti, Irene Finocchi, Emanuele Guido Fusco and Francesco Silvestri, Dynamic programming in faulty memory hierarchies (cache-obliviously) Sander Bruggink, Raphaël Cauderlier, Mathias Hülsbusch and Barbara König, Conditional Reactive Systems Didier Caucal and Teodor Knapik, Infinite monadic systems Bertram Felgenhauer, Harald Zankl and Aart Middeldorp, Layer Systems for Proving Confluence Céline Chevalier, Stephanie Delaune and Steve Kremer, Transforming Password Protocols to Compose Nathalie Bertrand and Blaise Genest, Minimal Disclosure in Partially Observable Markov Decision Processes Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou and Avner Magen, Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy Aleksander Madry and Debmalya Panigrahi, The Semi-stochastic Ski-rental Problem Manoj Gupta, Yogish Sabharwal and Sandeep Sen, The update complexity of selection and related problems Uli Fahrenberg, Axel Legay and Claus Thrane, The Quantitative Linear-Time–Branching-Time Spectrum Pablo Barceló, Leonid Libkin and Juan L. Reutter, Parameterized Regular Expressions and Their Languages Patricia Bouyer, Romain Brenguier, Nicolas Markey and Michael Ummels, Nash Equilibria in Concurrent Games with Büchi Objectives Dietmar Berwanger, Kaiser Lukasz and Bernd Puchala, Perfect-Information Construction for Coordination in Games Jacques Duparc, Alessandro Facchini and Filip Murlak, Definable Operations On Weakly Recognizable Sets of Trees

Philippe Darondeau, Stéphane Demri, Roland Meyer and Christophe Morvan, Petri Net Reachability Graphs: Decidability Status of FO Properties
Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Frances Rosamond, Stephan Thomasse and Anders Yeo, Simultaneously Satisfying Linear Equations Over $\mathbb{F}_2$: MaxLin2 and Max-$r$-Lin2 Parameterized Above Average
Abhijin Adiga, L. Sunil Chandran and Rogers Mathew, Cubicity, Degeneracy, and Crossing Number
Hongfei Fu and Joost-Pieter Katoen, Deciding Probabilistic Simulation between Probabilistic Pushdown Automata and Finite-State Systems
Mohamed Faouzi Atig and Pierre Ganty, Approximating Petri Net Reachability Along Context-free Traces
Fedor V. Fomin, Geevarghese Philip and Yngve Villanger, Minimum Fill-in of Sparse Graphs: Kernelization and Approximation
Johannes Ebbing, Arnaud Durand, Juha Kontinen and Heribert Vollmer, Dependence logic with a majority quantifier
Yang Cai and Ting Zhang, A Tight Lower Bound for Streett Complementation
Matthew Hague, Parameterised Pushdown Systems with Non-Atomic Writes
Jakub Michaliszyn, Emanuel Kieroński and Jan Otop, Modal Logics Definable by Universal Three-Variable Formulas
Bruno Grenet, Pascal Koiran, Natacha Portier and Yann Strozecki, The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent
Denis Kuperberg and Michael Vanden Boom, Quasi-Weak Cost Automata: A New Variant of Weakness
Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier and Frédéric Servais, Streamability of Nested Word Transductions
Prabhanjan Ananth, Meghana Nasre and Kanthi Sarpatwar, Rainbow Connectivity: Hardness and Tractability
John Fearnley, Markus Rabe, Sven Schewe and Lijun Zhang, Efficient Approximation of Optimal Control for Continuous-Time Markov Games
Frédéric Herbreteau, Dileep Kini, B Srivathsan and Igor Walukiewicz, Using non-convex approximations for efficient analysis of timed automata
Oren Ben-Kiki, Philip Bille, Dany Breslauer, Roberto Grossi and Oren Weimann, Optimal Packed String Matching
Ocan Sankur, Patricia Bouyer and Nicolas Markey, Shrinking Timed Automata
Pinar Heggernes, Pim Van 'T Hof, Daniel Lokshtanov and Christophe Paul, Obtaining a bipartite graph by contracting few edges
Raghavendra Rao B V and Jayalal M.N. Sarma, Isomorphism testing of read-once functions and polynomials
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk and Piotr Sankowski, Approximation Algorithms for Union and Intersection Covering Problems
Stefan Göller and Markus Lohrey, The First-Order Theory of Ground Tree Rewrite Graphs
Christian Glasser, Christian Reitwießner and Maximilian Witek, Applications of Discrepancy Theory in Multiobjective Approximation
Saverio Caminiti, Irene Finocchi, Emanuele Guido Fusco and Francesco Silvestri, Dynamic programming in faulty memory hierarchies (cache-obliviously)
Sander Bruggink, Raphaël Cauderlier, Mathias Hülsbusch and Barbara König, Conditional Reactive Systems
Didier Caucal and Teodor Knapik, Infinite monadic systems
Bertram Felgenhauer, Harald Zankl and Aart Middeldorp, Layer Systems for Proving Confluence
Céline Chevalier, Stephanie Delaune and Steve Kremer, Transforming Password Protocols to Compose
Nathalie Bertrand and Blaise Genest, Minimal Disclosure in Partially Observable Markov Decision Processes
Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou and Avner Magen, Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy
Aleksander Madry and Debmalya Panigrahi, The Semi-stochastic Ski-rental Problem
Manoj Gupta, Yogish Sabharwal and Sandeep Sen, The update complexity of selection and related problems
Uli Fahrenberg, Axel Legay and Claus Thrane, The Quantitative Linear-Time–Branching-Time Spectrum
Pablo Barceló, Leonid Libkin and Juan L. Reutter, Parameterized Regular Expressions and Their Languages
Patricia Bouyer, Romain Brenguier, Nicolas Markey and Michael Ummels, Nash Equilibria in Concurrent Games with Büchi Objectives
Dietmar Berwanger, Kaiser Lukasz and Bernd Puchala, Perfect-Information Construction for Coordination in Games
Jacques Duparc, Alessandro Facchini and Filip Murlak, Definable Operations On Weakly Recognizable Sets of Trees