BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Luigi Santocanale

Luigi Santocanale appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Logic in Computer Sciencemath.LOmath.CTmath.COmath.RADatabasesDiscrete Mathematics

Catalog footprint

What is connected

12works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2022arXiv

Frobenius structures in star-autonomous categories

It is known that the quantale of sup-preserving maps from a complete lattice to itself is a Frobenius quantale if and only if the lattice is completely distributive. Since completely distributive lattices are the nuclear objects in the autonomous category of complete lattices and sup-preserving maps, we study the above statement in a categorical setting. We introduce the notion of Frobenius structure in an arbitrary autonomous category, generalizing that of Frobenius quantale. We prove that the monoid of endomorphisms of a nuclear object has a Frobenius structure. If the environment category is star-autonomous and has epi-mono factorizations, a variant of this theorem allows to develop an abstract phase semantics and to generalise the previous statement. Conversely, we argue that, in a star-autonomous category where the monoidal unit is a dualizing object, if the monoid of endomorphisms of an object has a Frobenius structure and the monoidal unit embeds into this object as a retract, then the object is nuclear.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Unitless Frobenius quantales

It is often stated that Frobenius quantales are necessarily unital. By taking negation as a primitive operation, we can define Frobenius quantales that may not have a unit. We develop the elementary theory of these structures and show, in particular, how to define nuclei whose quotients are Frobenius quantales. This yields a phase semantics and a representation theorem via phase quantales. Important examples of these structures arise from Raney's notion of tight Galois connection: tight endomaps of a complete lattice always form a Girard quantale which is unital if and only if the lattice is completely distributive. We give a characterisation and an enumeration of tight endomaps of the diamond lattices Mn and exemplify the Frobenius structure on these maps. By means of phase semantics, we exhibit analogous examples built up from trace class operators on an infinite dimensional Hilbert space. Finally, we argue that units cannot be properly added to Frobenius quantales: every possible extention to a unital quantale fails to preserve negations.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Dualizing sup-preserving endomaps of a complete lattice

It is argued in (Eklund et al., 2018) that the quantale [L,L] of sup-preserving endomaps of a complete lattice L is a Girard quantale exactly when L is completely distributive. We have argued in (Santocanale, 2020) that this Girard quantale structure arises from the dual quantale of inf-preserving endomaps of L via Raney's transforms and extends to a Girard quantaloid structure on the full subcategory of SLatt (the category of complete lattices and sup-preserving maps) whose objects are the completely distributive lattices. It is the goal of this talk to illustrate further this connection between the quantale structure, Raney's transforms, and complete distributivity. Raney's transforms are indeed mix maps in the isomix category SLatt and most of the theory can be developed relying on naturality of these maps. We complete then the remarks on cyclic elements of [L,L] developed in (Santocanale, 2020) by investigating its dualizing elements. We argue that if [L,L] has the structure a Frobenius quantale, that is, if it has a dualizing element, not necessarily a cyclic one, then L is once more completely distributive. It follows then from a general statement on involutive residuated lattices that there is a bijection between dualizing elements of [L,L] and automorphisms of L. Finally, we also argue that if L is finite and [L,L] is autodual, then L is distributive.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Involutive Quantaloid of Completely Distributive Lattices

Let L be a complete lattice and let Q(L) be the unital quantale of join-continuous endo-functions of L. We prove the following result: Q(L) is an involutive (that is, non-commutative cyclic $\star$-autonomous) quantale if and only if L is a completely distributive lattice. If this is the case, then the dual tensor operation corresponds, via Raney's transforms, to composition in the (dual) quantale of meet-continuous endo-functions of L. Let sLatt be the category of sup-lattices and join-continuous functions and let cdLatt be the full subcategory of sLatt whose objects are the completely distributive lattices. We argue that (i) cdLatt is itself an involutive quantaloid, and therefore it is the largest full-subcategory of sLatt with this property; (ii) cdLatt is closed under the monoidal operations of sLatt and, consequently, if Q(L) is involutive, then Q(L) is completely distributive as well.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

$μ$-Bicomplete Categories and Parity Games

