LIPIcs, Volume 117
MFCS 2018, August 27-31, 2018, Liverpool, GB
Editors: Igor Potapov, Paul Spirakis, and James Worrell
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Amina Doumane, Samuel Humeau, and Damien Pous. A Finite Presentation of Graphs of Treewidth at Most Three. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 135:1-135:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{doumane_et_al:LIPIcs.ICALP.2024.135, author = {Doumane, Amina and Humeau, Samuel and Pous, Damien}, title = {{A Finite Presentation of Graphs of Treewidth at Most Three}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {135:1--135:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.135}, URN = {urn:nbn:de:0030-drops-202787}, doi = {10.4230/LIPIcs.ICALP.2024.135}, annote = {Keywords: Graphs, treewidth, connectedness, axiomatisation, series-parallel expressions} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yuxi Fu, Qizhe Yang, and Yangluo Zheng. Improved Algorithm for Reachability in d-VASS. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 136:1-136:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fu_et_al:LIPIcs.ICALP.2024.136, author = {Fu, Yuxi and Yang, Qizhe and Zheng, Yangluo}, title = {{Improved Algorithm for Reachability in d-VASS}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {136:1--136:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.136}, URN = {urn:nbn:de:0030-drops-202799}, doi = {10.4230/LIPIcs.ICALP.2024.136}, annote = {Keywords: Petri net, vector addition system, reachability} }
Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
Duncan Adamson, Nathan Flaherty, Igor Potapov, and Paul G. Spirakis. Brief Announcement: Collision-Free Robot Scheduling. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 22:1-22:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{adamson_et_al:LIPIcs.SAND.2024.22, author = {Adamson, Duncan and Flaherty, Nathan and Potapov, Igor and Spirakis, Paul G.}, title = {{Brief Announcement: Collision-Free Robot Scheduling}}, booktitle = {3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, pages = {22:1--22:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-315-7}, ISSN = {1868-8969}, year = {2024}, volume = {292}, editor = {Casteigts, Arnaud and Kuhn, Fabian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.22}, URN = {urn:nbn:de:0030-drops-199004}, doi = {10.4230/LIPIcs.SAND.2024.22}, annote = {Keywords: Graph Exploration, Scheduling, NP-Completeness, Approximation Algorithms} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, and Igor Potapov. The Complexity of Periodic Energy Minimisation. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{adamson_et_al:LIPIcs.MFCS.2022.8, author = {Adamson, Duncan and Deligkas, Argyrios and Gusev, Vladimir V. and Potapov, Igor}, title = {{The Complexity of Periodic Energy Minimisation}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {8:1--8:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.8}, URN = {urn:nbn:de:0030-drops-168065}, doi = {10.4230/LIPIcs.MFCS.2022.8}, annote = {Keywords: Optimisation of periodic structures, tiling, undecidability, NP-hardness} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Duncan Adamson, Vladimir V. Gusev, Igor Potapov, and Argyrios Deligkas. Ranking Bracelets in Polynomial Time. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{adamson_et_al:LIPIcs.CPM.2021.4, author = {Adamson, Duncan and Gusev, Vladimir V. and Potapov, Igor and Deligkas, Argyrios}, title = {{Ranking Bracelets in Polynomial Time}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {4:1--4:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.4}, URN = {urn:nbn:de:0030-drops-139554}, doi = {10.4230/LIPIcs.CPM.2021.4}, annote = {Keywords: Bracelets, Ranking, Necklaces} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Paul C. Bell, Igor Potapov, and Pavel Semukhin. On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 83:1-83:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bell_et_al:LIPIcs.MFCS.2019.83, author = {Bell, Paul C. and Potapov, Igor and Semukhin, Pavel}, title = {{On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {83:1--83:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.83}, URN = {urn:nbn:de:0030-drops-110279}, doi = {10.4230/LIPIcs.MFCS.2019.83}, annote = {Keywords: Linear recurrence sequences, Skolem’s problem, mortality problem, matrix equations, primary decomposition theorem, Baker’s theorem} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@Proceedings{potapov_et_al:LIPIcs.MFCS.2018, title = {{LIPIcs, Volume 117, MFCS'18, Complete Volume}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018}, URN = {urn:nbn:de:0030-drops-97459}, doi = {10.4230/LIPIcs.MFCS.2018}, annote = {Keywords: Theory of computation} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{potapov_et_al:LIPIcs.MFCS.2018.0, author = {Potapov, Igor and Spirakis, Paul and Worrell, James}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {0:i--0:xx}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.0}, URN = {urn:nbn:de:0030-drops-95824}, doi = {10.4230/LIPIcs.MFCS.2018.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Laurent Bulteau and Markus L. Schmid. Consensus Strings with Small Maximum Distance and Small Distance Sum. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bulteau_et_al:LIPIcs.MFCS.2018.1, author = {Bulteau, Laurent and Schmid, Markus L.}, title = {{Consensus Strings with Small Maximum Distance and Small Distance Sum}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {1:1--1:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.1}, URN = {urn:nbn:de:0030-drops-95834}, doi = {10.4230/LIPIcs.MFCS.2018.1}, annote = {Keywords: Consensus String Problems, Closest String, Closest Substring, Parameterised Complexity, Kernelisation} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Mikhail Andreev, Gleb Posobin, and Alexander Shen. Plain Stopping Time and Conditional Complexities Revisited. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{andreev_et_al:LIPIcs.MFCS.2018.2, author = {Andreev, Mikhail and Posobin, Gleb and Shen, Alexander}, title = {{Plain Stopping Time and Conditional Complexities Revisited}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {2:1--2:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.2}, URN = {urn:nbn:de:0030-drops-95842}, doi = {10.4230/LIPIcs.MFCS.2018.2}, annote = {Keywords: Kolmogorov complexity, stopping time complexity, structured conditional complexity, algorithmic information theory} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Hasan Abasi. Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{abasi:LIPIcs.MFCS.2018.3, author = {Abasi, Hasan}, title = {{Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.3}, URN = {urn:nbn:de:0030-drops-95854}, doi = {10.4230/LIPIcs.MFCS.2018.3}, annote = {Keywords: Error Tolerant Algorithm, Hidden Hypergraph, Montone DNF, Group Testing, Non-Adaptive Learning} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Alexander Kozachinskiy. From Expanders to Hitting Distributions and Simulation Theorems. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{kozachinskiy:LIPIcs.MFCS.2018.4, author = {Kozachinskiy, Alexander}, title = {{From Expanders to Hitting Distributions and Simulation Theorems}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {4:1--4:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.4}, URN = {urn:nbn:de:0030-drops-95863}, doi = {10.4230/LIPIcs.MFCS.2018.4}, annote = {Keywords: simulation theorems, hitting distributions, expanders} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Titus Dose. Balance Problems for Integer Circuits. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dose:LIPIcs.MFCS.2018.5, author = {Dose, Titus}, title = {{Balance Problems for Integer Circuits}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {5:1--5:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.5}, URN = {urn:nbn:de:0030-drops-95874}, doi = {10.4230/LIPIcs.MFCS.2018.5}, annote = {Keywords: computational complexity, integer expressions, integer circuits} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Louis-Marie Dando and Sylvain Lombardy. On Hadamard Series and Rotating Q-Automata. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dando_et_al:LIPIcs.MFCS.2018.6, author = {Dando, Louis-Marie and Lombardy, Sylvain}, title = {{On Hadamard Series and Rotating Q-Automata}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {6:1--6:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.6}, URN = {urn:nbn:de:0030-drops-95881}, doi = {10.4230/LIPIcs.MFCS.2018.6}, annote = {Keywords: Rational series, Hadamard operations, Rotating automata, Two-way automata} }