Mathematical foundations of computer science 2012 : 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings /
Mathematical foundations of computer science 2012 : 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings /
MFCS 2012
Branislav Rovan, Vladimiro Sassone, Peter Widmayer (eds.).
- Berlin ; New York : Springer, ©2012.
- 1 online resource (xv, 838 pages) : illustrations
- Lecture notes in computer science, Advanced research in computing and software science 7464. 1611-3349 ; LNCS sublibrary. SL 1, Theoretical computer science and general issues .
- Lecture notes in computer science ; 7464. Lecture notes in computer science. Advanced research in computing and software science. LNCS sublibrary. SL 1, Theoretical computer science and general issues. .
International conference proceedings.
Includes bibliographical references and author index.
On the Complexity of Ontological Reasoning under Disjunctive Existential Rules / New Races in Parameterized Algorithmics / Scott Is Always Simple / A Toolkit for Proving Limitations of the Expressive Power of Logics / How to Reconstruct a Genome / Simple Models for Recursive Schemes / Transportation under Nasty Side Constraints / Computation of Least Fixed Points / Unordered Constraint Satisfaction Games / A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree / Reductions to the Set of Random Strings: The Resource-Bounded Case / Approximate Graph Isomorphism / Near-Optimal Expanding Generator Sets for Solvable Permutation Groups / Generating Functions of Timed Languages / The Robust Set Problem: Parameterized Complexity and Approximation / Mortality for 2 x 2 Matrices Is NP-Hard / Solving Counter Parity Games / Drawing Planar Graphs on Points Inside a Polygon / New Advances in Reoptimizing the Minimum Steiner Tree Problem / Smoothed Complexity Theory / Abelian Pattern Avoidance in Partial Words / The Complexity of Rerouting Shortest Paths / Computing with Large Populations Using Interactions / Pancake Flipping Is Hard / In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses / Model Checking Stochastic Branching Processes / Georg Gottlob, Marco Manna, Michael Morak and Andreas Pieris -- Christian Komusiewicz and Rolf Niedermeier -- Antonino Salibra -- Nicole Schweikardt -- Esko Ukkonen -- Igor Walukiewicz -- Gerhard J. Woeginger -- Mihalis Yannakakis -- Lauri Ahlroth and Pekka Orponen -- Tatsuya Akutsu and Takeyuki Tamura -- Eric Allender, Harry Buhrman, Luke Friedman and Bruno Loff -- Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert and Yadu Vasudev -- Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar and Yadu Vasudev -- Eugene Asarin, Nicolas Basset, Aldric Degorre and Dominique Perrin -- Cristina Bazgan and Morgan Chopin -- Paul C. Bell, Mika Hirvensalo and Igor Potapov -- Dietmar Berwanger, Łukasz Kaiser and Simon Lessenich -- Therese Biedl and Peter Floderus -- Davide Bilò and Anna Zych -- Markus Bläser and Bodo Manthey -- Francine Blanchet-Sadri and Sean Simmons -- Paul Bonsma -- Olivier Bournez, Pierre Fraigniaud and Xavier Koegler -- Laurent Bulteau, Guillaume Fertin and Irena Rusu -- Jingsen Chen, Stefan Edelkamp, Amr Elmasry and Jyrki Katajainen -- Taolue Chen, Klaus Dräger and Stefan Kiefer. Parameterized Study of the Test Cover Problem / Sitting Closer to Friends Than Enemies, Revisited / A Dichotomy Theorem for Homomorphism Polynomials / Finite State Transducers for Modular Möbius Number Systems / Zero-Knowledge Proofs via Polynomial Representations / Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width / On the Impact of Fair Best Response Dynamics / Fast Balanced Partitioning Is Hard Even on Grids and Trees / A Characterization of Bispecial Sturmian Words / Online Sum-Radii Clustering / Observe and Remain Silent (Communication-Less Agent Location Discovery) / When Trees Grow Low: Shrubs and Fast MSO1 / Strategy Machines and Their Complexity / Coloring Graphs Characterized by a Forbidden Subgraph / Obtaining Planarity by Contracting Few Edges / Light Spanners in Bounded Pathwidth Graphs / Planarizing Gadgets for Perfect Matching Do Not Exist / Kernels for Edge Dominating Set: Simpler or Smaller / Categories of Coalgebraic Games / Quasi-recognizable vs MSO Definable Languages of One-Dimensional Overlapping Tiles / An Improved Approximation Scheme for Variable-Sized Bin Packing / Gathering an Even Number of Robots in an Odd Ring without Global Multiplicity Detection / Reversal Hierarchies for Small 2DFAs / Robert Crowston, Gregory Gutin, Mark Jones, Saket Saurabh and Anders Yeo -- Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk and Jakub Onufry Wojtaszczyk -- Nicolas de Rugy-Altherre -- Martin Delacourt and Petr Kůrka -- Giovanni Di Crescenzo and Vadym Fedyukovych -- Martin Doucha and Jan Kratochvíl -- Angelo Fanelli, Luca Moscardelli and Alexander Skopalik -- Andreas Emil Feldmann -- Gabriele Fici -- Dimitris Fotakis and Paraschos Koutris -- Tom Friedetzky, Leszek Gąsieniec, Thomas Gorry and Russell Martin -- Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek and Patrice Ossona de Mendez, et al. -- Marcus Gelderie -- Petr A. Golovach, Daniël Paulusma and Bernard Ries -- Petr A. Golovach, Pim van 't Hof and Daniël Paulusma -- Michelangelo Grigni and Hao-Hsiang Hung -- Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub and Thomas Thierauf -- Torben Hagerup -- Furio Honsell, Marina Lenisa and Rekha Redamalla -- David Janin -- Klaus Jansen and Stefan Kraft -- Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita and Sébastien Tixeuil -- Christos A. Kapoutsis and Giovanni Pighizzini. (Extended Abstract) / Strictness of the Collapsible Pushdown Hierarchy / Computational Complexity of Smooth Differential Equations / The Lower Reaches of Circuit Uniformity / The Join Levels of the Trotter-Weil Hierarchy Are Decidable / Equations X+A=B and (X+X)+C=(X -- X)+D over Sets of Natural Numbers / Weakly-Synchronized Ground Tree Rewriting (with Applications to Verifying Multithreaded Programs) / Descriptional Complexity of Deterministic Regular Expressions / Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs / Fine and Wilf's Theorem and Pseudo-repetitions / Taking It to the Limit: Approximate Reasoning for Markov Processes / Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games / Between Tree Patterns and Conjunctive Queries: Is There Tractability beyond Acyclicity? / Reducing a Target Interval to a Few Exact Queries / Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs / A Finite Basis for 'Almost Future' Temporal Logic over the Reals / Constructing Premaximal Ternary Square-Free Words of Any Level / Regularity Problems for Weak Pushdown [omega]-Automata and Games / Computational Aspects of Cellular Automata on Countable Sofic Shifts / Computing Lempel-Ziv Factorization Online / On Two Stronger Versions of Dejean's Conjecture / Probabilistic Automata and Probabilistic Logic / A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments / Alexander Kartzow and Paweł Parys -- Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick and Martin Ziegler -- Christoph Behle, Andreas Krebs, Klaus-Jörn Lange and Pierre McKenzie -- Manfred Kufleitner and Alexander Lauser -- Tommi Lehtinen -- Anthony Widjaja Lin -- Katja Losemann, Wim Martens and Matthias Niewerth -- Meena Mahajan, B.V. Raghavendra Rao and Karteek Sreenivasaiah -- Florin Manea, Robert Mercaş and Dirk Nowotka -- Kim Guldstrand Larsen, Radu Mardare and Prakash Panangaden -- Matúš Mihalák and Jan Christoph Schlegel -- Filip Murlak, Michał Ogiński and Marcin Przybyłko -- Jesper Nederlof, Erik Jan van Leeuwen and Ruben van der Zwaan -- Sotiris Nikoletseas, Christoforos Raptopoulos and Paul G. Spirakis -- Dorit Pardo (Ordentlich) and Alexander Rabinovich -- Elena A. Petrova and Arseny M. Shur -- Christof Löding and Stefan Repke -- Ville Salo and Ilkka Törmä -- Tatiana Starikovskaya -- Igor N. Tunev and Arseny M. Shur -- Thomas Weidner -- Mingyu Xiao and Jiong Guo.
This volume constitutes the refereed proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012, held in Bratislava, Slovakia, in August 2012. The 63 revised full papers presented together with 8 invited talks were carefully reviewed and selected from 162 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, databases and knowledge-based systems, foundations of computing, logic in computer science, models of computation, semantics and verification of programs, and theoretical issues in artificial intelligence.
9783642325892 3642325890 3642325882 9783642325885
10.1007/978-3-642-32589-2 doi 9783642325885
9783642325885 00024965
016169308 Uk
Computer science--Mathematics--Congresses.
Computer programming--Congresses.
Computer algorithms--Congresses.
Informatique--Mathématiques--Congrès.
Programmation (Informatique)--Congrès.
Algorithmes--Congrès.
Logiciels.
Informatique.
software.
computer science.
data processing.
Informatique.
Computer algorithms
Computer programming
Computer science--Mathematics
Computer science. Data structures (Computer science) Computational complexity. Algorithm Analysis and Problem Complexity. Discrete Mathematics in Computer Science. Numeric Computing. Mathematical Logic and Formal Languages. Math Applications in Computer Science.
Conference papers and proceedings
Software.
QA76.9.M35 / S96 2012
004.01/51
International conference proceedings.
Includes bibliographical references and author index.
On the Complexity of Ontological Reasoning under Disjunctive Existential Rules / New Races in Parameterized Algorithmics / Scott Is Always Simple / A Toolkit for Proving Limitations of the Expressive Power of Logics / How to Reconstruct a Genome / Simple Models for Recursive Schemes / Transportation under Nasty Side Constraints / Computation of Least Fixed Points / Unordered Constraint Satisfaction Games / A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree / Reductions to the Set of Random Strings: The Resource-Bounded Case / Approximate Graph Isomorphism / Near-Optimal Expanding Generator Sets for Solvable Permutation Groups / Generating Functions of Timed Languages / The Robust Set Problem: Parameterized Complexity and Approximation / Mortality for 2 x 2 Matrices Is NP-Hard / Solving Counter Parity Games / Drawing Planar Graphs on Points Inside a Polygon / New Advances in Reoptimizing the Minimum Steiner Tree Problem / Smoothed Complexity Theory / Abelian Pattern Avoidance in Partial Words / The Complexity of Rerouting Shortest Paths / Computing with Large Populations Using Interactions / Pancake Flipping Is Hard / In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses / Model Checking Stochastic Branching Processes / Georg Gottlob, Marco Manna, Michael Morak and Andreas Pieris -- Christian Komusiewicz and Rolf Niedermeier -- Antonino Salibra -- Nicole Schweikardt -- Esko Ukkonen -- Igor Walukiewicz -- Gerhard J. Woeginger -- Mihalis Yannakakis -- Lauri Ahlroth and Pekka Orponen -- Tatsuya Akutsu and Takeyuki Tamura -- Eric Allender, Harry Buhrman, Luke Friedman and Bruno Loff -- Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert and Yadu Vasudev -- Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar and Yadu Vasudev -- Eugene Asarin, Nicolas Basset, Aldric Degorre and Dominique Perrin -- Cristina Bazgan and Morgan Chopin -- Paul C. Bell, Mika Hirvensalo and Igor Potapov -- Dietmar Berwanger, Łukasz Kaiser and Simon Lessenich -- Therese Biedl and Peter Floderus -- Davide Bilò and Anna Zych -- Markus Bläser and Bodo Manthey -- Francine Blanchet-Sadri and Sean Simmons -- Paul Bonsma -- Olivier Bournez, Pierre Fraigniaud and Xavier Koegler -- Laurent Bulteau, Guillaume Fertin and Irena Rusu -- Jingsen Chen, Stefan Edelkamp, Amr Elmasry and Jyrki Katajainen -- Taolue Chen, Klaus Dräger and Stefan Kiefer. Parameterized Study of the Test Cover Problem / Sitting Closer to Friends Than Enemies, Revisited / A Dichotomy Theorem for Homomorphism Polynomials / Finite State Transducers for Modular Möbius Number Systems / Zero-Knowledge Proofs via Polynomial Representations / Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width / On the Impact of Fair Best Response Dynamics / Fast Balanced Partitioning Is Hard Even on Grids and Trees / A Characterization of Bispecial Sturmian Words / Online Sum-Radii Clustering / Observe and Remain Silent (Communication-Less Agent Location Discovery) / When Trees Grow Low: Shrubs and Fast MSO1 / Strategy Machines and Their Complexity / Coloring Graphs Characterized by a Forbidden Subgraph / Obtaining Planarity by Contracting Few Edges / Light Spanners in Bounded Pathwidth Graphs / Planarizing Gadgets for Perfect Matching Do Not Exist / Kernels for Edge Dominating Set: Simpler or Smaller / Categories of Coalgebraic Games / Quasi-recognizable vs MSO Definable Languages of One-Dimensional Overlapping Tiles / An Improved Approximation Scheme for Variable-Sized Bin Packing / Gathering an Even Number of Robots in an Odd Ring without Global Multiplicity Detection / Reversal Hierarchies for Small 2DFAs / Robert Crowston, Gregory Gutin, Mark Jones, Saket Saurabh and Anders Yeo -- Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk and Jakub Onufry Wojtaszczyk -- Nicolas de Rugy-Altherre -- Martin Delacourt and Petr Kůrka -- Giovanni Di Crescenzo and Vadym Fedyukovych -- Martin Doucha and Jan Kratochvíl -- Angelo Fanelli, Luca Moscardelli and Alexander Skopalik -- Andreas Emil Feldmann -- Gabriele Fici -- Dimitris Fotakis and Paraschos Koutris -- Tom Friedetzky, Leszek Gąsieniec, Thomas Gorry and Russell Martin -- Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek and Patrice Ossona de Mendez, et al. -- Marcus Gelderie -- Petr A. Golovach, Daniël Paulusma and Bernard Ries -- Petr A. Golovach, Pim van 't Hof and Daniël Paulusma -- Michelangelo Grigni and Hao-Hsiang Hung -- Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub and Thomas Thierauf -- Torben Hagerup -- Furio Honsell, Marina Lenisa and Rekha Redamalla -- David Janin -- Klaus Jansen and Stefan Kraft -- Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita and Sébastien Tixeuil -- Christos A. Kapoutsis and Giovanni Pighizzini. (Extended Abstract) / Strictness of the Collapsible Pushdown Hierarchy / Computational Complexity of Smooth Differential Equations / The Lower Reaches of Circuit Uniformity / The Join Levels of the Trotter-Weil Hierarchy Are Decidable / Equations X+A=B and (X+X)+C=(X -- X)+D over Sets of Natural Numbers / Weakly-Synchronized Ground Tree Rewriting (with Applications to Verifying Multithreaded Programs) / Descriptional Complexity of Deterministic Regular Expressions / Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs / Fine and Wilf's Theorem and Pseudo-repetitions / Taking It to the Limit: Approximate Reasoning for Markov Processes / Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games / Between Tree Patterns and Conjunctive Queries: Is There Tractability beyond Acyclicity? / Reducing a Target Interval to a Few Exact Queries / Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs / A Finite Basis for 'Almost Future' Temporal Logic over the Reals / Constructing Premaximal Ternary Square-Free Words of Any Level / Regularity Problems for Weak Pushdown [omega]-Automata and Games / Computational Aspects of Cellular Automata on Countable Sofic Shifts / Computing Lempel-Ziv Factorization Online / On Two Stronger Versions of Dejean's Conjecture / Probabilistic Automata and Probabilistic Logic / A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments / Alexander Kartzow and Paweł Parys -- Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick and Martin Ziegler -- Christoph Behle, Andreas Krebs, Klaus-Jörn Lange and Pierre McKenzie -- Manfred Kufleitner and Alexander Lauser -- Tommi Lehtinen -- Anthony Widjaja Lin -- Katja Losemann, Wim Martens and Matthias Niewerth -- Meena Mahajan, B.V. Raghavendra Rao and Karteek Sreenivasaiah -- Florin Manea, Robert Mercaş and Dirk Nowotka -- Kim Guldstrand Larsen, Radu Mardare and Prakash Panangaden -- Matúš Mihalák and Jan Christoph Schlegel -- Filip Murlak, Michał Ogiński and Marcin Przybyłko -- Jesper Nederlof, Erik Jan van Leeuwen and Ruben van der Zwaan -- Sotiris Nikoletseas, Christoforos Raptopoulos and Paul G. Spirakis -- Dorit Pardo (Ordentlich) and Alexander Rabinovich -- Elena A. Petrova and Arseny M. Shur -- Christof Löding and Stefan Repke -- Ville Salo and Ilkka Törmä -- Tatiana Starikovskaya -- Igor N. Tunev and Arseny M. Shur -- Thomas Weidner -- Mingyu Xiao and Jiong Guo.
This volume constitutes the refereed proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012, held in Bratislava, Slovakia, in August 2012. The 63 revised full papers presented together with 8 invited talks were carefully reviewed and selected from 162 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, databases and knowledge-based systems, foundations of computing, logic in computer science, models of computation, semantics and verification of programs, and theoretical issues in artificial intelligence.
9783642325892 3642325890 3642325882 9783642325885
10.1007/978-3-642-32589-2 doi 9783642325885
9783642325885 00024965
016169308 Uk
Computer science--Mathematics--Congresses.
Computer programming--Congresses.
Computer algorithms--Congresses.
Informatique--Mathématiques--Congrès.
Programmation (Informatique)--Congrès.
Algorithmes--Congrès.
Logiciels.
Informatique.
software.
computer science.
data processing.
Informatique.
Computer algorithms
Computer programming
Computer science--Mathematics
Computer science. Data structures (Computer science) Computational complexity. Algorithm Analysis and Problem Complexity. Discrete Mathematics in Computer Science. Numeric Computing. Mathematical Logic and Formal Languages. Math Applications in Computer Science.
Conference papers and proceedings
Software.
QA76.9.M35 / S96 2012
004.01/51