Search

The applications of the partial fraction decomposition in control and systems engineering are several. In this letter, we propose a new interpretation of residues in the partial fraction decomposition, which is employed for the following purposes: to address the pole sensitivity problem, namely to study the speed of variation of the system poles when the control parameter changes and when the system is subject to parameters variations, as well as to propose a new algorithm for the construction of the root locus. The new algorithm is proven to be more efficient in terms of execution time than the dedicated MATLAB function, while providing the same output results.

(Symmetric) monoidal theories encapsulate presentations by generators and equations for (symmetric) monoidal categories. Terms of a monoidal theory are typically represented pictorially using string diagrams. In this work we introduce and study a quantitative version of monoidal theories, where instead of equality one may reason more abstractly about distance between string diagrams. This is in analogy with quantitative algebraic theories by Mardare et al., but developed in a monoidal rather than cartesian setting. Our framework paves the way for a quantitative analysis of string diagrammatic calculi for resource-sensitive processes, as found e.g. in quantum theory, machine learning, cryptography, and digital circuit theory.

We provide a category theoretical framework capturing two approaches to graph-based models of chemistry: formal reactions and disconnection rules. We model a translation from the latter to the former as a functor, which is faithful, and full up to isomorphism. This allows us to state, as our main result, that the disconnection rules are sound, complete and universal with respect to the reactions. Concretely, this means that every reaction can be decomposed into a sequence of disconnection rules in an essentially unique way. This provides a uniform way to store reaction data, and gives an algorithmic interface between (forward) reaction prediction and (backward) reaction search or retrosynthesis., Comment: 22 pages, 6 figures. Extended version of an article to be published in the proceedings of ICTAC 2024

Modeling physical systems is an essential skill for a control engineer, since it enables to achieve a deep understanding of their dynamic behavior and, consequently, the development of effective control strategies. The first part of this article provides a tutorial description of the fundamental principles and properties of the Power-Oriented Graphs (POG) modeling technique. Various case studies in different energetic domains are then presented to consolidate the fundamental principles, each highlighting different features of the POG modeling technique. The latter is then compared with the other two main graphical modeling techniques available in the literature, namely Bond Graph (BG) and Energetic Macroscopic Representation (EMR). The second part of this article assumes once again a tutorial nature, in order to introduce the new Fast Modeling POG (FMPOG) procedure. The FMPOG, which operates in the POG framework, is a methodical step-by-step procedure that enables the readers to quickly derive the power-oriented graphical model of physical systems starting from their schematics. From the power-oriented graphical model, the state-space model can then be directly determined. To ensure the FMPOG procedure is easily usable by the entire community, we apply it to three examples in different energetic domains in this article, guiding the reader step-by-step through the derivation of the physical systems models. A freely available Matlab/Simulink program is provided in a repository, allowing the users to automatically apply the FMPOG procedure to various classes of physical systems. This program allows to convert the physical systems schematics into the corresponding POG block schemes and, ultimately, into the state-space mathematical models.

We develop a categorical framework for reasoning about abstract properties of differentiation, based on the theory of fibrations. Our work encompasses the first-order fragments of several existing categorical structures for differentiation, including cartesian differential categories, generalised cartesian differential categories, tangent categories, as well as the versions of these categories axiomatising reverse derivatives. We explain uniformly and concisely the requirements expressed by these structures, using sections of suitable fibrations as unifying concept. Our perspective sheds light on their similarities and differences, as well as simplifying certain constructions from the literature.

We introduce a sound and complete equational theory capturing equivalence of discrete probabilistic programs, that is, programs extended with primitives for Bernoulli distributions and conditioning, to model distributions over finite sets of events. To do so, we translate these programs into a graphical syntax of probabilistic circuits, formalised as string diagrams, the two-dimensional syntax of symmetric monoidal categories. We then prove a first completeness result for the equational theory of the conditioning-free fragment of our syntax. Finally, we extend this result to a complete equational theory for the entire language. Note these developments are also of interest for the development of probability theory in Markov categories: our first result gives a presentation by generators and equations of the category of Markov kernels, restricted to objects that are powers of the two-elements set., Comment: 41 pages

We develop a learning algorithm for closed signal flow graphs - a graphical model of signal transducers. The algorithm relies on the correspondence between closed signal flow graphs and weighted finite automata on a singleton alphabet. We demonstrate that this procedure results in a genuine reduction of complexity: our algorithm fares better than existing learning algorithms for weighted automata restricted to the case of a singleton alphabet., Comment: 13 pages, 6 figures. An extended abstract for Learning and Automata workshop (LearnAut 2024)

Electrical power conversions are common in a large variety of engineering applications. With reference to AC/DC and DC/AC power conversions, a strong research interest resides in multilevel converters, thanks to the many advantages they provide over standard two-level converters. In this paper, we first provide a power-oriented model of Modular Multilevel Converters (MMCs), followed by a detailed harmonic analysis. The model is given in the form of a block scheme that can be directly implemented in the Matlab/Simulink environment. The performed harmonic analysis gives a deep and exact understanding of the different terms affecting the evolution of the voltage trajectories in the upper and lower arms of the converter. Next, we propose a new model-based adaptive control scheme for MMCs. The proposed control allows to determine the optimal average capacitor voltages reference in real-time, thus allowing to properly track the desired load current while minimizing the harmonic content in the generated load current itself.

