MFCS 2017 August 21-25, 2017 - Aalborg, Denmark

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)



Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin (Eds.)
ISBN 978-3-95977-046-0, LIPICS Vol. 83 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 39 MB)
Search Publication Server


Authors
  • Abramsky, Samson
  • Adámek, Jiri
  • Agrawal, Akanksha
  • Allender, Eric
  • Anglès d'Auriac, Paul-Elliot
  • Arvind, Vikraman
  • Atig, Mohamed Faouzi
  • Avni, Guy
  • Balaji, Nikhil
  • Bannai, Hideo
  • Barbosa, Rui Soares
  • Barth, Dominik
  • Beck, Moritz
  • Bergougnoux, Benjamin
  • Blanché, Alexandre
  • Bliznets, Ivan
  • Bodlaender, Hans L.
  • Boissonnat, Jean-Daniel
  • Bonamy, Marthe
  • Brânzei, Simina
  • Brunet, Paul
  • Carvalho, Catarina
  • Casel, Katrin
  • Castellan, Simon
  • Cavallari, Filippo
  • Chatterjee, Krishnendu
  • Chen, Haiming
  • Chen, Liang-Ting
  • Clairambault, Pierre
  • Colcombet, Thomas
  • Cosme Llópez, Enric
  • Dück, Stefan
  • D'Angelo, Gianlorenzo
  • Dabrowski, Konrad K.
  • Damaschke, Peter
  • Datta, Rajit
  • Daviaud, Laure
  • Day, Joel D.
  • Deligkas, Argyrios
  • Deng, Xiaotie
  • de Silva, Nadish
  • Dey, Palash
  • Dose, Titus
  • Droste, Manfred
  • Durand, Bruno
  • Dutta, Kunal
  • Dzyga, Michalina
  • Eiben, Eduard
  • Feghali, Carl
  • Feng, Qilong
  • Ferens, Robert
  • Fernau, Henning
  • Filos-Ratsikas, Aris
  • Fomin, Fedor V.
  • Fulla, Peter
  • Ganian, Robert
  • Gao, Yansong
  • Ghani, Neil
  • Ghosh, Arijit
  • Glaßer, Christian
  • Glinskih, Ludmila
  • Golovach, Petr A.
  • Grigoriev, Alexander
  • Grosshans, Nathan
  • Guha, Shibashis
  • Guillon, Pierre
  • Gupta, Sushmita
  • Gusev, Vladimir V.
  • Haase, Christoph
  • Hague, Matthew
  • Hansen, Kristoffer Arnsfelt
  • Hatanaka, Tatsuhiko
  • Hella, Lauri
  • Henzinger, Monika
  • Hermelin, Danny
  • Hirahara, Shuichi
  • Hoffmann, Michael
  • Hsu, Chloe Ching-Yun
  • Ibsen-Jensen, Rasmus
  • Impagliazzo, Russell
  • Inenaga, Shunsuke
  • Ito, Takehiro
  • Itsykson, Dmitry
  • Jacobs, Bart
  • Jeandel, Emmanuel
  • Johnson, Marianne
  • Johnson, Matthew
  • Jonsson, Peter
  • Kabanets, Valentine
  • Kahn, David M.
  • Karpov, Nikolai
  • Kawachi, Akinori
  • Kiefer, Stefan
  • Kieronski, Emanuel
  • Klauck, Hartmut
  • Kolay, Sudeshna
  • Kolokolova, Antonina
  • Krebs, Andreas
  • Krishna, Shankara Narayanan
  • Kupferman, Orna
  • Kuusisto, Antti
  • Laarhoven, Thijs
  • Lagarde, Guillaume
  • Lagerkvist, Victor
  • Lanotte, Ruggero
  • Larsen, Kim G.
  • Li, Shaohua
  • Limaye, Nutan
  • Lohrey, Markus
  • Lozin, Vadim V.
  • Lu, Ping
  • Lutz, Neil
  • Madnani, Khushraj
  • Mahajan, Meena
  • Mandrioli, Dino
  • Manea, Florin
  • Markey, Nicolas
  • Martin, Barnaby
  • McBride, Conor
  • McKenzie, Pierre
  • Meier, Arne
  • Meng, Xiangzhong
  • Merlet, Glenn
  • Merro, Massimo
  • Mertzios, George B.
  • Meyer, Roland
  • Michalewski, Henryk
  • Michler, Larissa
  • Milanic, Martin
  • Milius, Stefan
  • Miltersen, Peter Bro
  • Misra, Neeldhara
  • Monin, Benoit
  • Mukhopadhyay, Partha
  • Mursic, Peter
  • Muskalla, Sebastian
  • Muzi, Irene
  • Myasnikov, Alexei
  • Mydlarz, Marcelo
  • Nestra, Härmel
  • Nichterlein, André
  • Niedermeier, Rolf
  • Nimbhorkar, Prajakta
  • Nishimoto, Takaaki
  • Nordvall Forsberg, Fredrik
  • Nowak, Martin A.
  • Nowotka, Dirk
  • O'Brien, Michael P.
  • Ogihara, Mitsunori
  • Ordyniak, Sebastian
  • Pagh, Rasmus
  • Pandya, Paritosh K.
  • Panolan, Fahad
  • Parker, Austin J.
  • Paul, Erik
  • Paulusma, Daniël
  • Perdrix, Simon
  • Petrisan, Daniela
  • Pilipczuk, Michal
  • Potapov, Igor
  • Pous, Damien
  • Pradella, Matteo
  • Raja, S.
  • Ramanujan, M. S.
  • Raskin, Jean-Francois
  • Reidl, Felix
  • Romani, Shadab
  • Romashchenko, Andrei
  • Roy, Biman
  • Roy, Sanjukta
  • S., Akshay
  • Saivasan, Prakash
  • Saurabh, Saket
  • Schmid, Markus L.
  • Schnoebelen, Philippe
  • Segoufin, Luc
  • Semukhin, Pavel
  • Severini, Lorenzo
  • Skrzypczak, Michal
  • Spahn, Stephan
  • Spirakis, Paul G.
  • Srinivasan, Srikanth
  • Sullivan, Blair D.
  • Svozil, Alexander
  • Szykula, Marek
  • Tóth, Csaba D.
  • Takeda, Masayuki
  • Tanimura, Yuka
  • Tawari, Anuj
  • Technau, Marc
  • Thilikos, Dimitrios M.
  • Tini, Simone
  • Uchizawa, Kei
  • Umans, Chris
  • Urbat, Henning
  • van Leeuwen, Erik Jan
  • Velaj, Yllka
  • Vikas, Narayan
  • Vilmart, Renaud
  • Virtema, Jonni
  • Vyas, Nikhil
  • Wang, Jianxin
  • Wang, Quanlong
  • Weiß, Armin
  • Whitesides, Sue
  • Wiese, Andreas
  • Winskel, Glynn
  • Wu, Zhilin
  • Yamakami, Tomoyuki
  • Yancey, Kelly B.
  • Yancey, Matthew P.
  • Zamaraev, Viktor
  • Zanasi, Fabio
  • Zapata, Octavio
  • Zehavi, Meirav
  • Zeng, Yulong
  • Zhang, Jie
  • Zhou, Xiao
  • Zhuk, Dmitriy
  • Zivny, Stanislav

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Larsen, Kim G. ; Bodlaender, Hans L. ; Raskin, Jean-Francois

    Abstract | Document (358 KB) | BibTeX

    Does Looking Inside a Circuit Help?
    Authors: Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina ; McKenzie, Pierre ; Romani, Shadab

    Abstract | Document (495 KB) | BibTeX

    The Power of Programs over Monoids in DA
    Authors: Grosshans, Nathan ; McKenzie, Pierre ; Segoufin, Luc

    Abstract | Document (541 KB) | BibTeX

    Regular Language Distance and Entropy
    Authors: Parker, Austin J. ; Yancey, Kelly B. ; Yancey, Matthew P.

    Abstract | Document (654 KB) | BibTeX

    The Complexity of Boolean Surjective General-Valued CSPs
    Authors: Fulla, Peter ; Zivny, Stanislav

    Abstract | Document (527 KB) | BibTeX

    On the Expressive Power of Quasiperiodic SFT
    Authors: Durand, Bruno ; Romashchenko, Andrei

    Abstract | Document (482 KB) | BibTeX

    Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
    Authors: Bliznets, Ivan ; Karpov, Nikolai

    Abstract | Document (489 KB) | BibTeX

    Hypercube LSH for Approximate near Neighbors
    Authors: Laarhoven, Thijs

    Abstract | Document (650 KB) | BibTeX

    Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems
    Authors: Kawachi, Akinori ; Ogihara, Mitsunori ; Uchizawa, Kei

    Abstract | Document (461 KB) | BibTeX

    Dividing Splittable Goods Evenly and With Limited Fragmentation
    Authors: Damaschke, Peter

    Abstract | Document (421 KB) | BibTeX

    Small-Space LCE Data Structure with Constant-Time Queries
    Authors: Tanimura, Yuka ; Nishimoto, Takaaki ; Bannai, Hideo ; Inenaga, Shunsuke ; Takeda, Masayuki

    Abstract | Document (703 KB) | BibTeX

    ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T Quantum Mechanics
    Authors: Jeandel, Emmanuel ; Perdrix, Simon ; Vilmart, Renaud ; Wang, Quanlong

    Abstract | Document (572 KB) | BibTeX

    Counting Problems for Parikh Images
    Authors: Haase, Christoph ; Kiefer, Stefan ; Lohrey, Markus

    Abstract | Document (523 KB) | BibTeX

    Communication Complexity of Pairs of Graph Families with Applications
    Authors: Kolay, Sudeshna ; Panolan, Fahad ; Saurabh, Saket

    Abstract | Document (566 KB) | BibTeX

    Monitor Logics for Quantitative Monitor Automata
    Authors: Paul, Erik

    Abstract | Document (484 KB) | BibTeX

    The Complexity of Quantum Disjointness
    Authors: Klauck, Hartmut

    Abstract | Document (432 KB) | BibTeX

    Smoothed and Average-Case Approximation Ratios of Mechanisms: Beyond the Worst-Case Analysis
    Authors: Deng, Xiaotie ; Gao, Yansong ; Zhang, Jie

    Abstract | Document (547 KB) | BibTeX

    Time Complexity of Constraint Satisfaction via Universal Algebra
    Authors: Jonsson, Peter ; Lagerkvist, Victor ; Roy, Biman

    Abstract | Document (578 KB) | BibTeX

    The Hardness of Solving Simple Word Equations
    Authors: Day, Joel D. ; Manea, Florin ; Nowotka, Dirk

    Abstract | Document (640 KB) | BibTeX

    Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices
    Authors: Daviaud, Laure ; Guillon, Pierre ; Merlet, Glenn

    Abstract | Document (530 KB) | BibTeX

    Binary Search in Graphs Revisited
    Authors: Deligkas, Argyrios ; Mertzios, George B. ; Spirakis, Paul G.

    Abstract | Document (468 KB) | BibTeX

    A Formal Semantics of Influence in Bayesian Reasoning
    Authors: Jacobs, Bart ; Zanasi, Fabio

    Abstract | Document (520 KB) | BibTeX

    The Complexity of SORE-definability Problems
    Authors: Lu, Ping ; Wu, Zhilin ; Chen, Haiming

    Abstract | Document (619 KB) | BibTeX

    TC^0 Circuits for Algorithmic Problems in Nilpotent Groups
    Authors: Myasnikov, Alexei ; Weiß, Armin

    Abstract | Document (478 KB) | BibTeX

    Better Complexity Bounds for Cost Register Automata
    Authors: Allender, Eric ; Krebs, Andreas ; McKenzie, Pierre

    Abstract | Document (530 KB) | BibTeX

    Kernelization of the Subset General Position Problem in Geometry
    Authors: Boissonnat, Jean-Daniel ; Dutta, Kunal ; Ghosh, Arijit ; Kolay, Sudeshna

    Abstract | Document (439 KB) | BibTeX

    Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs
    Authors: Glinskih, Ludmila ; Itsykson, Dmitry

    Abstract | Document (465 KB) | BibTeX

    The Complexity of Quantified Constraints Using the Algebraic Formulation
    Authors: Carvalho, Catarina ; Martin, Barnaby ; Zhuk, Dmitriy

    Abstract | Document (478 KB) | BibTeX

    Induced Embeddings into Hamming Graphs
    Authors: Milanic, Martin ; Mursic, Peter ; Mydlarz, Marcelo

    Abstract | Document (523 KB) | BibTeX

    Structured Connectivity Augmentation
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Thilikos, Dimitrios M.

    Abstract | Document (688 KB) | BibTeX

    Combinatorial Properties and Recognition of Unit Square Visibility Graphs
    Authors: Casel, Katrin ; Fernau, Henning ; Grigoriev, Alexander ; Schmid, Markus L. ; Whitesides, Sue

    Abstract | Document (581 KB) | BibTeX

    Weighted Operator Precedence Languages
    Authors: Droste, Manfred ; Dück, Stefan ; Mandrioli, Dino ; Pradella, Matteo

    Abstract | Document (578 KB) | BibTeX

    Model Checking and Validity in Propositional and Modal Inclusion Logics
    Authors: Hella, Lauri ; Kuusisto, Antti ; Meier, Arne ; Virtema, Jonni

    Abstract | Document (509 KB) | BibTeX

    Emptiness Problems for Integer Circuits
    Authors: Barth, Dominik ; Beck, Moritz ; Dose, Titus ; Glaßer, Christian ; Michler, Larissa ; Technau, Marc

    Abstract | Document (499 KB) | BibTeX

    Another Characterization of the Higher K-Trivials
    Authors: Anglès d'Auriac, Paul-Elliot ; Monin, Benoit

    Abstract | Document (499 KB) | BibTeX

    The Quantum Monad on Relational Structures
    Authors: Abramsky, Samson ; Barbosa, Rui Soares ; de Silva, Nadish ; Zapata, Octavio

    Abstract | Document (588 KB) | BibTeX

    Towards a Polynomial Kernel for Directed Feedback Vertex Set
    Authors: Bergougnoux, Benjamin ; Eiben, Eduard ; Ganian, Robert ; Ordyniak, Sebastian ; Ramanujan, M. S.

    Abstract | Document (517 KB) | BibTeX

    Timed Network Games
    Authors: Avni, Guy ; Guha, Shibashis ; Kupferman, Orna

    Abstract | Document (488 KB) | BibTeX

    Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings
    Authors: Arvind, Vikraman ; Datta, Rajit ; Mukhopadhyay, Partha ; Raja, S.

    Abstract | Document (508 KB) | BibTeX

    Faster Algorithms for Mean-Payoff Parity Games
    Authors: Chatterjee, Krishnendu ; Henzinger, Monika ; Svozil, Alexander

    Abstract | Document (596 KB) | BibTeX

    Attainable Values of Reset Thresholds
    Authors: Dzyga, Michalina ; Ferens, Robert ; Gusev, Vladimir V. ; Szykula, Marek

    Abstract | Document (539 KB) | BibTeX

    Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees
    Authors: Lagarde, Guillaume ; Limaye, Nutan ; Srinivasan, Srikanth

    Abstract | Document (563 KB) | BibTeX

    Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
    Authors: Pilipczuk, Michal ; van Leeuwen, Erik Jan ; Wiese, Andreas

    Abstract | Document (581 KB) | BibTeX

    Eilenberg Theorems for Free
    Authors: Urbat, Henning ; Adámek, Jiri ; Chen, Liang-Ting ; Milius, Stefan

    Abstract | Document (584 KB) | BibTeX

    Membership Problem in GL(2, Z) Extended by Singular Matrices
    Authors: Potapov, Igor ; Semukhin, Pavel

    Abstract | Document (501 KB) | BibTeX

    Grammars for Indentation-Sensitive Parsing
    Authors: Nestra, Härmel

    Abstract | Document (509 KB) | BibTeX

    The Power of Linear-Time Data Reduction for Maximum Matching
    Authors: Mertzios, George B. ; Nichterlein, André ; Niedermeier, Rolf

    Abstract | Document (621 KB) | BibTeX

    Two-Planar Graphs Are Quasiplanar
    Authors: Hoffmann, Michael ; Tóth, Csaba D.

    Abstract | Document (806 KB) | BibTeX

    The Shortest Identities for Max-Plus Automata with Two States
    Authors: Daviaud, Laure ; Johnson, Marianne

    Abstract | Document (466 KB) | BibTeX

    On the Upward/Downward Closures of Petri Nets
    Authors: Atig, Mohamed Faouzi ; Meyer, Roland ; Muskalla, Sebastian ; Saivasan, Prakash

    Abstract | Document (528 KB) | BibTeX

    On Multidimensional and Monotone k-SUM
    Authors: Hsu, Chloe Ching-Yun ; Umans, Chris

    Abstract | Document (504 KB) | BibTeX

    Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
    Authors: Hatanaka, Tatsuhiko ; Ito, Takehiro ; Zhou, Xiao

    Abstract | Document (2,671 KB) | BibTeX

    Automata in the Category of Glued Vector Spaces
    Authors: Colcombet, Thomas ; Petrisan, Daniela

    Abstract | Document (604 KB) | BibTeX

    The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable
    Authors: Paul, Erik

    Abstract | Document (526 KB) | BibTeX

    New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
    Authors: Allender, Eric ; Hirahara, Shuichi

    Abstract | Document (555 KB) | BibTeX

    Strategy Complexity of Concurrent Safety Games
    Authors: Chatterjee, Krishnendu ; Hansen, Kristoffer Arnsfelt ; Ibsen-Jensen, Rasmus

    Abstract | Document (537 KB) | BibTeX

    A Characterisation of Pi^0_2 Regular Tree Languages
    Authors: Cavallari, Filippo ; Michalewski, Henryk ; Skrzypczak, Michal

    Abstract | Document (570 KB) | BibTeX

    On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
    Authors: Dey, Palash ; Misra, Neeldhara

    Abstract | Document (556 KB) | BibTeX

    Fractal Intersections and Products via Algorithmic Dimension
    Authors: Lutz, Neil

    Abstract | Document (508 KB) | BibTeX

    Domains for Higher-Order Games
    Authors: Hague, Matthew ; Meyer, Roland ; Muskalla, Sebastian

    Abstract | Document (532 KB) | BibTeX

    Fine-Grained Complexity of Rainbow Coloring and its Variants
    Authors: Agrawal, Akanksha

    Abstract | Document (521 KB) | BibTeX

    Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
    Authors: Chatterjee, Krishnendu ; Ibsen-Jensen, Rasmus ; Nowak, Martin A.

    Abstract | Document (523 KB) | BibTeX

    The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
    Authors: Yamakami, Tomoyuki

    Abstract | Document (488 KB) | BibTeX

    Variations on Inductive-Recursive Definitions
    Authors: Ghani, Neil ; McBride, Conor ; Nordvall Forsberg, Fredrik ; Spahn, Stephan

    Abstract | Document (468 KB) | BibTeX

    One-Dimensional Logic over Trees
    Authors: Kieronski, Emanuel ; Kuusisto, Antti

    Abstract | Document (493 KB) | BibTeX

    An Improved FPT Algorithm for the Flip Distance Problem
    Authors: Li, Shaohua ; Feng, Qilong ; Meng, Xiangzhong ; Wang, Jianxin

    Abstract | Document (557 KB) | BibTeX

    Reversible Kleene lattices
    Authors: Brunet, Paul

    Abstract | Document (591 KB) | BibTeX

    Lossy Kernels for Hitting Subgraphs
    Authors: Eiben, Eduard ; Hermelin, Danny ; Ramanujan, M. S.

    Abstract | Document (565 KB) | BibTeX

    Undecidable Problems for Probabilistic Network Programming
    Authors: Kahn, David M.

    Abstract | Document (502 KB) | BibTeX

    Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
    Authors: Vikas, Narayan

    Abstract | Document (398 KB) | BibTeX

    Recognizing Graphs Close to Bipartite Graphs
    Authors: Bonamy, Marthe ; Dabrowski, Konrad K. ; Feghali, Carl ; Johnson, Matthew ; Paulusma, Daniël

    Abstract | Document (509 KB) | BibTeX

    Parameterized Algorithms and Kernels for Rainbow Matching
    Authors: Gupta, Sushmita ; Roy, Sanjukta ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (572 KB) | BibTeX

    Compositional Weak Metrics for Group Key Update
    Authors: Lanotte, Ruggero ; Merro, Massimo ; Tini, Simone

    Abstract | Document (896 KB) | BibTeX

    Clique-Width for Graph Classes Closed under Complementation
    Authors: Blanché, Alexandre ; Dabrowski, Konrad K. ; Johnson, Matthew ; Lozin, Vadim V. ; Paulusma, Daniël ; Zamaraev, Viktor

    Abstract | Document (533 KB) | BibTeX

    Computing the Maximum using (min, +) Formulas
    Authors: Mahajan, Meena ; Nimbhorkar, Prajakta ; Tawari, Anuj

    Abstract | Document (392 KB) | BibTeX

    Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network
    Authors: D'Angelo, Gianlorenzo ; Severini, Lorenzo ; Velaj, Yllka

    Abstract | Document (586 KB) | BibTeX

    K4-free Graphs as a Free Algebra
    Authors: Cosme Llópez, Enric ; Pous, Damien

    Abstract | Document (501 KB) | BibTeX

    Making Metric Temporal Logic Rational
    Authors: Krishna, Shankara Narayanan ; Madnani, Khushraj ; Pandya, Paritosh K.

    Abstract | Document (690 KB) | BibTeX

    Complexity of Restricted Variants of Skolem and Related Problems
    Authors: S., Akshay ; Balaji, Nikhil ; Vyas, Nikhil

    Abstract | Document (555 KB) | BibTeX

    Being Even Slightly Shallow Makes Life Hard
    Authors: Muzi, Irene ; O'Brien, Michael P. ; Reidl, Felix ; Sullivan, Blair D.

    Abstract | Document (640 KB) | BibTeX

    Walrasian Pricing in Multi-Unit Auctions
    Authors: Brânzei, Simina ; Filos-Ratsikas, Aris ; Miltersen, Peter Bro ; Zeng, Yulong

    Abstract | Document (523 KB) | BibTeX

    Distributed Strategies Made Easy
    Authors: Castellan, Simon ; Clairambault, Pierre ; Winskel, Glynn

    Abstract | Document (488 KB) | BibTeX

    On Definable and Recognizable Properties of Graphs of Bounded Treewidth (Invited Talk)
    Authors: Pilipczuk, Michal

    Abstract | Document (233 KB) | BibTeX

    Hardness and Approximation of High-Dimensional Search Problems (Invited Talk)
    Authors: Pagh, Rasmus

    Abstract | Document (249 KB) | BibTeX

    Temporal Logics for Multi-Agent Systems (Invited Talk)
    Authors: Markey, Nicolas

    Abstract | Document (284 KB) | BibTeX

    Ideal-Based Algorithms for the Symbolic Verification of Well-Structured Systems (Invited Talk)
    Authors: Schnoebelen, Philippe

    Abstract | Document (345 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI