Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Anita Badyl and Paweł Parys. Extending the WMSO+U Logic with Quantification over Tuples. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{badyl_et_al:LIPIcs.CSL.2024.12, author = {Badyl, Anita and Parys, Pawe{\l}}, title = {{Extending the WMSO+U Logic with Quantification over Tuples}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.12}, URN = {urn:nbn:de:0030-drops-196557}, doi = {10.4230/LIPIcs.CSL.2024.12}, annote = {Keywords: Boundedness, logic, decidability, expressivity, recursion schemes} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
David Barozzini, Paweł Parys, and Jan Wróblewski. Unboundedness for Recursion Schemes: A Simpler Type System. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 112:1-112:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{barozzini_et_al:LIPIcs.ICALP.2022.112, author = {Barozzini, David and Parys, Pawe{\l} and Wr\'{o}blewski, Jan}, title = {{Unboundedness for Recursion Schemes: A Simpler Type System}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {112:1--112:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.112}, URN = {urn:nbn:de:0030-drops-164533}, doi = {10.4230/LIPIcs.ICALP.2022.112}, annote = {Keywords: Higher-order recursion schemes, boundedness, intersection types, safe schemes} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Paweł Parys. Higher-Order Model Checking Step by Step. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 140:1-140:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{parys:LIPIcs.ICALP.2021.140, author = {Parys, Pawe{\l}}, title = {{Higher-Order Model Checking Step by Step}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {140:1--140:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.140}, URN = {urn:nbn:de:0030-drops-142098}, doi = {10.4230/LIPIcs.ICALP.2021.140}, annote = {Keywords: Higher-order recursion schemes, Parity automata, Model-checking, Transformation, Order reduction} }
Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
André Arnold, Damian Niwiński, and Paweł Parys. A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arnold_et_al:LIPIcs.CSL.2021.9, author = {Arnold, Andr\'{e} and Niwi\'{n}ski, Damian and Parys, Pawe{\l}}, title = {{A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation}}, booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)}, pages = {9:1--9:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-175-7}, ISSN = {1868-8969}, year = {2021}, volume = {183}, editor = {Baier, Christel and Goubault-Larrecq, Jean}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.9}, URN = {urn:nbn:de:0030-drops-134430}, doi = {10.4230/LIPIcs.CSL.2021.9}, annote = {Keywords: Mu-calculus, Parity games, Quasi-polynomial time, Black-box algorithm} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Paweł Parys. Higher-Order Nonemptiness Step by Step. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{parys:LIPIcs.FSTTCS.2020.53, author = {Parys, Pawe{\l}}, title = {{Higher-Order Nonemptiness Step by Step}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {53:1--53:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.53}, URN = {urn:nbn:de:0030-drops-132941}, doi = {10.4230/LIPIcs.FSTTCS.2020.53}, annote = {Keywords: Higher-order grammars, Nonemptiness, Model-checking, Transformation, Order reduction} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
David Barozzini, Lorenzo Clemente, Thomas Colcombet, and Paweł Parys. Cost Automata, Safe Schemes, and Downward Closures. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 109:1-109:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{barozzini_et_al:LIPIcs.ICALP.2020.109, author = {Barozzini, David and Clemente, Lorenzo and Colcombet, Thomas and Parys, Pawe{\l}}, title = {{Cost Automata, Safe Schemes, and Downward Closures}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {109:1--109:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.109}, URN = {urn:nbn:de:0030-drops-125169}, doi = {10.4230/LIPIcs.ICALP.2020.109}, annote = {Keywords: Cost logics, cost automata, downward closures, higher-order recursion schemes, safe recursion schemes} }
Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Paweł Parys. Parity Games: Another View on Lehtinen’s Algorithm. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{parys:LIPIcs.CSL.2020.32, author = {Parys, Pawe{\l}}, title = {{Parity Games: Another View on Lehtinen’s Algorithm}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {32:1--32:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.32}, URN = {urn:nbn:de:0030-drops-116757}, doi = {10.4230/LIPIcs.CSL.2020.32}, annote = {Keywords: Parity games, quasi-polynomial time, separating automata, good-for-games automata} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Paweł Parys. Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{parys:LIPIcs.MFCS.2019.10, author = {Parys, Pawe{\l}}, title = {{Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {10:1--10:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.10}, URN = {urn:nbn:de:0030-drops-109543}, doi = {10.4230/LIPIcs.MFCS.2019.10}, annote = {Keywords: Parity games, Zielonka’s algorithm, quasi-polynomial time} }
Published in: LIPIcs, Volume 108, 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)
Pawel Parys. Homogeneity Without Loss of Generality. In 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 108, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{parys:LIPIcs.FSCD.2018.27, author = {Parys, Pawel}, title = {{Homogeneity Without Loss of Generality}}, booktitle = {3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-077-4}, ISSN = {1868-8969}, year = {2018}, volume = {108}, editor = {Kirchner, H\'{e}l\`{e}ne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2018.27}, URN = {urn:nbn:de:0030-drops-91972}, doi = {10.4230/LIPIcs.FSCD.2018.27}, annote = {Keywords: higher-order recursion schemes, lambda-calculus, homogeneous types, safe schemes} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Pawel Parys. Recursion Schemes and the WMSO+U Logic. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{parys:LIPIcs.STACS.2018.53, author = {Parys, Pawel}, title = {{Recursion Schemes and the WMSO+U Logic}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {53:1--53:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.53}, URN = {urn:nbn:de:0030-drops-85122}, doi = {10.4230/LIPIcs.STACS.2018.53}, annote = {Keywords: higher-order recursion schemes, intersection types, WMSO+U logic, boundedness} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Pawel Parys. The Complexity of the Diagonal Problem for Recursion Schemes. 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. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{parys:LIPIcs.FSTTCS.2017.45, author = {Parys, Pawel}, title = {{The Complexity of the Diagonal Problem for Recursion Schemes}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {45:1--45: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.45}, URN = {urn:nbn:de:0030-drops-83757}, doi = {10.4230/LIPIcs.FSTTCS.2017.45}, annote = {Keywords: diagonal problem, higher-order recursion schemes, intersection types, downward closure} }
Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Pawel Parys and Szymon Torunczyk. Models of Lambda-Calculus and the Weak MSO Logic. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{parys_et_al:LIPIcs.CSL.2016.11, author = {Parys, Pawel and Torunczyk, Szymon}, title = {{Models of Lambda-Calculus and the Weak MSO Logic}}, booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)}, pages = {11:1--11:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-022-4}, ISSN = {1868-8969}, year = {2016}, volume = {62}, editor = {Talbot, Jean-Marc and Regnier, Laurent}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.11}, URN = {urn:nbn:de:0030-drops-65511}, doi = {10.4230/LIPIcs.CSL.2016.11}, annote = {Keywords: typed lambda-calculus, models, weak MSO logic} }
Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)
Wojciech Czerwinski, Claire David, Filip Murlak, and Pawel Parys. Reasoning About Integrity Constraints for Tree-Structured Data. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{czerwinski_et_al:LIPIcs.ICDT.2016.20, author = {Czerwinski, Wojciech and David, Claire and Murlak, Filip and Parys, Pawel}, title = {{Reasoning About Integrity Constraints for Tree-Structured Data}}, booktitle = {19th International Conference on Database Theory (ICDT 2016)}, pages = {20:1--20:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-002-6}, ISSN = {1868-8969}, year = {2016}, volume = {48}, editor = {Martens, Wim and Zeume, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.20}, URN = {urn:nbn:de:0030-drops-57897}, doi = {10.4230/LIPIcs.ICDT.2016.20}, annote = {Keywords: data trees, integrity constraints, unions of conjunctive queries, schema mappings, entailment, containment, consistency} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Achim Blumensath, Thomas Colcombet, and Pawel Parys. On a Fragment of AMSO and Tiling Systems. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{blumensath_et_al:LIPIcs.STACS.2016.19, author = {Blumensath, Achim and Colcombet, Thomas and Parys, Pawel}, title = {{On a Fragment of AMSO and Tiling Systems}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {19:1--19:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.19}, URN = {urn:nbn:de:0030-drops-57202}, doi = {10.4230/LIPIcs.STACS.2016.19}, annote = {Keywords: monadic second-order logic, boundedness, tiling problems} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Mikolaj Bojanczyk, Pawel Parys, and Szymon Torunczyk. The MSO+U Theory of (N,<) Is Undecidable. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 21:1-21:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bojanczyk_et_al:LIPIcs.STACS.2016.21, author = {Bojanczyk, Mikolaj and Parys, Pawel and Torunczyk, Szymon}, title = {{The MSO+U Theory of (N,\langle) Is Undecidable}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {21:1--21:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.21}, URN = {urn:nbn:de:0030-drops-57223}, doi = {10.4230/LIPIcs.STACS.2016.21}, annote = {Keywords: automata, logic, unbounding quantifier, bounds, undecidability} }
Feedback for Dagstuhl Publishing