Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Joel D. Day, Maria Kosche, Florin Manea, and Markus L. Schmid. Subsequences with Gap Constraints: Complexity Bounds for Matching and Analysis Problems. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{day_et_al:LIPIcs.ISAAC.2022.64, author = {Day, Joel D. and Kosche, Maria and Manea, Florin and Schmid, Markus L.}, title = {{Subsequences with Gap Constraints: Complexity Bounds for Matching and Analysis Problems}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {64:1--64:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.64}, URN = {urn:nbn:de:0030-drops-173493}, doi = {10.4230/LIPIcs.ISAAC.2022.64}, annote = {Keywords: String algorithms, subsequences with gap constraints, pattern matching, fine-grained complexity, conditional lower bounds, parameterised complexity} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Dominik D. Freydenberger and Liat Peterfreund. The Theory of Concatenation over Finite Models. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 130:1-130:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{freydenberger_et_al:LIPIcs.ICALP.2021.130, author = {Freydenberger, Dominik D. and Peterfreund, Liat}, title = {{The Theory of Concatenation over Finite Models}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {130:1--130:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela 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.ICALP.2021.130}, URN = {urn:nbn:de:0030-drops-141997}, doi = {10.4230/LIPIcs.ICALP.2021.130}, annote = {Keywords: finite model theory, word equations, descriptive complexity, model checking, document spanners} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Joel D. Day, Pamela Fleischmann, Maria Kosche, Tore Koß, Florin Manea, and Stefan Siemer. The Edit Distance to k-Subsequence Universality. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{day_et_al:LIPIcs.STACS.2021.25, author = {Day, Joel D. and Fleischmann, Pamela and Kosche, Maria and Ko{\ss}, Tore and Manea, Florin and Siemer, Stefan}, title = {{The Edit Distance to k-Subsequence Universality}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {25:1--25:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.25}, URN = {urn:nbn:de:0030-drops-136705}, doi = {10.4230/LIPIcs.STACS.2021.25}, annote = {Keywords: Subsequence, Scattered factor, Subword, Universality, k-subsequence universality, Edit distance, Efficient algorithms} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Joel D. Day and Florin Manea. On the Structure of Solution Sets to Regular Word Equations. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 124:1-124:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{day_et_al:LIPIcs.ICALP.2020.124, author = {Day, Joel D. and Manea, Florin}, title = {{On the Structure of Solution Sets to Regular Word Equations}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {124:1--124: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.124}, URN = {urn:nbn:de:0030-drops-125314}, doi = {10.4230/LIPIcs.ICALP.2020.124}, annote = {Keywords: Quadratic Word Equations, Regular Word Equations, String Solving, NP} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Joel D. Day, Florin Manea, and Dirk Nowotka. Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{day_et_al:LIPIcs.MFCS.2019.44, author = {Day, Joel D. and Manea, Florin and Nowotka, Dirk}, title = {{Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {44:1--44: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.44}, URN = {urn:nbn:de:0030-drops-109889}, doi = {10.4230/LIPIcs.MFCS.2019.44}, annote = {Keywords: Quadratic Word Equations, Length Upper Bounds, NP, Unavoidable Patterns} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea, and Markus L. Schmid. Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 109:1-109:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{casel_et_al:LIPIcs.ICALP.2019.109, author = {Casel, Katrin and Day, Joel D. and Fleischmann, Pamela and Kociumaka, Tomasz and Manea, Florin and Schmid, Markus L.}, title = {{Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {109:1--109:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.109}, URN = {urn:nbn:de:0030-drops-106858}, doi = {10.4230/LIPIcs.ICALP.2019.109}, annote = {Keywords: Graph and String Parameters, NP-Completeness, Approximation Algorithms} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Joel D. Day, Pamela Fleischmann, Florin Manea, and Dirk Nowotka. Local Patterns. 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. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{day_et_al:LIPIcs.FSTTCS.2017.24, author = {Day, Joel D. and Fleischmann, Pamela and Manea, Florin and Nowotka, Dirk}, title = {{Local Patterns}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {24:1--24:14}, 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.24}, URN = {urn:nbn:de:0030-drops-84013}, doi = {10.4230/LIPIcs.FSTTCS.2017.24}, annote = {Keywords: Patterns with Variables, Local Patterns, Combinatorial Pattern Matching, Descriptive Patterns} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Joel D. Day, Florin Manea, and Dirk Nowotka. The Hardness of Solving Simple Word Equations. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{day_et_al:LIPIcs.MFCS.2017.18, author = {Day, Joel D. and Manea, Florin and Nowotka, Dirk}, title = {{The Hardness of Solving Simple Word Equations}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {18:1--18: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.18}, URN = {urn:nbn:de:0030-drops-81233}, doi = {10.4230/LIPIcs.MFCS.2017.18}, annote = {Keywords: Word Equations, Regular Patterns, Regular Constraints} }
Feedback for Dagstuhl Publishing