default search action
46th MFCS 2021: Tallinn, Estonia
- Filippo Bonchi
, Simon J. Puglisi
46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia. LIPIcs 202, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2021, ISBN 978-3-95977-201-3 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:16
- Amina Doumane:
Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk). 1:1-1:1 - Martin Grohe:
A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk). 2:1-2:1 - Joël Ouaknine:
Holonomic Techniques, Periods, and Decision Problems (Invited Talk). 3:1-3:1 - Eva Rotenberg
On Dynamic Graphs (Invited Talk). 4:1-4:1 - Barna Saha:
Sublinear Algorithms for Edit Distance (Invited Talk). 5:1-5:1 - Mahmoud Abo Khamis
An Approximation Algorithm for the Matrix Tree Multiplication Problem. 6:1-6:14 - Eric Allender, Archit Chauhan, Samir Datta
Depth-First Search in Directed Planar Graphs, Revisited. 7:1-7:22 - Emmanuel Arrighi, Henning Fernau
Order Reconfiguration Under Width Constraints. 8:1-8:15 - Pablo Arrighi, Marin Costes, Nathanaël Eon:
Universal Gauge-Invariant Cellular Automata. 9:1-9:14 - Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay:
Equivalence Testing of Weighted Automata over Partially Commutative Monoids. 10:1-10:15 - Kristina Asimi, Libor Barto
Finitely Tractable Promise Constraint Satisfaction Problems. 11:1-11:16 - David Auger, Xavier Badin de Montjoye, Yann Strozecki:
A Generic Strategy Improvement Method for Simple Stochastic Games. 12:1-12:22 - Paolo Baldan, Alberto Carraro
(Un)Decidability for History Preserving True Concurrent Logics. 13:1-13:16 - Sayan Bandyapadhyay, Fedor V. Fomin
Parameterized Complexity of Feature Selection for Categorical Data Clustering. 14:1-14:14 - Paul C. Bell
Decision Questions for Probabilistic Automata on Small Alphabets. 15:1-15:17 - Arpitha P. Bharathi, Monaldo Mastrolilli:
Ideal Membership Problem for Boolean Minority and Dual Discriminator. 16:1-16:20 - Siddharth Bhaskar
Graph Traversals as Universal Constructions. 17:1-17:20 - Davide Bilò, Sarel Cohen, Tobias Friedrich, Martin Schirneck
Space-Efficient Fault-Tolerant Diameter Oracles. 18:1-18:16 - Achim Blumensath, Jakub Lédl:
ω-Forest Algebras and Temporal Logics. 19:1-19:21 - León Bohn, Christof Löding:
Constructing Deterministic ω-Automata from Examples by an Extension of the RPNI Algorithm. 20:1-20:18 - Jan Bok
Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases. 21:1-21:15 - Cyril Branciard, Alexandre Clément
Coherent Control and Distinguishability of Quantum Channels via PBS-Diagrams. 22:1-22:20 - Marcin Brianski
Reconfiguring Independent Sets on Interval Graphs. 23:1-23:14 - Florian Bruse, Marco Sälzer, Martin Lange:
Finite Convergence of μ-Calculus Fixpoints on Genuinely Infinite Structures. 24:1-24:19 - Kevin Buchin
Dots & Boxes Is PSPACE-Complete. 25:1-25:18 - Kevin Buchin, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen:
Uncertain Curve Simplification. 26:1-26:22 - Silvia Butti, Víctor Dalmau:
Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem. 27:1-27:19 - Arnaldo Cesco
A Decidable Equivalence for a Turing-Complete, Distributed Model of Computation. 28:1-28:18 - Brynmor Chapman, R. Ryan Williams
Black-Box Hypotheses and Lower Bounds. 29:1-29:22 - Kostia Chardonnet, Benoît Valiron
Geometry of Interaction for ZX-Diagrams. 30:1-30:16 - Siddhesh Chaubal, Anna Gál:
Diameter Versus Certificate Complexity of Boolean Functions. 31:1-31:22 - Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, R. Vijayaragunathan:
Budgeted Dominating Sets in Uncertain Graphs. 32:1-32:22 - Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, James Worrell:
On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets. 33:1-33:21 - Julian D'Costa, Toghrul Karimov
The Pseudo-Skolem Problem is Decidable. 34:1-34:21 - Ugo Dal Lago, Reinhard Kahle
A Recursion-Theoretic Characterization of the Probabilistic Class PP. 35:1-35:12 - Samir Datta
Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles. 36:1-36:22 - Anuj Dawar
On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism. 37:1-37:16 - Celina M. H. de Figueiredo, Alexsander Andrade de Melo, Fabiano de S. Oliveira, Ana Silva
Maximum Cut on Interval Graphs of Interval Count Four Is NP-Complete. 38:1-38:15 - Max A. Deppert, Klaus Jansen, Kim-Manuel Klein:
Fuzzy Simultaneous Congruences. 39:1-39:16 - Gaëtan Douéneau-Tabot:
Pebble Transducers with Unary Output. 40:1-40:17 - Amina Doumane:
Graph Characterization of the Universal Theory of Relations. 41:1-41:15 - Gabriel L. Duarte, Mateus de Oliveira Oliveira, Uéverton S. Souza
Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances. 42:1-42:17 - Guillaume Ducoffe:
Isometric Embeddings in Trees and Their Use in Distance Problems. 43:1-43:16 - Guillaume Ducoffe:
On Computing the Average Distance for Some Chordal-Like Graphs. 44:1-44:16 - Maël Dumas, Anthony Perez, Ioan Todinca:
A Cubic Vertex-Kernel for Trivially Perfect Editing. 45:1-45:14 - Robert Ferens
Lower Bounds on Avoiding Thresholds. 46:1-46:14 - Marie Fortin, Louwe B. Kuijer, Patrick Totzke
HyperLTL Satisfiability Is Σ₁¹-Complete, HyperCTL* Satisfiability Is Σ₁²-Complete. 47:1-47:19 - Pawel Gawrychowski
Matching Patterns with Variables Under Hamming Distance. 48:1-48:24 - Yoan Géran
Keyboards as a New Model of Computation. 49:1-49:20 - Adam Glos
Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs. 50:1-50:23 - Nathan Grosshans:
A Note on the Join of Varieties of Monoids with LI. 51:1-51:16 - Hermann Gruber
Optimal Regular Expressions for Palindromes of Given Length. 52:1-52:15 - Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, Martin Zimmermann
A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct. 53:1-53:20 - Gregory Z. Gutin, Anders Yeo
Perfect Forests in Graphs and Their Extensions. 54:1-54:13 - Christoph Haase, Alessio Mansutti
On Deciding Linear Arithmetic Constraints Over p-adic Integers for All Primes. 55:1-55:20 - Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jérôme Urhausen, Kevin Verbeek
Obstructing Classification via Projection. 56:1-56:19 - Hovhannes A. Harutyunyan, Denis Pankratov, Jesse Racicot:
Online Domination: The Value of Getting to Know All Your Neighbors. 57:1-57:21 - Daniel Hausmann
A Linear-Time Nominal μ-Calculus with Name Allocation. 58:1-58:18 - Shuichi Hirahara, François Le Gall:
Test of Quantumness with Small-Depth Quantum Circuits. 59:1-59:15 - Pavel Hubácek
On Search Complexity of Discrete Logarithm. 60:1-60:16 - Mirai Ikebuchi:
A Homological Condition on Equational Unifiability. 61:1-61:16 - Reijo Jaakkola
Ordered Fragments of First-Order Logic. 62:1-62:14 - Petr Jancar
The Simplest Non-Regular Deterministic Context-Free Language. 63:1-63:18 - Bart M. P. Jansen, Shivesh Kumar Roy, Michal Wlodarczyk:
On the Hardness of Compressing Weights. 64:1-64:21 - Vít Jelínek
Griddings of Permutations and Hardness of Pattern Matching. 65:1-65:22 - Michael Kaminski, Igor E. Shparlinski:
Sets of Linear Forms Which Are Hard to Compute. 66:1-66:22 - George Kenison
On Positivity and Minimality for Second-Order Holonomic Sequences. 67:1-67:15 - Bohdan Kivva
Improved Upper Bounds for the Rigidity of Kronecker Products. 68:1-68:18 - Hartmut Klauck, Debbie Lim:
The Power of One Clean Qubit in Communication Complexity. 69:1-69:23 - Nicolai Kraus
Connecting Constructive Notions of Ordinals in Homotopy Type Theory. 70:1-70:16 - Fu Li, Xiong Zheng:
Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network. 71:1-71:16 - Sven Linker
Finite Models for a Spatial Logic with Discrete and Topological Path Operators. 72:1-72:16 - Nikolas Mählmann, Sebastian Siebertz, Alexandre Vigny:
Recursive Backdoors for SAT. 73:1-73:18 - Caroline Mattes, Armin Weiß
Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group. 74:1-74:24 - George B. Mertzios, Hendrik Molter, Malte Renken
The Complexity of Transitively Orienting Temporal Graphs. 75:1-75:18 - Hendrik Molter, Malte Renken
Temporal Reachability Minimization: Delaying vs. Deleting. 76:1-76:15 - Nils Morawietz
A Timecop's Chase Around the Table. 77:1-77:18 - Robert S. R. Myers, Henning Urbat:
Syntactic Minimization Of Nondeterministic Finite Automata. 78:1-78:16 - Keisuke Nakano:
Idempotent Turing Machines. 79:1-79:18 - Satyadev Nandakumar, Subin Pulari:
Ergodic Theorems and Converses for PSPACE Functions. 80:1-80:19 - Damian Niwinski, Michal Skrzypczak:
On Guidable Index of Tree Automata. 81:1-81:14 - Giacomo Paesani
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs. 82:1-82:14 - Pál András Papp, Roger Wattenhofer:
Stabilization Bounds for Influence Propagation from a Random Initial State. 83:1-83:15 - Norbert Peyerimhoff, Marc Roth
Parameterized (Modular) Counting and Cayley Graph Expanders. 84:1-84:15 - Bader Abu Radi, Orna Kupferman, Ofer Leshkowitz:
A Hierarchy of Nondeterminism. 85:1-85:21 - Hellis Tamm
Boolean Automata and Atoms of Regular Languages. 86:1-86:13 - Davide Trotta
The Gödel Fibration. 87:1-87:16 - Stelios Tsampas
Abstract Congruence Criteria for Weak Bisimilarity. 88:1-88:23 - Renaud Vilmart:
Quantum Multiple-Valued Decision Diagrams in Graphical Calculi. 89:1-89:15 - Sarah Winter:
Decision Problems for Origin-Close Top-Down Tree Transducers. 90:1-90:16
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-08 01:36 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: