Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yossi Azar, Shahar Lewkowicz, and Danny Vainstein. List Update with Delays or Time Windows. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{azar_et_al:LIPIcs.ICALP.2024.15, author = {Azar, Yossi and Lewkowicz, Shahar and Vainstein, Danny}, title = {{List Update with Delays or Time Windows}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {15:1--15: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.15}, URN = {urn:nbn:de:0030-drops-201583}, doi = {10.4230/LIPIcs.ICALP.2024.15}, annote = {Keywords: Online, List Update, Delay, Time Window, Deadline} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Moses Ganardi. Compression by Contracting Straight-Line Programs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ganardi:LIPIcs.ESA.2021.45, author = {Ganardi, Moses}, title = {{Compression by Contracting Straight-Line Programs}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {45:1--45:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.45}, URN = {urn:nbn:de:0030-drops-146263}, doi = {10.4230/LIPIcs.ESA.2021.45}, annote = {Keywords: grammar-based compression, balancing, finger search} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Robert Ferens and Artur Jeż. Solving One Variable Word Equations in the Free Group in Cubic Time. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ferens_et_al:LIPIcs.STACS.2021.30, author = {Ferens, Robert and Je\.{z}, Artur}, title = {{Solving One Variable Word Equations in the Free Group in Cubic Time}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {30:1--30:17}, 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.30}, URN = {urn:nbn:de:0030-drops-136751}, doi = {10.4230/LIPIcs.STACS.2021.30}, annote = {Keywords: Word equations, free group, one-variable equations} }
Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Artur Jeż. Solving Word Equations (And Other Unification Problems) by Recompression (Invited Talk). In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{jez:LIPIcs.CSL.2020.3, author = {Je\.{z}, Artur}, title = {{Solving Word Equations (And Other Unification Problems) by Recompression}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {3:1--3:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-132-0}, ISSN = {1868-8969}, year = {2020}, volume = {152}, editor = {Fern\'{a}ndez, Maribel 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.CSL.2020.3}, URN = {urn:nbn:de:0030-drops-116468}, doi = {10.4230/LIPIcs.CSL.2020.3}, annote = {Keywords: word equation, context unification, equations in groups, compression} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Moses Ganardi, Artur Jez, and Markus Lohrey. Sliding Windows over Context-Free Languages. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ganardi_et_al:LIPIcs.MFCS.2018.15, author = {Ganardi, Moses and Jez, Artur and Lohrey, Markus}, title = {{Sliding Windows over Context-Free Languages}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {15:1--15:15}, 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.15}, URN = {urn:nbn:de:0030-drops-95973}, doi = {10.4230/LIPIcs.MFCS.2018.15}, annote = {Keywords: sliding windows, streaming algorithms, context-free languages} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Michal Ganczorz, Pawel Gawrychowski, Artur Jez, and Tomasz Kociumaka. Edit Distance with Block Operations. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ganczorz_et_al:LIPIcs.ESA.2018.33, author = {Ganczorz, Michal and Gawrychowski, Pawel and Jez, Artur and Kociumaka, Tomasz}, title = {{Edit Distance with Block Operations}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {33:1--33:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.33}, URN = {urn:nbn:de:0030-drops-94963}, doi = {10.4230/LIPIcs.ESA.2018.33}, annote = {Keywords: Edit distance, Block operations, Common string partition} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Artur Jez. Word Equations in Nondeterministic Linear Space. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 95:1-95:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{jez:LIPIcs.ICALP.2017.95, author = {Jez, Artur}, title = {{Word Equations in Nondeterministic Linear Space}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {95:1--95: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.95}, URN = {urn:nbn:de:0030-drops-74089}, doi = {10.4230/LIPIcs.ICALP.2017.95}, annote = {Keywords: Word equations, string unification, context-sensitive languages, space efficient computations, linear space} }
Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Artur Jez. Recompression of SLPs. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{jez:LIPIcs.CPM.2017.2, author = {Jez, Artur}, title = {{Recompression of SLPs}}, booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-039-2}, ISSN = {1868-8969}, year = {2017}, volume = {78}, editor = {K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.2}, URN = {urn:nbn:de:0030-drops-73475}, doi = {10.4230/LIPIcs.CPM.2017.2}, annote = {Keywords: Straight Line Programs, smallest grammar problem, compression, pro- cessing compressed data, recompression} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Artur Jez. Recompression: New Approach to Word Equations and Context Unification (Invited Talk). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 2:1-2:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{jez:LIPIcs.STACS.2017.2, author = {Jez, Artur}, title = {{Recompression: New Approach to Word Equations and Context Unification}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {2:1--2:3}, 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.2}, URN = {urn:nbn:de:0030-drops-70280}, doi = {10.4230/LIPIcs.STACS.2017.2}, annote = {Keywords: Word equations, exponent of periodicity, semantic unification, string unification, context unification, compression} }
Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Pawel Gawrychowski and Artur Jez. LZ77 Factorisation of Trees. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{gawrychowski_et_al:LIPIcs.FSTTCS.2016.35, author = {Gawrychowski, Pawel and Jez, Artur}, title = {{LZ77 Factorisation of Trees}}, booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)}, pages = {35:1--35:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-027-9}, ISSN = {1868-8969}, year = {2016}, volume = {65}, editor = {Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.35}, URN = {urn:nbn:de:0030-drops-68700}, doi = {10.4230/LIPIcs.FSTTCS.2016.35}, annote = {Keywords: Tree grammars, Grammar compression, LZ77, SLP, Tree compression} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Volker Diekert, Artur Jez, and Manfred Kufleitner. Solutions of Word Equations Over Partially Commutative Structures. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 127:1-127:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{diekert_et_al:LIPIcs.ICALP.2016.127, author = {Diekert, Volker and Jez, Artur and Kufleitner, Manfred}, title = {{Solutions of Word Equations Over Partially Commutative Structures}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {127:1--127: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.127}, URN = {urn:nbn:de:0030-drops-62624}, doi = {10.4230/LIPIcs.ICALP.2016.127}, annote = {Keywords: Word equations, EDT0L language, trace monoid, right-angled Artin group, partial commutation} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Artur Jez and Markus Lohrey. Approximation of smallest linear tree grammar. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 445-457, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{jez_et_al:LIPIcs.STACS.2014.445, author = {Jez, Artur and Lohrey, Markus}, title = {{Approximation of smallest linear tree grammar}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {445--457}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.445}, URN = {urn:nbn:de:0030-drops-44789}, doi = {10.4230/LIPIcs.STACS.2014.445}, annote = {Keywords: Grammar-based compression, Tree compression, Tree-grammars} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Artur Jez. Recompression: a simple and powerful technique for word equations. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 233-244, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{jez:LIPIcs.STACS.2013.233, author = {Jez, Artur}, title = {{Recompression: a simple and powerful technique for word equations}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {233--244}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.233}, URN = {urn:nbn:de:0030-drops-39376}, doi = {10.4230/LIPIcs.STACS.2013.233}, annote = {Keywords: Word equations, exponent of periodicity, string unification} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Artur Jez. Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P). In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 136-147, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{jez:LIPIcs.STACS.2012.136, author = {Jez, Artur}, title = {{Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {136--147}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.136}, URN = {urn:nbn:de:0030-drops-34068}, doi = {10.4230/LIPIcs.STACS.2012.136}, annote = {Keywords: Compressed membership problem, SLP, Finite Automata, Algorithms for compressed data} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Artur Jez and Alexander Okhotin. On Equations over Sets of Integers. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 477-488, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{jez_et_al:LIPIcs.STACS.2010.2478, author = {Jez, Artur and Okhotin, Alexander}, title = {{On Equations over Sets of Integers}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {477--488}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2478}, URN = {urn:nbn:de:0030-drops-24780}, doi = {10.4230/LIPIcs.STACS.2010.2478}, annote = {Keywords: Language equations, computability, arithmetical hierarchy, hyper-arithmetical hierarchy} }