We propose a categorical semantics for machine learning algorithms in terms of lenses, parametric maps, and reverse derivative categories. This foundation provides a powerful explanatory and unifying framework: it encompasses a variety of gradient descent algorithms such as ADAM, AdaGrad, and Nesterov momentum, as well as a variety of loss functions such as MSE and Softmax cross-entropy, and different architectures, shedding new light on their similarities and differences. Furthermore, our approach to learning has examples generalising beyond the familiar continuous domains (modelled in categories of smooth maps) and can be realised in the discrete setting of Boolean and polynomial circuits. We demonstrate the practical significance of our framework with an implementation in Python., Comment: arXiv admin note: text overlap with arXiv:2403.13001

We introduce Graphical Quadratic Algebra (GQA), a string diagrammatic calculus extending the language of Graphical Affine Algebra with a new generator characterised by invariance under rotation matrices. We show that GQA is a sound and complete axiomatisation for three different models: quadratic relations, which are a compositional formalism for least-squares problems, Gaussian stochastic processes, and Gaussian stochastic processes extended with non-determinisms. The equational theory of GQA sheds light on the connections between these perspectives, giving an algebraic interpretation to the interplay of stochastic behaviour, relational behaviour, non-determinism, and conditioning. As applications, we discuss various case studies, including linear regression, probabilistic programming, and electrical circuits with realistic (noisy) components.

The logic of Dependence and Independence Bunched Implications (DIBI) is a logic to reason about conditional independence (CI); for instance, DIBI formulas can characterise CI in probability distributions and relational databases, using the probabilistic and relational DIBI models, respectively. Despite the similarity of the probabilistic and relational models, a uniform, more abstract account remains unsolved. The laborious case-by-case verification of the frame conditions required for constructing new models also calls for such a treatment. In this paper, we develop an abstract framework for systematically constructing DIBI models, using category theory as the unifying mathematical language. In particular, we use string diagrams -- a graphical presentation of monoidal categories -- to give a uniform definition of the parallel composition and subkernel relation in DIBI models. Our approach not only generalises known models, but also yields new models of interest and reduces properties of DIBI models to structures in the underlying categories. Furthermore, our categorical framework enables a logical notion of CI, in terms of the satisfaction of specific DIBI formulas. We compare it with string diagrammatic approaches to CI and show that it is an extension of string diagrammatic CI under reasonable conditions., Comment: 33 pages

We introduce a mathematical framework for retrosynthetic analysis, an important research method in synthetic chemistry. Our approach represents molecules and their interaction using string diagrams in layered props - a recently introduced categorical model for partial explanations in scientific reasoning. Such principled approach allows one to model features currently not available in automated retrosynthesis tools, such as chirality, reaction environment and protection-deprotection steps., Comment: 22 pages, 3 figures

This tutorial gives an advanced introduction to string diagrams and graph languages for higher-order computation. The subject matter develops in a principled way, starting from the two dimensional syntax of key categorical concepts such as functors, adjunctions, and strictification, and leading up to Cartesian Closed Categories, the core mathematical model of the lambda calculus and of functional programming languages. This methodology inverts the usual approach of proceeding from syntax to a categorical interpretation, by rationally reconstructing a syntax from the categorical model. The result is a graph syntax -- more precisely, a hierarchical hypergraph syntax -- which in many ways is shown to be an improvement over the conventional linear term syntax. The rest of the tutorial focuses on applications of interest to programming languages: operational semantics, general frameworks for type inference, and complex whole-program transformations such as closure conversion and automatic differentiation.

This document is an elementary introduction to string diagrams. It takes a computer science perspective: rather than using category theory as a starting point, we build on intuitions from formal language theory, treating string diagrams as a syntax with its semantics. After the basic theory, pointers are provided to contemporary applications of string diagrams in various fields of science.

We give parallel algorithms for string diagrams represented as structured cospans of ACSets. Specifically, we give linear (sequential) and logarithmic (parallel) time algorithms for composition, tensor product, construction of diagrams from arbitrary $\Sigma$-terms, and application of functors to diagrams. Our datastructure can represent morphisms of both the free symmetric monoidal category over an arbitrary signature as well as those with a chosen Special Frobenius structure. We show how this additional (hypergraph) structure can be used to map diagrams to diagrams of optics. This leads to a case study in which we define an algorithm for efficiently computing symbolic representations of gradient-based learners based on reverse derivatives. The work we present here is intended to be useful as a general purpose datastructure. Implementation requires only integer arrays and well-known algorithms, and is data-parallel by constuction. We therefore expect it to be applicable to a wide variety of settings, including embedded and parallel hardware and low-level languages.

We develop a fully diagrammatic approach to finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. In this setting, we are able to provide a complete equational theory for language equivalence, with two notable features. First, the proposed axiomatisation is finite. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks., Comment: arXiv admin note: text overlap with arXiv:2009.14576

