The algebra of directed acyclic graphs

DOI10.1007/978-3-642-38164-5_4MaRDI QIDQ4922072zbMATH OpenOpenAlexFDO

Authors Marco Devesas Campos, Marcelo P. Fiore

Publication date 28 May 2013

Published in Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.0376

zbMATH Keywords

bialgebradagHopf algebrainitial-algebra semantics, categorical semanticsPROPsymmetric monoidal equational theorytopological sorting

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Hopf algebras and their applications (16T05) Theories (e.g., algebraic theories), structure, and semantics (18C10) Categorical semantics of formal languages (18C50)

Abstract: We give an algebraic presentation of directed acyclic graph structure, introducing a symmetric monoidal equational theory whose free PROP we characterise as that of finite abstract dags with input/output interfaces. Our development provides an initial-algebra semantics for dag structure.

Recommendations

• Algebraic structures of directed acyclic graphs: application to concurrent calculus
• scientific article; zbMATH DE number 3959458
• An algebra for directed bigraphs
• scientific article; zbMATH DE number 3978423
• An algebraic foundation for graph-based diagrams in computing

Cites work

• An abstract characterization of Thompson's group \(F\).
• Axioms for bigraphical structure
• Categorical algebra
• scientific article; zbMATH DE number 2125662 (Why is no real title available?)
• scientific article; zbMATH DE number 1933002 (Why is no real title available?)
• Languages for monoidal categories
• Temperley-Lieb Algebra: From Knot Theory to Logic and Computation via Quantum Mechanics
• The Space and Motion of Communicating Agents

Cited in

(26)

• An algebraic framework of weighted directed graphs
• Posets with interfaces as a model for concurrency
• Catoids and modal convolution algebras
• An algebra for directed bigraphs
• Confluence of graph rewriting with interfaces
• Interacting Hopf algebras
• A formal language for cyclic operads
• The algebra of recursive graph transformation language UnCAL: complete axiomatisation and iteration categorical semantics
• scientific article; zbMATH DE number 3948305 (Why is no real title available?)
• scientific article; zbMATH DE number 3959458 (Why is no real title available?)
• scientific article; zbMATH DE number 14488 (Why is no real title available?)
• Alphabets of Acyclic Invariant Structures
• scientific article; zbMATH DE number 1841817 (Why is no real title available?)
• Algebraic structures of directed acyclic graphs: application to concurrent calculus
• An algebraic foundation for graph-based diagrams in computing
• Updating probabilistic knowledge on condition/event nets using Bayesian networks
• Presenting finite posets
• scientific article; zbMATH DE number 7437711 (Why is no real title available?)
• Generating Posets Beyond N
• How to prove decidability of equational theories with second-order computation analyser SOL
• THE CHECK OF THE CORRESPONDENCE OF THE DIRECTED GRAPH TO THE ALGEBRAIC LATTICE
• Lawvere categories as composed PROPs
• String diagram rewrite theory III: Confluence with and without Frobenius
• Towards compositional graph theory
• A compositional framework for Petri nets
• On a class of algebras associated to directed graphs

This page was built for publication: The algebra of directed acyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4922072)