LIPIcs, Volume 83
MFCS 2017, August 21-25, 2017, Aalborg, Denmark
Editors: Kim G. Larsen, Hans L. Bodlaender, and Jean-Francois Raskin
Published in: LITES, Volume 8, Issue 2 (2022): Special Issue on Distributed Hybrid Systems. Leibniz Transactions on Embedded Systems, Volume 8, Issue 2
LITES, Volume 8, Issue 2: Special Issue on Distributed Hybrid Systems, pp. 0:i-0:iii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{abate_et_al:LITES.8.2.0, author = {Abate, Alessandro and Fahrenberg, Uli and Fr\"{a}nzle, Martin}, title = {{Introduction to the Special Issue on Distributed Hybrid Systems}}, journal = {Leibniz Transactions on Embedded Systems}, pages = {00:1--00:3}, ISSN = {2199-2002}, year = {2022}, volume = {8}, number = {2}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LITES.8.2.0}, doi = {10.4230/LITES.8.2.0}, annote = {Keywords: Distributed hybrid systems} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Kim G. Larsen. Synthesis of Safe, Optimal and Compact Strategies for Stochastic Hybrid Games (Invited Paper). In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 2:1-2:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{larsen:LIPIcs.CONCUR.2019.2, author = {Larsen, Kim G.}, title = {{Synthesis of Safe, Optimal and Compact Strategies for Stochastic Hybrid Games}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {2:1--2:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-121-4}, ISSN = {1868-8969}, year = {2019}, volume = {140}, editor = {Fokkink, Wan and van Glabbeek, Rob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.2}, URN = {urn:nbn:de:0030-drops-109048}, doi = {10.4230/LIPIcs.CONCUR.2019.2}, annote = {Keywords: Timed automata, Stochastic hybrid grame, Symbolic synthesis, Reinforcement learning, Q-learning, M-learning} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Radu Mardare, Qiyi Tang, and Franck van Breugel. Computing Probabilistic Bisimilarity Distances for Probabilistic Automata. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bacci_et_al:LIPIcs.CONCUR.2019.9, author = {Bacci, Giorgio and Bacci, Giovanni and Larsen, Kim G. and Mardare, Radu and Tang, Qiyi and van Breugel, Franck}, title = {{Computing Probabilistic Bisimilarity Distances for Probabilistic Automata}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-121-4}, ISSN = {1868-8969}, year = {2019}, volume = {140}, editor = {Fokkink, Wan and van Glabbeek, Rob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.9}, URN = {urn:nbn:de:0030-drops-109119}, doi = {10.4230/LIPIcs.CONCUR.2019.9}, annote = {Keywords: Probabilistic automata, Behavioural metrics, Simple stochastic games, Simple policy iteration algorithm} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Frederik Meyer Bønneland, Peter Gjøl Jensen, Kim G. Larsen, Marco Muñiz, and Jiří Srba. Partial Order Reduction for Reachability Games. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bnneland_et_al:LIPIcs.CONCUR.2019.23, author = {B{\o}nneland, Frederik Meyer and Jensen, Peter Gj{\o}l and Larsen, Kim G. and Mu\~{n}iz, Marco and Srba, Ji\v{r}{\'\i}}, title = {{Partial Order Reduction for Reachability Games}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {23:1--23:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-121-4}, ISSN = {1868-8969}, year = {2019}, volume = {140}, editor = {Fokkink, Wan and van Glabbeek, Rob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.23}, URN = {urn:nbn:de:0030-drops-109251}, doi = {10.4230/LIPIcs.CONCUR.2019.23}, annote = {Keywords: Petri nets, games, synthesis, partial order reduction, stubborn sets} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Proceedings{larsen_et_al:LIPIcs.MFCS.2017, title = {{LIPIcs, Volume 83, MFCS'17, Complete Volume}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017}, URN = {urn:nbn:de:0030-drops-82073}, doi = {10.4230/LIPIcs.MFCS.2017}, annote = {Keywords: Theory of Computation} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{larsen_et_al:LIPIcs.MFCS.2017.0, author = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.0}, URN = {urn:nbn:de:0030-drops-80564}, doi = {10.4230/LIPIcs.MFCS.2017.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, and Shadab Romani. Does Looking Inside a Circuit Help?. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{impagliazzo_et_al:LIPIcs.MFCS.2017.1, author = {Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina and McKenzie, Pierre and Romani, Shadab}, title = {{Does Looking Inside a Circuit Help?}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {1:1--1:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.1}, URN = {urn:nbn:de:0030-drops-80975}, doi = {10.4230/LIPIcs.MFCS.2017.1}, annote = {Keywords: Black-Box Hypothesis, Rice's theorem, circuit complexity, SAT, sensitivity of boolean functions, decision tree complexity} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. The Power of Programs over Monoids in DA. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{grosshans_et_al:LIPIcs.MFCS.2017.2, author = {Grosshans, Nathan and McKenzie, Pierre and Segoufin, Luc}, title = {{The Power of Programs over Monoids in DA}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {2:1--2:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.2}, URN = {urn:nbn:de:0030-drops-80909}, doi = {10.4230/LIPIcs.MFCS.2017.2}, annote = {Keywords: Programs over monoids, DA, lower-bounds} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Austin J. Parker, Kelly B. Yancey, and Matthew P. Yancey. Regular Language Distance and Entropy. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{parker_et_al:LIPIcs.MFCS.2017.3, author = {Parker, Austin J. and Yancey, Kelly B. and Yancey, Matthew P.}, title = {{Regular Language Distance and Entropy}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {3:1--3:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.3}, URN = {urn:nbn:de:0030-drops-80945}, doi = {10.4230/LIPIcs.MFCS.2017.3}, annote = {Keywords: regular languages, channel capacity, entropy, Jaccard, symbolic dynamics} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Peter Fulla and Stanislav Zivny. The Complexity of Boolean Surjective General-Valued CSPs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{fulla_et_al:LIPIcs.MFCS.2017.4, author = {Fulla, Peter and Zivny, Stanislav}, title = {{The Complexity of Boolean Surjective General-Valued CSPs}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.4}, URN = {urn:nbn:de:0030-drops-80623}, doi = {10.4230/LIPIcs.MFCS.2017.4}, annote = {Keywords: constraint satisfaction problems, surjective CSP, valued CSP, min-cut, polymorphisms, multimorphisms} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Bruno Durand and Andrei Romashchenko. On the Expressive Power of Quasiperiodic SFT. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{durand_et_al:LIPIcs.MFCS.2017.5, author = {Durand, Bruno and Romashchenko, Andrei}, title = {{On the Expressive Power of Quasiperiodic SFT}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {5:1--5:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.5}, URN = {urn:nbn:de:0030-drops-80985}, doi = {10.4230/LIPIcs.MFCS.2017.5}, annote = {Keywords: minimal SFT, tilings, quasiperiodicityIn this paper we study the shifts, which are the shift-invariant and topologically closed sets of configurations} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Ivan Bliznets and Nikolai Karpov. Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bliznets_et_al:LIPIcs.MFCS.2017.6, author = {Bliznets, Ivan and Karpov, Nikolai}, title = {{Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {6:1--6:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.6}, URN = {urn:nbn:de:0030-drops-80728}, doi = {10.4230/LIPIcs.MFCS.2017.6}, annote = {Keywords: clustering, parameterized complexity, highly connected} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Thijs Laarhoven. Hypercube LSH for Approximate near Neighbors. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{laarhoven:LIPIcs.MFCS.2017.7, author = {Laarhoven, Thijs}, title = {{Hypercube LSH for Approximate near Neighbors}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {7:1--7:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.7}, URN = {urn:nbn:de:0030-drops-80926}, doi = {10.4230/LIPIcs.MFCS.2017.7}, annote = {Keywords: (approximate) near neighbors, locality-sensitive hashing, large deviations, dimensionality reduction, lattice algorithms} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Akinori Kawachi, Mitsunori Ogihara, and Kei Uchizawa. Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{kawachi_et_al:LIPIcs.MFCS.2017.8, author = {Kawachi, Akinori and Ogihara, Mitsunori and Uchizawa, Kei}, title = {{Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {8:1--8:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.8}, URN = {urn:nbn:de:0030-drops-81078}, doi = {10.4230/LIPIcs.MFCS.2017.8}, annote = {Keywords: Computational complexity, dynamical systems, Garden of Eden, predecessor} }
Feedback for Dagstuhl Publishing