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