For an arbitrary category, we consider the least class of functors con- taining the projections and closed under finite products, finite coproducts, parameterized initial algebras and parameterized final coalgebras, i.e. the class of functors that are definable by $μ$-terms. We call the category $μ$-bicomplete if every $μ$-term defines a functor. We provide concrete ex- amples of such categories and explicitly characterize this class of functors for the category of sets and functions. This goal is achieved through par- ity games: we associate to each game an algebraic expression and turn the game into a term of a categorical theory. We show that $μ$-terms and parity games are equivalent, meaning that they define the same property of being $μ$-bicomplete. Finally, the interpretation of a parity game in the category of sets is shown to be the set of deterministic winning strategies for a chosen player.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fixed-point elimination in the intuitionistic propositional calculus

It is a consequence of existing literature that least and greatest fixed-points of monotone polynomials on Heyting algebras-that is, the algebraic models of the Intuitionistic Propositional Calculus-always exist, even when these algebras are not complete as lattices. The reason is that these extremal fixed-points are definable by formulas of the IPC. Consequently, the $μ$-calculus based on intuitionistic logic is trivial, every $μ$-formula being equivalent to a fixed-point free formula. We give in this paper an axiomatization of least and greatest fixed-points of formulas, and an algorithm to compute a fixed-point free formula equivalent to a given $μ$-formula. The axiomatization of the greatest fixed-point is simple. The axiomatization of the least fixed-point is more complex, in particular every monotone formula converges to its least fixed-point by Kleene's iteration in a finite number of steps, but there is no uniform upper bound on the number of iterations. We extract, out of the algorithm, upper bounds for such n, depending on the size of the formula. For some formulas, we show that these upper bounds are polynomial and optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Relational lattices via duality

The natural join and the inner union combine in different ways tables of a relational database. Tropashko [18] observed that these two operations are the meet and join in a class of lattices-called the relational lattices- and proposed lattice theory as an alternative algebraic approach to databases. Aiming at query optimization, Litak et al. [12] initiated the study of the equational theory of these lattices. We carry on with this project, making use of the duality theory developed in [16]. The contributions of this paper are as follows. Let A be a set of column's names and D be a set of cell values; we characterize the dual space of the relational lattice R(D, A) by means of a generalized ultrametric space, whose elements are the functions from A to D, with the P (A)-valued distance being the Hamming one but lifted to subsets of A. We use the dual space to present an equational axiomatization of these lattices that reflects the combinatorial properties of these generalized ultrametric spaces: symmetry and pairwise completeness. Finally, we argue that these equations correspond to combinatorial properties of the dual spaces of lattices, in a technical sense analogous of correspondence theory in modal logic. In particular, this leads to an exact characterization of the finite lattices satisfying these equations.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Dual characterizations for finite lattices via correspondence theory for monotone modal logic

We establish a formal connection between algorithmic correspondence theory and certain dual characterization results for finite lattices, similar to Nation's characterization of a hierarchy of pseudovarieties of finite lattices, progressively generalizing finite distributive lattices. This formal connection is mediated through monotone modal logic. Indeed, we adapt the correspondence algorithm ALBA to the setting of monotone modal logic, and we use a certain duality-induced encoding of finite lattices as monotone neighbourhood frames to translate lattice terms into formulas in monotone modal logic.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Lattices of regular closed subsets of closure spaces

For a closure space (P,f) with f(\emptyset)=\emptyset, the closures of open subsets of P, called the regular closed subsets, form an ortholattice Reg(P,f), extending the poset Clop(P,f) of all clopen subsets. If (P,f) is a finite convex geometry, then Reg(P,f) is pseudocomplemented. The Dedekind-MacNeille completion of the poset of regions of any central hyperplane arrangement can be obtained in this way, hence it is pseudocomplemented. The lattice Reg(P,f) carries a particularly interesting structure for special types of convex geometries, that we call closure spaces of semilattice type. For finite such closure spaces, (1) Reg(P,f) satisfies an infinite collection of stronger and stronger quasi-identities, weaker than both meet- and join-semidistributivity. Nevertheless it may fail semidistributivity. (2) If Reg(P,f) is semidistributive, then it is a bounded homomorphic image of a free lattice. (3) Clop(P,f) is a lattice iff every regular closed set is clopen. The extended permutohedron R(G) on a graph G, and the extended permutohedron Reg(S) on a join-semilattice S, are both defined as lattices of regular closed sets of suitable closure spaces. While the lattice of regular closed sets is, in the semilattice context, always the Dedekind Mac-Neille completion of the poset of clopen sets, this does not always hold in the graph context, although it always does so for finite block graphs and for cycles. Furthermore, both R(G) and Reg(S) are bounded homomorphic images of free lattices.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Sublattices of associahedra and permutohedra

