Publications

2024

• S. Brinke, E. Grädel, L. Mrkonjić, and M. Naaf. Semiring Provenance in the Infinite. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen (A. Amarilli and A. Deutsch, Eds.), vol. 119 of Open Access Series in Informatics (OASIcs), pp. 3:1–3:26, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.             
  BibTeX

  @inproceedings{BGMN24,
       author = {Sophie Brinke and Erich Gr{\"a}del and Lovro Mrkonji{\'c} and Matthias Naaf},
       title = {Semiring Provenance in the Infinite},
       booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen},
       pages = {3:1--3:26},
       series = {Open Access Series in Informatics (OASIcs)},
       isbn = {978-3-95977-320-1},
       issn = {2190-6807},
       year = {2024},
       volume = {119},
       editor = {Antoine Amarilli and Alin Deutsch},
       publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
       address = {Dagstuhl, Germany},
       url = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.3},
       doi = {10.4230/OASIcs.Tannen.3},
  }
  

• E. Grädel, N. Lücking, and M. Naaf. Semiring Provenance for Büchi Games: Strategy Analysis with Absorptive Polynomials. Logical Methods in Computer Science, vol. 20(1), 2024.             
  BibTeX

  @article{GLN24,
       author = {Erich Gr{\"a}del and Niels L{\"u}cking and Matthias Naaf},
       title = {{Semiring Provenance for B{\"u}chi Games: Strategy Analysis with Absorptive Polynomials}},
       url = {https://lmcs.episciences.org/13205},
       doi = {10.46298/lmcs-20(1:21)2024},
       journal = {Logical Methods in Computer Science},
       volume = {20},
       number = {1},
       year = {2024},
  }
  

2023

• C. Bizière, E. Grädel, and M. Naaf. Locality Theorems in Semiring Semantics. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (J. Leroux, S. Lombardy, and D. Peleg, Eds.), vol. 272 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 20:1–20:15, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.             
  BibTeX

  @inproceedings{BGN23b,
       author = {Clotilde Bizi{\`e}re and Erich Gr{\"a}del and Matthias Naaf},
       title = {{Locality Theorems in Semiring Semantics}},
       booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
       pages = {20:1--20:15},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-95977-292-1},
       issn = {1868-8969},
       year = {2023},
       volume = {272},
       editor = {J{\'e}r{\^o}me Leroux and Sylvain Lombardy and David Peleg},
       publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
       address = {Dagstuhl, Germany},
       url = {https://drops.dagstuhl.de/opus/volltexte/2023/18554},
       urn = {urn:nbn:de:0030-drops-185546},
       doi = {10.4230/LIPIcs.MFCS.2023.20},
       annote = {Keywords: Semiring semantics, Locality, First-order logic},
  }
  

• C. Bizière, E. Grädel, and M. Naaf. Locality Theorems in Semiring Semantics. arXiv:2303.12627 [cs.LO], full version of MFCS'23 paper, 2023.             
  BibTeX

  @misc{BGN23,
       title = {Locality Theorems in Semiring Semantics},
       author = {Clotilde Bizière and Erich Gr{\"a}del and Matthias Naaf},
       year = {2023},
       howpublished = {arXiv:2303.12627 [cs.LO], full version of MFCS'23 paper},
       url = {http://arxiv.org/abs/2303.12627},
  }
  

2022

• E. Grädel, H. Helal, M. Naaf, and R. Wilke. Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022) (C. Baier and D. Fisman, Eds.), pp. 41:1–41:12. ACM, 2022.             
  BibTeX

  @inproceedings{GHNW22b,
       author = {Erich Gr{\"a}del and Hayyan Helal and Matthias Naaf and Richard Wilke},
       editor = {Christel Baier and Dana Fisman},
       title = {Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics},
       booktitle = {Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)},
       pages = {41:1--41:12},
       publisher = {{ACM}},
       year = {2022},
       doi = {10.1145/3531130.3533358},
       url = {https://doi.org/10.1145/3531130.3533358},
  }
  

• E. Grädel, H. Helal, M. Naaf, and R. Wilke. Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics. arXiv:2203.03425 [cs.LO], full version of LICS'22 paper, 2022.             
  BibTeX

  @misc{GHNW22,
       title = {Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics},
       author = {Erich Gr{\"a}del and Hayyan Helal and Matthias Naaf and Richard Wilke},
       year = {2022},
       howpublished = {arXiv:2203.03425 [cs.LO], full version of LICS'22 paper},
       url = {http://arxiv.org/abs/2203.03425},
  }
  

2021

• K. M. Dannert, E. Grädel, M. Naaf, and V. Tannen. Semiring Provenance for Fixed-Point Logic. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021) (C. Baier and J. Goubault-Larrecq, Eds.), vol. 183 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 17:1–17:22, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021.             
  BibTeX

  @inproceedings{DGNT21,
       author = {Katrin M. Dannert and Erich Gr{\"a}del and Matthias Naaf and Val Tannen},
       title = {{Semiring Provenance for Fixed-Point Logic}},
       booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
       pages = {17:1--17:22},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-95977-175-7},
       issn = {1868-8969},
       year = {2021},
       volume = {183},
       editor = {Christel Baier and Jean Goubault-Larrecq},
       publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
       address = {Dagstuhl, Germany},
       url = {https://drops.dagstuhl.de/opus/volltexte/2021/13451},
       urn = {urn:nbn:de:0030-drops-134518},
       doi = {10.4230/LIPIcs.CSL.2021.17},
       annote = {Keywords: Finite Model Theory, Semiring Provenance, Absorptive Semirings, Fixed-Point Logics},
  }
  

• E. Grädel, N. Lücking, and M. Naaf. Semiring Provenance for Büchi Games: Strategy Analysis with Absorptive Polynomials. In Proceedings 12th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2021) (P. Ganty and D. Bresolin, Eds.), vol. 346 of EPTCS, pp. 67–82, 2021.             
  BibTeX

  @inproceedings{GLN21b,
       author = {Erich Gr{\"a}del and Niels L{\"u}cking and Matthias Naaf},
       editor = {Pierre Ganty and Davide Bresolin},
       title = {Semiring Provenance for B{\"u}chi Games: Strategy Analysis with Absorptive Polynomials},
       booktitle = {Proceedings 12th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2021)},
       series = {{EPTCS}},
       volume = {346},
       pages = {67--82},
       year = {2021},
       url = {https://doi.org/10.4204/EPTCS.346.5},
       doi = {10.4204/EPTCS.346.5},
  }
  

• E. Grädel, N. Lücking, and M. Naaf. Semiring Provenance for Büchi Games: Strategy Analysis with Absorptive Polynomials. arXiv:2106.12892 [cs.LO], full version of GandALF'21 paper, 2021.             
  BibTeX

  @misc{GLN21,
       title = {Semiring Provenance for B{\"u}chi Games: Strategy Analysis with Absorptive Polynomials},
       author = {Erich Gr{\"a}del and Niels L{\"u}cking and Matthias Naaf},
       year = {2021},
       howpublished = {arXiv:2106.12892 [cs.LO], full version of GandALF'21 paper},
       url = {http://arxiv.org/abs/2106.12892},
  }
  

• M. Naaf. Computing Least and Greatest Fixed Points in Absorptive Semirings. arXiv:2106.00399 [cs.LO], full version of RAMiCS'21 paper, 2021.             
  BibTeX

  @misc{Naaf21,
       title = {Computing Least and Greatest Fixed Points in Absorptive Semirings},
       author = {Matthias Naaf},
       year = {2021},
       howpublished = {arXiv:2106.00399 [cs.LO], full version of RAMiCS'21 paper},
       url = {http://arxiv.org/abs/2106.00399},
  }
  

• M. Naaf. Computing Least and Greatest Fixed Points in Absorptive Semirings. In Relational and Algebraic Methods in Computer Science - 19th International Conference (RAMiCS 2021), Proceedings (U. Fahrenberg, M. Gehrke, L. Santocanale, and M. Winter, Eds.), vol. 13027 of Lecture Notes in Computer Science (LNCS), pp. 344–361. Springer, 2021.             
  BibTeX

  @inproceedings{Naaf21b,
       author = {Matthias Naaf},
       editor = {Uli Fahrenberg and Mai Gehrke and Luigi Santocanale and Michael Winter},
       title = {Computing Least and Greatest Fixed Points in Absorptive Semirings},
       booktitle = {Relational and Algebraic Methods in Computer Science - 19th International Conference (RAMiCS 2021), Proceedings},
       series = {Lecture Notes in Computer Science (LNCS)},
       volume = {13027},
       pages = {344--361},
       publisher = {Springer},
       year = {2021},
       url = {https://doi.org/10.1007/978-3-030-88701-8_21},
       doi = {10.1007/978-3-030-88701-8\_21},
  }
  

2019

• K. M. Dannert, E. Grädel, M. Naaf, and V. Tannen. Generalized Absorptive Polynomials and Provenance Semantics for Fixed-Point Logic. arXiv:1910.07910 [cs.LO], 2019.             
  BibTeX

  @misc{DGNV19,
       author = {Katrin M. {Dannert} and Erich Gr{\"a}del and Matthias {Naaf} and Val {Tannen}},
       title = {{Generalized Absorptive Polynomials and Provenance Semantics for Fixed-Point Logic}},
       year = {2019},
       url = {http://arxiv.org/abs/1910.07910},
       month = {Oct},
       howpublished = {arXiv:1910.07910 [cs.LO]},
  }
  

• M. Naaf. Semirings for Provenance Analysis of Fixed-point Logics and Games. Master thesis, RWTH Aachen University, 2019.             
  BibTeX

  @misc{Naaf19,
       author = {Matthias Naaf},
       howpublished = {Master thesis, RWTH Aachen University},
       title = {Semirings for Provenance Analysis of Fixed-point Logics and Games},
       url = {http://logic.rwth-aachen.de/pub/naaf/masterarbeit.pdf},
       year = {2019},
  }