Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Guillaume Theyssier. FO Logic on Cellular Automata Orbits Equals MSO Logic. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 154:1-154:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{theyssier:LIPIcs.ICALP.2024.154, author = {Theyssier, Guillaume}, title = {{FO Logic on Cellular Automata Orbits Equals MSO Logic}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {154:1--154:20}, 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.154}, URN = {urn:nbn:de:0030-drops-202972}, doi = {10.4230/LIPIcs.ICALP.2024.154}, annote = {Keywords: MSO logic, FO logic, cellular automata, domino problem, Cayley graphs} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Weiß. Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 29:1-29:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bartholdi_et_al:LIPIcs.CCC.2020.29, author = {Bartholdi, Laurent and Figelius, Michael and Lohrey, Markus and Wei{\ss}, Armin}, title = {{Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {29:1--29:29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.29}, URN = {urn:nbn:de:0030-drops-125814}, doi = {10.4230/LIPIcs.CCC.2020.29}, annote = {Keywords: NC^1-hardness, word problem, G-programs, straight-line programs, non-solvable groups, self-similar groups, Thompson’s groups, Grigorchuk’s group} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Markus Lohrey and Armin Weiß. The Power Word Problem. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lohrey_et_al:LIPIcs.MFCS.2019.43, author = {Lohrey, Markus and Wei{\ss}, Armin}, title = {{The Power Word Problem}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {43:1--43: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.43}, URN = {urn:nbn:de:0030-drops-109871}, doi = {10.4230/LIPIcs.MFCS.2019.43}, annote = {Keywords: word problem, compressed word problem, free groups} }
Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Julian Pape-Lange. On Maximal Repeats in Compressed Strings. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{papelange:LIPIcs.CPM.2019.18, author = {Pape-Lange, Julian}, title = {{On Maximal Repeats in Compressed Strings}}, booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)}, pages = {18:1--18:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-103-0}, ISSN = {1868-8969}, year = {2019}, volume = {128}, editor = {Pisanti, Nadia and P. Pissis, Solon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.18}, URN = {urn:nbn:de:0030-drops-104898}, doi = {10.4230/LIPIcs.CPM.2019.18}, annote = {Keywords: Maximal repeats, Combinatorics on compressed strings, LZ77, Compact suffix automata, CDAWGs} }