Monoidal Width

DOI10.46298/LMCS-19(3:15)2023MaRDI QIDQ6076171zbMATH OpenOpenAlexFDO

Authors Elena di Lavore, Paweł Sobociński

Publication date 23 October 2023

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

monoidal categoriesrank widthtree width

Mathematics Subject Classification ID

Monoidal categories, symmetric monoidal categories (18M05)

Abstract: We introduce monoidal width as a measure of complexity for morphisms in monoidal categories. Inspired by well-known structural width measures for graphs, like tree width and rank width, monoidal width is based on a notion of syntactic decomposition: a monoidal decomposition of a morphism is an expression in the language of monoidal categories, where operations are monoidal products and compositions, that specifies this morphism. Monoidal width penalises the composition operation along ``big objects, while it encourages the use of monoidal products. We show that, by choosing the correct categorical algebra for decomposing graphs, we can capture tree width and rank width. For matrices, monoidal width is related to the rank. These examples suggest monoidal width as a good measure for structural complexity of processes modelled as morphisms in monoidal categories.

Recommendations

• Two-dimensional monadicity
• Monoidal structures
• Monoidal multiplexing
• scientific article; zbMATH DE number 3652410
• scientific article; zbMATH DE number 3894026
• Width of complexes of modules
• The dimension monoid of a lattice
• Monodromy

Cites work

• A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics
• An Invitation to Applied Category Theory
• Approximating clique-width and branch-width
• Compositional game theory
• Compositional reachability in Petri nets
• Decorated cospans
• Diagrammatic Semantics for Digital Circuits.
• Disintegration and Bayesian inversion via string diagrams
• Full Rank Factorization of Matrices
• Graph complexity
• Graph expressions and graph rewritings
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. X: Obstructions to tree-decomposition
• scientific article; zbMATH DE number 2125662 (Why is no real title available?)
• scientific article; zbMATH DE number 1189283 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 2222245 (Why is no real title available?)
• On non-serial dynamic programming
• Origins of the cohomology of groups
• Picturing quantum processes. A first course in quantum theory and diagrammatic reasoning
• Relating structure and power: Comonadic semantics for computational resources
• S-functions for graphs
• Spined categories: generalizing tree-width beyond graphs
• The geometry of tensor calculus. I
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The pebbling comonad in finite model theory
• Towards compositional graph theory

Cited in

(3)

• scientific article; zbMATH DE number 6666117 (Why is no real title available?)
• Monoidal Width: Capturing Rank Width
• Context-free languages of string diagrams

This page was built for publication: Monoidal Width

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