Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Michael Benedikt, Dmitry Chistikov, and Alessio Mansutti. The Complexity of Presburger Arithmetic with Power or Powers. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 112:1-112:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{benedikt_et_al:LIPIcs.ICALP.2023.112, author = {Benedikt, Michael and Chistikov, Dmitry and Mansutti, Alessio}, title = {{The Complexity of Presburger Arithmetic with Power or Powers}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {112:1--112:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.112}, URN = {urn:nbn:de:0030-drops-181641}, doi = {10.4230/LIPIcs.ICALP.2023.112}, annote = {Keywords: arithmetic theories, exponentiation, decision procedures} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Dmitry Chistikov, Christoph Haase, Zahra Hadizadeh, and Alessio Mansutti. Higher-Order Quantified Boolean Satisfiability. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 33:1-33:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chistikov_et_al:LIPIcs.MFCS.2022.33, author = {Chistikov, Dmitry and Haase, Christoph and Hadizadeh, Zahra and Mansutti, Alessio}, title = {{Higher-Order Quantified Boolean Satisfiability}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {33:1--33: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.33}, URN = {urn:nbn:de:0030-drops-168313}, doi = {10.4230/LIPIcs.MFCS.2022.33}, annote = {Keywords: Boolean satisfiability problem, higher-order Boolean functions, weak k-EXP hierarchies, non-elementary complexity, Presburger arithmetic} }
Published in: LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021)
A. R. Balasubramanian and K. S. Thejaswini. Adaptive Synchronisation of Pushdown Automata. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 17:1-17:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{balasubramanian_et_al:LIPIcs.CONCUR.2021.17, author = {Balasubramanian, A. R. and Thejaswini, K. S.}, title = {{Adaptive Synchronisation of Pushdown Automata}}, booktitle = {32nd International Conference on Concurrency Theory (CONCUR 2021)}, pages = {17:1--17:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-203-7}, ISSN = {1868-8969}, year = {2021}, volume = {203}, editor = {Haddad, Serge and Varacca, Daniele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.17}, URN = {urn:nbn:de:0030-drops-143948}, doi = {10.4230/LIPIcs.CONCUR.2021.17}, annote = {Keywords: Adaptive synchronisation, Pushdown automata, Alternating pushdown systems} }
Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)
Dmitry Chistikov, Stefan Kiefer, Andrzej S. Murawski, and David Purser. The Big-O Problem for Labelled Markov Chains and Weighted Automata. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 41:1-41:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chistikov_et_al:LIPIcs.CONCUR.2020.41, author = {Chistikov, Dmitry and Kiefer, Stefan and Murawski, Andrzej S. and Purser, David}, title = {{The Big-O Problem for Labelled Markov Chains and Weighted Automata}}, booktitle = {31st International Conference on Concurrency Theory (CONCUR 2020)}, pages = {41:1--41:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-160-3}, ISSN = {1868-8969}, year = {2020}, volume = {171}, editor = {Konnov, Igor and Kov\'{a}cs, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.41}, URN = {urn:nbn:de:0030-drops-128534}, doi = {10.4230/LIPIcs.CONCUR.2020.41}, annote = {Keywords: weighted automata, labelled Markov chains, probabilistic systems} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Michaël Cadilhac, Dmitry Chistikov, and Georg Zetzsche. Rational Subsets of Baumslag-Solitar Groups. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 116:1-116:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{cadilhac_et_al:LIPIcs.ICALP.2020.116, author = {Cadilhac, Micha\"{e}l and Chistikov, Dmitry and Zetzsche, Georg}, title = {{Rational Subsets of Baumslag-Solitar Groups}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {116:1--116:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.116}, URN = {urn:nbn:de:0030-drops-125238}, doi = {10.4230/LIPIcs.ICALP.2020.116}, annote = {Keywords: Rational subsets, Baumslag-Solitar groups, decidability, regular languages, pointed expansion} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Dmitry Chistikov and Christoph Haase. On the Power of Ordering in Linear Arithmetic Theories. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 119:1-119:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chistikov_et_al:LIPIcs.ICALP.2020.119, author = {Chistikov, Dmitry and Haase, Christoph}, title = {{On the Power of Ordering in Linear Arithmetic Theories}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {119:1--119:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.119}, URN = {urn:nbn:de:0030-drops-125265}, doi = {10.4230/LIPIcs.ICALP.2020.119}, annote = {Keywords: logical definability, linear arithmetic theories, semi linear sets, ultimately periodic sets, numerical semigroups} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Laure Daviaud, Marcin Jurdziński, and K. S. Thejaswini. The Strahler Number of a Parity Game. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 123:1-123:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{daviaud_et_al:LIPIcs.ICALP.2020.123, author = {Daviaud, Laure and Jurdzi\'{n}ski, Marcin and Thejaswini, K. S.}, title = {{The Strahler Number of a Parity Game}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {123:1--123:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.123}, URN = {urn:nbn:de:0030-drops-125304}, doi = {10.4230/LIPIcs.ICALP.2020.123}, annote = {Keywords: parity game, attractor decomposition, progress measure, universal tree, Strahler number} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Dmitry Chistikov, Andrzej S. Murawski, and David Purser. Asymmetric Distances for Approximate Differential Privacy. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 10:1-10:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{chistikov_et_al:LIPIcs.CONCUR.2019.10, author = {Chistikov, Dmitry and Murawski, Andrzej S. and Purser, David}, title = {{Asymmetric Distances for Approximate Differential Privacy}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {10:1--10: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.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.10}, URN = {urn:nbn:de:0030-drops-109121}, doi = {10.4230/LIPIcs.CONCUR.2019.10}, annote = {Keywords: Bisimilarity distances, Differential privacy, Labelled Markov chains} }
Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Rupak Majumdar. Random Testing for Distributed Systems with Theoretical Guarantees (Invited Paper). In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{majumdar:LIPIcs.FSTTCS.2018.1, author = {Majumdar, Rupak}, title = {{Random Testing for Distributed Systems with Theoretical Guarantees}}, booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-093-4}, ISSN = {1868-8969}, year = {2018}, volume = {122}, editor = {Ganguly, Sumit and Pandya, Paritosh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.1}, URN = {urn:nbn:de:0030-drops-99000}, doi = {10.4230/LIPIcs.FSTTCS.2018.1}, annote = {Keywords: Random testing, Hitting families} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Shaull Almagor, Dmitry Chistikov, Joël Ouaknine, and James Worrell. O-Minimal Invariants for Linear Loops. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 114:1-114:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{almagor_et_al:LIPIcs.ICALP.2018.114, author = {Almagor, Shaull and Chistikov, Dmitry and Ouaknine, Jo\"{e}l and Worrell, James}, title = {{O-Minimal Invariants for Linear Loops}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {114:1--114:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.114}, URN = {urn:nbn:de:0030-drops-91188}, doi = {10.4230/LIPIcs.ICALP.2018.114}, annote = {Keywords: Invariants, linear loops, linear dynamical systems, non-termination, o-minimality} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Dmitry Chistikov and Christoph Haase. On the Complexity of Quantified Integer Programming. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 94:1-94:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{chistikov_et_al:LIPIcs.ICALP.2017.94, author = {Chistikov, Dmitry and Haase, Christoph}, title = {{On the Complexity of Quantified Integer Programming}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {94:1--94:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.94}, URN = {urn:nbn:de:0030-drops-75024}, doi = {10.4230/LIPIcs.ICALP.2017.94}, annote = {Keywords: integer programming, semi-linear sets, Presburger arithmetic, quantifier elimination} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Dmitry Chistikov, Szabolcs Iván, Anna Lubiw, and Jeffrey Shallit. Fractional Coverings, Greedy Coverings, and Rectifier Networks. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 23:1-23:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{chistikov_et_al:LIPIcs.STACS.2017.23, author = {Chistikov, Dmitry and Iv\'{a}n, Szabolcs and Lubiw, Anna and Shallit, Jeffrey}, title = {{Fractional Coverings, Greedy Coverings, and Rectifier Networks}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {23:1--23:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.23}, URN = {urn:nbn:de:0030-drops-70107}, doi = {10.4230/LIPIcs.STACS.2017.23}, annote = {Keywords: rectifier network, OR-circuit, biclique covering, fractional covering, greedy covering} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, and James Worrell. On Restricted Nonnegative Matrix Factorization. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 103:1-103:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{chistikov_et_al:LIPIcs.ICALP.2016.103, author = {Chistikov, Dmitry and Kiefer, Stefan and Marusic, Ines and Shirmohammadi, Mahsa and Worrell, James}, title = {{On Restricted Nonnegative Matrix Factorization}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {103:1--103:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.103}, URN = {urn:nbn:de:0030-drops-62389}, doi = {10.4230/LIPIcs.ICALP.2016.103}, annote = {Keywords: nonnegative matrix factorization, nonnegative rank, probabilistic automata, labelled Markov chains, minimization} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Dmitry Chistikov and Christoph Haase. The Taming of the Semi-Linear Set. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 128:1-128:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{chistikov_et_al:LIPIcs.ICALP.2016.128, author = {Chistikov, Dmitry and Haase, Christoph}, title = {{The Taming of the Semi-Linear Set}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {128:1--128:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.128}, URN = {urn:nbn:de:0030-drops-62636}, doi = {10.4230/LIPIcs.ICALP.2016.128}, annote = {Keywords: semi-linear sets, convex polyhedra, triangulations, integer linear programming, commutative grammars} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Dmitry Chistikov. Notes on Counting with Finite Machines. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 339-350, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{chistikov:LIPIcs.FSTTCS.2014.339, author = {Chistikov, Dmitry}, title = {{Notes on Counting with Finite Machines}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {339--350}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.339}, URN = {urn:nbn:de:0030-drops-48547}, doi = {10.4230/LIPIcs.FSTTCS.2014.339}, annote = {Keywords: State complexity, Unary languages, Counting} }
Feedback for Dagstuhl Publishing