Authors: Došen, Kosta 
Petrić, Zoran 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Syntax for split preorders
Journal: Annals of Pure and Applied Logic
Volume: 164
Issue: 4
First page: 443
Last page: 481
Issue Date: 1-Apr-2013
Rank: M22
ISSN: 0168-0072
DOI: 10.1016/j.apal.2012.10.008
A split preorder is a preordering relation on the disjoint union of two sets, which function as source and target when one composes split preorders. The paper presents by generators and equations the category SplPre, whose arrows are the split preorders on the disjoint union of two finite ordinals. The same is done for the subcategory Gen of SplPre, whose arrows are equivalence relations, and for the category Rel, whose arrows are the binary relations between finite ordinals, and which has an isomorphic image within SplPre by a map that preserves composition, but not identity arrows. It was shown previously that SplPre and Gen have an isomorphic representation in Rel in the style of Brauer.The syntactical presentation of Gen and Rel in this paper exhibits the particular Frobenius algebra structure of Gen and the particular bialgebraic structure of Rel, the latter structure being built upon the former structure in SplPre. This points towards algebraic modelling of various categories motivated by logic, and related categories, for which one can establish coherence with respect Rel and Gen. It also sheds light on the relationship between the notions of Frobenius algebra and bialgebra. The completeness of the syntactical presentations is proved via normal forms, with the normal form for SplPre and Gen being in some sense orthogonal to the composition-free, i.e. cut-free, normal form for Rel. The paper ends by showing that the assumptions for the algebraic structures of SplPre, Gen and Rel cannot be extended with new equations without falling into triviality.
Keywords: Bialgebra | Comonad | Frobenius algebra | Monad | Normal form | Split preorder
Publisher: Elsevier
Project: Representations of logical structures and formal languages and their application in computing 

Show full item record


checked on Jul 19, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.