Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Andrew Ryzhikov and Petra Wolf. Monoids of Upper Triangular Matrices over the Boolean Semiring. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 81:1-81:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ryzhikov_et_al:LIPIcs.MFCS.2024.81, author = {Ryzhikov, Andrew and Wolf, Petra}, title = {{Monoids of Upper Triangular Matrices over the Boolean Semiring}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {81:1--81:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.81}, URN = {urn:nbn:de:0030-drops-206377}, doi = {10.4230/LIPIcs.MFCS.2024.81}, annote = {Keywords: matrix monoids, membership, rank, ergodicity, partially ordered automata} }
Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, and Howard Straubing. An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{krebs_et_al:LIPIcs.CSL.2018.28, author = {Krebs, Andreas and Lodaya, Kamal and Pandya, Paritosh K. and Straubing, Howard}, title = {{An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation}}, booktitle = {27th EACSL Annual Conference on Computer Science Logic (CSL 2018)}, pages = {28:1--28:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-088-0}, ISSN = {1868-8969}, year = {2018}, volume = {119}, editor = {Ghica, Dan R. and Jung, Achim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.28}, URN = {urn:nbn:de:0030-drops-96953}, doi = {10.4230/LIPIcs.CSL.2018.28}, annote = {Keywords: two-variable logic, finite model theory, algebraic automata theory} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Andreas Krebs, Arne Meier, Jonni Virtema, and Martin Zimmermann. Team Semantics for the Specification and Verification of Hyperproperties. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{krebs_et_al:LIPIcs.MFCS.2018.10, author = {Krebs, Andreas and Meier, Arne and Virtema, Jonni and Zimmermann, Martin}, title = {{Team Semantics for the Specification and Verification of Hyperproperties}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {10:1--10: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.10}, URN = {urn:nbn:de:0030-drops-95926}, doi = {10.4230/LIPIcs.MFCS.2018.10}, annote = {Keywords: LTL, Hyperproperties, Team Semantics, Model Checking, Satisfiability} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Andreas Krebs, Nutan Limaye, and Michael Ludwig. A Unified Method for Placing Problems in Polylogarithmic Depth. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{krebs_et_al:LIPIcs.FSTTCS.2017.36, author = {Krebs, Andreas and Limaye, Nutan and Ludwig, Michael}, title = {{A Unified Method for Placing Problems in Polylogarithmic Depth}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {36:1--36:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.36}, URN = {urn:nbn:de:0030-drops-83805}, doi = {10.4230/LIPIcs.FSTTCS.2017.36}, annote = {Keywords: Polylogarithmic depth, Term evaluation, Parallel algorithms} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Eric Allender, Andreas Krebs, and Pierre McKenzie. Better Complexity Bounds for Cost Register Automata. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{allender_et_al:LIPIcs.MFCS.2017.24, author = {Allender, Eric and Krebs, Andreas and McKenzie, Pierre}, title = {{Better Complexity Bounds for Cost Register Automata}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {24:1--24: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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.24}, URN = {urn:nbn:de:0030-drops-80661}, doi = {10.4230/LIPIcs.MFCS.2017.24}, annote = {Keywords: computational complexity, cost registers} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Peter Chini, Jonathan Kolberg, Andreas Krebs, Roland Meyer, and Prakash Saivasan. On the Complexity of Bounded Context Switching. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chini_et_al:LIPIcs.ESA.2017.27, author = {Chini, Peter and Kolberg, Jonathan and Krebs, Andreas and Meyer, Roland and Saivasan, Prakash}, title = {{On the Complexity of Bounded Context Switching}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.27}, URN = {urn:nbn:de:0030-drops-78730}, doi = {10.4230/LIPIcs.ESA.2017.27}, annote = {Keywords: Shared memory concurrency, safety verification, fixed-parameter tractability, exponential time hypothesis, bounded context switching} }
Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Célia Borlido, Silke Czarnetzki, Mai Gehrke, and Andreas Krebs. Stone Duality and the Substitution Principle. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{borlido_et_al:LIPIcs.CSL.2017.13, author = {Borlido, C\'{e}lia and Czarnetzki, Silke and Gehrke, Mai and Krebs, Andreas}, title = {{Stone Duality and the Substitution Principle}}, booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)}, pages = {13:1--13:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-045-3}, ISSN = {1868-8969}, year = {2017}, volume = {82}, editor = {Goranko, Valentin and Dam, Mads}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.13}, URN = {urn:nbn:de:0030-drops-77060}, doi = {10.4230/LIPIcs.CSL.2017.13}, annote = {Keywords: C-variety of languages, typed monoid, Boolean space with an internal monoid, substitution principle, semidirect product} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Andreas Krebs, Klaus-Jörn Lange, and Michael Ludwig. Visibly Counter Languages and Constant Depth Circuits. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 594-607, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{krebs_et_al:LIPIcs.STACS.2015.594, author = {Krebs, Andreas and Lange, Klaus-J\"{o}rn and Ludwig, Michael}, title = {{Visibly Counter Languages and Constant Depth Circuits}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {594--607}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.594}, URN = {urn:nbn:de:0030-drops-49447}, doi = {10.4230/LIPIcs.STACS.2015.594}, annote = {Keywords: visibly counter automata, constant depth circuits, AC0, FO\lbrack+\rbrack} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Andreas Krebs and Nutan Limaye. DLOGTIME Proof Systems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 189-200, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{krebs_et_al:LIPIcs.FSTTCS.2013.189, author = {Krebs, Andreas and Limaye, Nutan}, title = {{DLOGTIME Proof Systems}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {189--200}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.189}, URN = {urn:nbn:de:0030-drops-43725}, doi = {10.4230/LIPIcs.FSTTCS.2013.189}, annote = {Keywords: Proof systems, DLOGTIME, NC0} }
Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)
Christoph Berkholz, Andreas Krebs, and Oleg Verbitsky. Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 61-80, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{berkholz_et_al:LIPIcs.CSL.2013.61, author = {Berkholz, Christoph and Krebs, Andreas and Verbitsky, Oleg}, title = {{Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy}}, booktitle = {Computer Science Logic 2013 (CSL 2013)}, pages = {61--80}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-60-6}, ISSN = {1868-8969}, year = {2013}, volume = {23}, editor = {Ronchi Della Rocca, Simona}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.61}, URN = {urn:nbn:de:0030-drops-41907}, doi = {10.4230/LIPIcs.CSL.2013.61}, annote = {Keywords: Alternation hierarchy, finite-variable logic} }
Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Andreas Krebs and Howard Straubing. An effective characterization of the alternation hierarchy in two-variable logic. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 86-98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{krebs_et_al:LIPIcs.FSTTCS.2012.86, author = {Krebs, Andreas and Straubing, Howard}, title = {{An effective characterization of the alternation hierarchy in two-variable logic}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}, pages = {86--98}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-47-7}, ISSN = {1868-8969}, year = {2012}, volume = {18}, editor = {D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.86}, URN = {urn:nbn:de:0030-drops-38501}, doi = {10.4230/LIPIcs.FSTTCS.2012.86}, annote = {Keywords: FO\underline2, Quantifier Alternation, J, Pseudovarities, Identities} }
Feedback for Dagstuhl Publishing