We propose a calculus of string diagrams to reason about satisfiability of Boolean formulas, and prove it to be sound and complete. We then showcase our calculus in a few case studies. First, we consider SAT-solving. Second, we consider Horn clauses, which leads us to a new decision method for propositional logic programs equivalence under Herbrand model semantics.

We propose a categorical framework to reason about scientific explanations: descriptions of a phenomenon meant to translate it into simpler terms, or into a context that has been already understood. Our motivating examples come from systems biology, electrical circuit theory, and concurrency. We demonstrate how three explanatory models in these seemingly diverse areas can be all understood uniformly via a graphical calculus of layered props. Layered props allow for a compact visual presentation of the same phenomenon at different levels of precision, as well as the translation between these levels. Notably, our approach allows for partial explanations, that is, for translating just one part of a diagram while keeping the rest of the diagram untouched. Furthermore, our approach paves the way for formal reasoning about counterfactual models in systems biology., Comment: In Proceedings ACT 2022, arXiv:2307.15519

String diagrams are pictorial representations for morphisms of symmetric monoidal categories. They constitute an intuitive and expressive graphical syntax, which has found application in a very diverse range of fields including concurrency theory, quantum computing, control theory, machine learning, linguistics, and digital circuits. Rewriting theory for string diagrams relies on a combinatorial interpretation as double-pushout rewriting of certain hypergraphs. As previously studied, there is a `tension' in this interpretation: in order to make it sound and complete, we either need to add structure on string diagrams (in particular, Frobenius algebra structure) or pose restrictions on double-pushout rewriting (resulting in 'convex' rewriting). From the string diagram viewpoint, imposing a full Frobenius structure may not always be natural or desirable in applications, which motivates our study of a weaker requirement: commutative monoid structure. In this work we characterise string diagram rewriting modulo commutative monoid equations, via a sound and complete interpretation in a suitable notion of double-pushout rewriting of hypergraphs., Comment: 28 pages (including appendix). Journal version replacing the previous conference paper

Reverse derivative categories (RDCs) have recently been shown to be a suitable semantic framework for studying machine learning algorithms. Whereas emphasis has been put on training methodologies, less attention has been devoted to particular \emph{model classes}: the concrete categories whose morphisms represent machine learning models. In this paper we study presentations by generators and equations of classes of RDCs. In particular, we propose \emph{polynomial circuits} as a suitable machine learning model. We give an axiomatisation for these circuits and prove a functional completeness result. Finally, we discuss the use of polynomial circuits over specific semirings to perform machine learning with discrete values.

Whereas string diagrams for strict monoidal categories are well understood, and have found application in several fields of Computer Science, graphical formalisms for non-strict monoidal categories are far less studied. In this paper, we provide a presentation by generators and relations of string diagrams for non-strict monoidal categories, and show how this construction can handle applications in domains such as digital circuits and programming languages. We prove the correctness of our construction, which yields a novel proof of Mac Lane's strictness theorem. This in turn leads to an elementary graphical proof of Mac Lane's coherence theorem, and in particular allows for the inductive construction of the canonical isomorphisms in a monoidal category.

In this paper we address the problem of proving confluence for string diagram rewriting, which was previously shown to be characterised combinatorically as double-pushout rewriting with interfaces (DPOI) on (labelled) hypergraphs. For standard DPO rewriting without interfaces, confluence for terminating rewrite systems is, in general, undecidable. Nevertheless, we show here that confluence for DPOI, and hence string diagram rewriting, is decidable. We apply this result to give effective procedures for deciding local confluence of symmetric monoidal theories with and without Frobenius structure by critical pair analysis. For the latter, we introduce the new notion of path joinability for critical pairs, which enables finitely many joins of a critical pair to be lifted to an arbitrary context in spite of the strong non-local constraints placed on rewriting in a generic symmetric monoidal theory.

We enhance the calculus of string diagrams for monoidal categories with hierarchical features in order to capture closed monoidal (and cartesian closed) structure. Using this new syntax we formulate an automatic differentiation algorithm for (applied) simply typed lambda calculus in the style of [Pearlmutter and Siskind 2008] and we prove for the first time its soundness. To give an efficient yet principled implementation of the AD algorithm we define a sound and complete representation of hierarchical string diagrams as a class of hierarchical hypergraphs we call hypernets.

String diagrams are an increasingly popular algebraic language for the analysis of graphical models of computations across different research fields. Whereas string diagrams have been thoroughly studied as semantic structures, much less attention has been given to their algorithmic properties, and efficient implementations of diagrammatic reasoning are almost an unexplored subject. This work intends to be a contribution in such a direction. We introduce a data structure representing string diagrams in terms of adjacency matrices. This encoding has the key advantage of providing simple and efficient algorithms for composition and tensor product of diagrams. We demonstrate its effectiveness by showing that the complexity of the two operations is linear in the size of string diagrams. Also, as our approach is based on basic linear algebraic operations, we can take advantage of heavily optimised implementations, which we use to measure performances of string diagrammatic operations via several benchmarks., Comment: In Proceedings ACT 2021, arXiv:2211.01102