Grätzer asked in 1971 for a characterization of sublattices of Tamari lattices (associahedra). A natural candidate was coined by McKenzie in 1972 with the notion of a bounded homomorphic image of a free lattice---in short, bounded lattice. Urquhart proved in 1978 that every associahedron is bounded (thus so are its sublattices). Geyer conjectured in 1994 that every finite bounded lattice embeds into some associahedron. We disprove Geyer's conjecture, by introducing an infinite collection of lattice-theoretical identities that hold in every associahedron, but not in every finite bounded lattice. Among those finite counterexamples, there are the permutohedron on four letters P(4), and in fact two of its subdirectly irreducible retracts, which are Cambrian lattices of type A. For natural numbers m and n, we denote by B(m,n) the (bounded) lattice obtained by doubling a join of m atoms in an (m+n)-atom Boolean lattice. We prove that B(m,n) embeds into an associahedron iff min(m,n) is less than or equal to 1, and that B(m,n) embeds into a permutohedron iff min(m,n) is less than or equal to 2. In particular, B(3,3) cannot be embedded into any permutohedron. Nevertheless we prove that B(3,3) is a homomorphic image of a sublattice of the permutohedron on 12 letters.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The extended permutohedron on a transitive binary relation

For a given transitive binary relation e on a set E, the transitive closures of open (i.e., co-transitive in e) sets, called the regular closed subsets, form an ortholattice Reg(e), the extended permutohedron on e. This construction, which contains the poset Clop(e) of all clopen sets, is a common generalization of known notions such as the generalized permutohedron on a partially ordered set on the one hand, and the bipartition lattice on a set on the other hand. We obtain a precise description of the completely join-irreducible (resp., completely meet-irreducible) elements of Reg(e) and the arrow relations between them. In particular, we prove that (1) Reg(e) is the Dedekind-MacNeille completion of the poset Clop(e); (2) Every open subset of e is a set-theoretic union of completely join-irreducible clopen subsets of e; (3) Clop(e) is a lattice iiff every regular closed subset of e is clopen, iff e contains no "square" configuration, iff Reg(e)=Clop(e); (4) If e is finite, then Reg(e) is pseudocomplemented iff it is semidistributive, iff it is a bounded homomorphic image of a free lattice, iff e is a disjoint sum of antisymmetric transitive relations and two-element full relations. We illustrate the strength of our results by proving that, for n greater than or equal to 3, the congruence lattice of the lattice Bip(n) of all bipartitions of an n-element set is obtained by adding a new top element to a Boolean lattice with n2^{n-1} atoms. We also determine the factors of the minimal subdirect decomposition of Bip(n).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Varieties of lattices with geometric descriptions

A lattice L is spatial if every element of L is a join of completely join-irreducible elements of L (points), and strongly spatial if it is spatial and the minimal coverings of completely join-irreducible elements are well-behaved. Herrmann, Pickering, and Roddy proved in 1994 that every modular lattice can be embedded, within its variety, into an algebraic and spatial lattice. We extend this result to n-distributive lattices, for fixed n. We deduce that the variety of all n-distributive lattices is generated by its finite members, thus it has a decidable word problem. This solves two problems stated by Huhn in 1985. We prove that every modular (resp., n-distributive) lattice embeds within its variety into some strongly spatial lattice. Every lattice which is either algebraic modular spatial or bi-algebraic is strongly spatial. We also construct a lattice that cannot be embedded, within its variety, into any algebraic and spatial lattice. This lattice has a least and a largest element, and it generates a locally finite, join-semidistributive variety.

0 citations0 reviewsNo code linkedOpen access