21 research outputs found
Graph Rewriting and Relabeling with PBPO+: A Unifying Theory for Quasitoposes
No full textWe 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.Comment: This article significantly extends and improves arXiv:2010.08230. 36
page
La foire aux valeurs
No full textL'auteur examine l'usage contemporain du terme "valeur" en rapport avec le patrimoine, et revient sur l'emploi théorique et pratique qu'en fait Aloïs Riegl.The author examines the contemporary use of the term "value", in touch with the heritage, and returns on the theoretical and practical employment by Aloïs Riegl
Graph Rewriting and Relabeling with PBPO <sup>+</sup>
Full text linkWe extend the powerful Pullback-Pushout (PBPO) approach for graph rewriting with strong matching. Our approach, called PBPO +, exerts more control over the embedding of the pattern in the host graph, which is important for a large class of graph rewrite systems. In addition, we show that PBPO + is well-suited for rewriting labeled graphs and certain classes of attributed graphs. For this purpose, we employ a lattice structure on the label set and use order-preserving graph morphisms. We argue that our approach is simpler and more general than related relabeling approaches in the literature.</p
Uniform Monad Presentations and Graph Quasitoposes
Full text linkCategory theory is a field of mathematics that provides a unifying framework for the generalisation of mathematical definitions and theorems, and which has found significant applications in computer science. This thesis explores two such applications: uniform algebraic presentations of monads and quasitoposes in graph rewriting. Part I of this thesis studies monads, which serve as a unifying framework for modelling computational effects in programming languages. A key aspect of monads is their correspondence with algebraic theories, where an algebraic theory that corresponds to a monad is called an algebraic presentation of that monad. Composing monads allows to combine their computational effects and is often performed via distributive laws, which correspond to the algebraic notion of composite theories. This thesis provides a complete and constructive proof of this correspondence and establishes criteria that ensure a certain minimal set of distributivity equations suffices to axiomatise the composite theory. To achieve this, we employ term rewriting techniques and introducing functor rewriting systems. Important results in the literature rely on the correspondence we proved, namely no-go theorems, which establish that certain distributive laws cannot exist. The non-existence of certain distributive laws has motivated investigations into weaker notions of distributive laws, called weak distributive laws. In this context, semifree monads were introduced to establish a correspondence between distributive laws for a given monad and weak distributive laws for its semifree monad. The second main contribution of Part I proves how an algebraic presentation of a monad can be systematically transformed into a presentation of its semifree monad. Part II of this thesis studies quasitoposes and their role in graph rewriting, a rule-based framework for transforming graphs. The diversity of graph definitions makes it impractical to develop a separate rewriting formalism for each type. Category theory offers a unified approach for defining formalisms in a graph-agnostic manner. Moreover, quasitoposes, which are categories with specific properties, have emerged as a promising framework for comparing rewriting formalisms, studying meta-theorems for non-linear rewriting, facilitating relabelling, and supporting categorical termination methods. This thesis develops two methods for identifying new quasitoposes: one via fuzzy presheaves and the other via Lawvere-Tierney (LT) topologies. Fuzzy presheaves are introduced as a generalisation of fuzzy sets and fuzzy graphs, and their categories are shown to be rm-adhesive quasitoposes. The second approach provides a complete characterisation of LT-topologies and of their separated elements and sheaves in the categories of simplicial sets, bicoloured graphs, fuzzy sets, and fuzzy graphs, leading to the identification of new quasitoposes
Algebraic Presentation of Semifree Monads
Full text linkMonads and their composition via distributive laws have many applications in
program semantics and functional programming. For many interesting monads,
distributive laws fail to exist, and this has motivated investigations into
weaker notions. In this line of research, Petri\c{s}an and Sarkis recently
introduced a construction called the semifree monad in order to study
semialgebras for a monad and weak distributive laws. In this paper, we prove
that an algebraic presentation of the semifree monad M^s on a monad M can be
obtained uniformly from an algebraic presentation of M. This result was
conjectured by Petri\c{s}an and Sarkis. We also show that semifree monads are
ideal monads, that the semifree construction is not a monad transformer, and
that the semifree construction is a comonad on the category of monads.Comment: In Proceedings of CMCS 202
Correspondence Between Composite Theories and Distributive Laws
Full text linkComposite theories are the algebraic equivalent of distributive laws. In this paper, we delve into the details of this correspondence and concretely show how to construct a composite theory from a distributive law and vice versa. Using term rewriting methods, we also describe when a minimal set of equations axiomatises the composite theory
Fuzzy Presheaves are Quasitoposes
Full text linkQuasitoposes 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 graph categories are quasitoposes.</p
Characterisation of Lawvere-Tierney Topologies on Simplicial Sets, Bicolored Graphs, and Fuzzy Sets
Full text linkSimplicial sets generalize many categories of graphs. In this paper, we give a complete characterization 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
Correspondence between Composite Theories and Distributive Laws
Full text linkComposite theories are the algebraic equivalent of distributive laws. In this
paper, we delve into the details of this correspondence and concretely show how
to construct a composite theory from a distributive law and vice versa. Using
term rewriting methods, we also describe when a minimal set of equations
axiomatises the composite theory
Algebraic Presentation of Semifree Monads
No full textMonads and their composition via distributive laws have many applications in program semantics and functional programming. For many interesting monads, distributive laws fail to exist, and this has motivated investigations into weaker notions. In this line of research, Petrişan and Sarkis recently introduced a construction called the semifree monad in order to study semialgebras for a monad and weak distributive laws. In this paper, we prove that an algebraic presentation of the semifree monad Ms on a monad M can be obtained uniformly from an algebraic presentation of M. This result was conjectured by Petrişan and Sarkis. We also show that semifree monads are ideal monads, that the semifree construction is not a monad transformer, and that the semifree construction is a comonad on the category of monads
