Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSemialgebras and Weak Distributive Laws
149
0
0.0
(
0
)
Added by
Ralph Sarkis
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Daniela Petri{c{s}}an
Ask ChatGPT about the research
No Arabic abstract
Motivated by recent work on weak distributive laws and their applications to coalgebraic semantics, we investigate the algebraic nature of semialgebras for a monad. These are algebras for the underlying functor of the monad subject to the associativity axiom alone-the unit axiom from the definition of an Eilenberg-Moore algebras is dropped. We prove that if the underlying category has coproducts, then semialgebras for a monad M are in fact the Eilenberg-Moore algebras for a suitable monad structure on the functor id + M , which we call the semifree monad M^s. We also provide concrete algebraic presentations for semialgebras for the maybe monad, the semigroup monad and the finite distribution monad. A second contribution is characterizing the weak distributive laws of the form M T $Rightarrow$ T M as strong distributive laws M^s T $Rightarrow$ T M^s subject to an additional condition.
rate research
Read More
The Vietoris monad on the category of compact Hausdorff spaces is a topological analogue of the power-set monad on the category of sets. Exploiting Manes characterisation of the compact Hausdorff spaces as algebras for the ultrafilter monad on sets, we give precise form to the above analogy by exhibiting the Vietoris monad as induced by a weak distributive law, in the sense of Bohm, of the power-set monad over the ultrafilter monad.
Modern distributed systems often rely on so called weakly-consistent databases, which achieve scalability by sacrificing the consistency guarantee of distributed transaction processing. Such databases have been formalised in two different styles, one based on abstract executions and the other based on dependency graphs. The choice between these styles has been made according to intended applications: the former has been used to specify and verify the implementation of these databases, and the latter to prove properties of programs running on top of the databases. In this paper, we present a set of novel algebraic laws (i.e. inequations) that connect these two styles of specifications; the laws relate binary relations used in a specification based on abstract executions, to those used in a specification based on dependency graphs. We then show that this algebraic connection gives rise to so called robustness criteria, conditions which ensures that a program running on top of a weakly-consistent database does not exhibit anomalous behaviours due to this weak consistency. These criteria make it easy to reason about programs running on top of these databases, and may become a basis for dynamic or static program analyses. For a certain class of consistency models specifications, we prove a full abstraction result that connects the two styles of specifications.
We introduce a simple extension of the $lambda$-calculus with pairs---called the distributive $lambda$-calculus---obtained by adding a computational interpretation of the valid distributivity isomorphism $A Rightarrow (Bwedge C) equiv (ARightarrow B) wedge (ARightarrow C)$ of simple types. We study the calculus both as an untyped and as a simply typed setting. Key features of the untyped calculus are confluence, the absence of clashes of constructs, that is, evaluation never gets stuck, and a leftmost-outermost normalization theorem, obtained with straightforward proofs. With respect to simple types, we show that the new rules satisfy subject reduction if types are considered up to the distributivity isomorphism. The main result is strong normalization for simple types up to distributivity. The proof is a smooth variation over the one for the $lambda$-calculus with pairs and simple types.
In this paper, we introduce and investigate emph{bisemialgebras}andemph{ Hopf semialgebras} over commutative semirings. We generalize to the semialgebraic context several results on bialgebras and Hopf algebras over rings including the main reconstruction theorems and the emph{Fundamental Theorem of Hopf Algebras}. We also provide a notion of emph{quantum monoids} as Hopf semialgebras which are neither commutative nor cocommutative; this extends the Hopf algebraic notion of a quantum group. The generalization to the semialgebraic context is neither trivial nor straightforward due to the non-additive nature of the base category of Abelian monoids which is also neither Puppe-exact nor homological and does not necessarily have enough injectives.
In 2009, Ghani, Hancock and Pattinson gave a coalgebraic characterisation of stream processors $A^mathbb{N} to B^mathbb{N}$ drawing on ideas of Brouwerian constructivism. Their stream processors have an intensional character; in this paper, we give a corresponding coalgebraic characterisation of extensional stream processors, i.e., the set of continuous functions $A^mathbb{N} to B^mathbb{N}$. Our account sites both our result and that of op. cit. within the apparatus of comodels for algebraic effects originating with Power-Shkaravska.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
