2023

  1. Graph Rewriting and Relabeling with PBPO\(^\Mbox+\): A Unifying Theory for Quasitoposes
    Roy Overbeek, Jörg Endrullis, and RossetAloı̈s
    J. Log. Algebraic Methods Program. , 133 , pp. 100873 (2023)
    paper

    Summary

    We extend the powerful Pullback-Pushout (PBPO) approach for graph rewriting with strong matching. Our approach, called PBPO+, allows more control over the embedding of the pattern in the host graph, which is important for a large class of rewrite systems. We argue that PBPO+ can be considered a unifying theory in the general setting of quasitoposes, by demonstrating that PBPO+ can define a strict superset of the rewrite relations definable by PBPO, AGREE and DPO. Additionally, we show that PBPO+ is well suited for rewriting labeled graphs and some classes of attributed graphs, by introducing a lattice structure on the label set and requiring graph morphisms to be order-preserving.

    This paper is an extended version of Graph Rewriting and Relabeling with PBPO+ (ICGT 2021).

    Bibtex

    @article{graph:rewriting:pbpo:2023,
  author = {Overbeek, Roy and Endrullis, J{\"{o}}rg and Rosset, Alo{\"{\i}}s},
  title = {Graph rewriting and relabeling with PBPO\({}^{\mbox{+}}\): {A} unifying
                    theory for quasitoposes},
  journal = {J. Log. Algebraic Methods Program.},
  volume = {133},
  pages = {100873},
  year = {2023},
  url = {https://doi.org/10.1016/j.jlamp.2023.100873},
  doi = {10.1016/J.JLAMP.2023.100873},
  biburl = {https://dblp.org/rec/journals/jlap/OverbeekER23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  keywords = {rewriting},
  type = {journal}
}

    Digital Object Identifier

    10.1016/J.JLAMP.2023.100873
  2. Termination of Graph Transformation Systems Using Weighted Subgraph Counting
    Roy Overbeek, and Jörg Endrullis
    In: Graph Transformation - 16th International Conference, ICGT 2023, Held as Part of STAF 2023, Leicester, UK, July 19-20, 2023, Proceedings Fernández, Maribel and Poskitt, Christopher M. (eds.) , pp. 81–101 , Springer (2023)
    paper

    Summary

    We introduce a termination method for the algebraic graph transformation framework PBPO+, in which we weigh objects by summing a class of weighted morphisms targeting them. The method is well-defined in rm-adhesive quasitoposes (which include toposes and therefore many graph categories of interest), and is applicable to non-linear rules. The method is also defined for other frameworks, including SqPO and left-linear DPO, because we have previously shown that they are naturally encodable into PBPO+ in the quasitopos setting.

    An extended version appeared in Logical Methods in Computer Science (2024).

    Bibtex

    @inproceedings{graph:termination:subgraph:counting:2023,
  author = {Overbeek, Roy and Endrullis, J{\"{o}}rg},
  editor = {Fern{\'{a}}ndez, Maribel and Poskitt, Christopher M.},
  title = {Termination of Graph Transformation Systems Using Weighted Subgraph
                    Counting},
  booktitle = {Graph Transformation - 16th International Conference, {ICGT} 2023,
                    Held as Part of {STAF} 2023, Leicester, UK, July 19-20, 2023, Proceedings},
  series = {Lecture Notes in Computer Science},
  volume = {13961},
  pages = {81--101},
  publisher = {Springer},
  year = {2023},
  url = {https://doi.org/10.1007/978-3-031-36709-0\_5},
  doi = {10.1007/978-3-031-36709-0\_5},
  biburl = {https://dblp.org/rec/conf/gg/OverbeekE23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  keywords = {rewriting, termination},
  type = {conference}
}

    Digital Object Identifier

    10.1007/978-3-031-36709-0_5
  3. Fuzzy Presheaves Are Quasitoposes
    RossetAloı̈s, Roy Overbeek, and Jörg Endrullis
    In: Graph Transformation - 16th International Conference, ICGT 2023, Held as Part of STAF 2023, Leicester, UK, July 19-20, 2023, Proceedings Fernández, Maribel and Poskitt, Christopher M. (eds.) , pp. 102–122 , Springer (2023)
    paper

    Summary

    Quasitoposes encompass a wide range of structures, including various categories of graphs. They have proven to be a natural setting for reasoning about the metatheory of algebraic graph rewriting. In this paper we propose and motivate the notion of fuzzy presheaves, which generalises fuzzy sets and fuzzy graphs. We prove that fuzzy presheaves are rm-adhesive quasitoposes, proving our recent conjecture for fuzzy graphs. Furthermore, we show that simple fuzzy graphs categories are quasitoposes.

    Bibtex

    @inproceedings{graph:rewriting:fuzzy:presheaves:2023,
  author = {Rosset, Alo{\"{\i}}s and Overbeek, Roy and Endrullis, J{\"{o}}rg},
  editor = {Fern{\'{a}}ndez, Maribel and Poskitt, Christopher M.},
  title = {Fuzzy Presheaves are Quasitoposes},
  booktitle = {Graph Transformation - 16th International Conference, {ICGT} 2023,
                    Held as Part of {STAF} 2023, Leicester, UK, July 19-20, 2023, Proceedings},
  series = {Lecture Notes in Computer Science},
  volume = {13961},
  pages = {102--122},
  publisher = {Springer},
  year = {2023},
  url = {https://doi.org/10.1007/978-3-031-36709-0\_6},
  doi = {10.1007/978-3-031-36709-0\_6},
  biburl = {https://dblp.org/rec/conf/gg/RossetOE23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  keywords = {rewriting, category theory},
  type = {conference}
}

    Digital Object Identifier

    10.1007/978-3-031-36709-0_6
  4. Characterisation of Lawvere-Tierney Topologies on Simplicial Sets, Bicolored Graphs, and Fuzzy Sets
    RossetAloı̈s, Helle Hvid Hansen, and Jörg Endrullis
    In: Logic, Language, and Computation - 14th International Tbilisi Symposium, TbiLLC 2023, Telavi, Georgia, September 18-22, 2023, Revised Selected Papers Hogeweg, Lotte, Jalali, Raheleh, Sedlár, Igor, and Schwarz, Lena (eds.) , pp. 258–284 , Springer (2023)
    paper

    Summary

    Simplicial sets generalise many categories of graphs. In this paper, we give a complete characterisation of the Lawvere-Tierney topologies on (semi-)simplicial sets, on bicolored graphs, and on fuzzy sets. We apply our results to establish that 'partially simple' simplicial sets and 'partially simple' graphs form quasitoposes.

    Bibtex

    @inproceedings{topos:lawvere:tierney:2023,
  author = {Rosset, Alo{\"{\i}}s and Hansen, Helle Hvid and Endrullis, J{\"{o}}rg},
  editor = {Hogeweg, Lotte and Jalali, Raheleh and Sedl{\'{a}}r, Igor and Schwarz, Lena},
  title = {Characterisation of Lawvere-Tierney Topologies on Simplicial Sets,
                    Bicolored Graphs, and Fuzzy Sets},
  booktitle = {Logic, Language, and Computation - 14th International Tbilisi Symposium,
                    TbiLLC 2023, Telavi, Georgia, September 18-22, 2023, Revised Selected
                    Papers},
  series = {Lecture Notes in Computer Science},
  volume = {15661},
  pages = {258--284},
  publisher = {Springer},
  year = {2023},
  url = {https://doi.org/10.1007/978-3-032-14339-6\_14},
  doi = {10.1007/978-3-032-14339-6\_14},
  biburl = {https://dblp.org/rec/conf/tbillc/RossetHE23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  keywords = {category theory},
  type = {conference}
}

    Digital Object Identifier

    10.1007/978-3-032-14339-6_14