The Experts below are selected from a list of 8970 Experts worldwide ranked by ideXlab platform
Noam Zeilberger - One of the best experts on this subject based on the ideXlab platform.
-
The Sequent Calculus of Skew Monoidal Categories.
arXiv: Logic in Computer Science, 2020Co-Authors: Tarmo Uustalu, Niccolò Veltri, Noam ZeilbergerAbstract:Szlachanyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a Sequent Calculus for skew monoidal categories, building on the recent formulation by one of the authors of a Sequent Calculus for the Tamari order (skew semigroup categories). In this Calculus, antecedents consist of a stoup (an optional formula) followed by a context, and the connectives behave like in the standard monoidal Sequent Calculus except that the left rules may only be applied in stoup position. We prove that this Calculus is sound and complete with respect to existence of maps in the free skew monoidal category, and moreover that it captures equality of maps once a suitable equivalence relation is imposed on derivations. We then identify a subsystem of focused derivations and establish that it contains exactly one canonical representative from each equivalence class. This coherence theorem leads directly to simple procedures for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates. Finally, and in the spirit of Lambek's work, we describe the close connection between this proof-theoretic analysis and Bourke and Lack's recent characterization of skew monoidal categories as left representable skew multicategories. We have formalized this development in the dependently typed programming language Agda.
-
the Sequent Calculus of skew monoidal categories
Electronic Notes in Theoretical Computer Science, 2018Co-Authors: Tarmo Uustalu, Niccolò Veltri, Noam ZeilbergerAbstract:Abstract Szlachanyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a Sequent Calculus for skew monoidal categories, building on the recent formulation by one of the authors of a Sequent Calculus for the Tamari order (skew semigroup categories). In this Calculus, antecedents consist of a stoup (an optional formula) followed by a context (a list of formulae), and the connectives unit and tensor behave like in intuitionistic non-commutative linear logic (the logic of monoidal categories) except that the left rules may only be applied in stoup position. We show the admissibility of two forms cut (stoup cut and context cut), and prove the Calculus sound and complete with respect to existence of maps in the free skew monoidal category. We then introduce an equivalence relation on Sequent Calculus derivations and prove that there is a one-to-one correspondence between equivalence classes of derivations and maps in the free skew monoidal category. Finally, we identify a subCalculus of focused derivations, and establish that it contains exactly one canonical representative from each equivalence class. As an end result, we obtain simple algorithms both for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates, in particular, for deciding whether there is a map. We have formalized this development in the dependently typed programming language Agda.
-
A Sequent Calculus for a semi-associative law
arXiv: Logic, 2018Co-Authors: Noam ZeilbergerAbstract:We introduce a Sequent Calculus with a simple restriction of Lambek's product rules that precisely captures the classical Tamari order, i.e., the partial order on fully-bracketed words (equivalently, binary trees) induced by a semi-associative law (equivalently, right rotation). We establish a focusing property for this Sequent Calculus (a strengthening of cut-elimination), which yields the following coherence theorem: every valid entailment in the Tamari order has exactly one focused derivation. We then describe two main applications of the coherence theorem, including: 1. A new proof of the lattice property for the Tamari order, and 2. A new proof of the Tutte-Chapoton formula for the number of intervals in the Tamari lattice $Y_n$.
-
MFPS - The Sequent Calculus of Skew Monoidal Categories
Electronic Notes in Theoretical Computer Science, 2018Co-Authors: Tarmo Uustalu, Niccolò Veltri, Noam ZeilbergerAbstract:Abstract Szlachanyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a Sequent Calculus for skew monoidal categories, building on the recent formulation by one of the authors of a Sequent Calculus for the Tamari order (skew semigroup categories). In this Calculus, antecedents consist of a stoup (an optional formula) followed by a context (a list of formulae), and the connectives unit and tensor behave like in intuitionistic non-commutative linear logic (the logic of monoidal categories) except that the left rules may only be applied in stoup position. We show the admissibility of two forms cut (stoup cut and context cut), and prove the Calculus sound and complete with respect to existence of maps in the free skew monoidal category. We then introduce an equivalence relation on Sequent Calculus derivations and prove that there is a one-to-one correspondence between equivalence classes of derivations and maps in the free skew monoidal category. Finally, we identify a subCalculus of focused derivations, and establish that it contains exactly one canonical representative from each equivalence class. As an end result, we obtain simple algorithms both for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates, in particular, for deciding whether there is a map. We have formalized this development in the dependently typed programming language Agda.
-
a Sequent Calculus for a semi associative law
Logical Methods in Computer Science, 2017Co-Authors: Noam ZeilbergerAbstract:We introduce a Sequent Calculus with a simple restriction of Lambek's product rules that precisely captures the classical Tamari order, i.e., the partial order on fully-bracketed words (equivalently, binary trees) induced by a semi-associative law (equivalently, tree rotation). We establish a focusing property for this Sequent Calculus (a strengthening of cut-elimination), which yields the following coherence theorem: every valid entailment in the Tamari order has exactly one focused derivation. One combinatorial application of this coherence theorem is a new proof of the Tutte-Chapoton formula for the number of intervals in the Tamari lattice Y_n. Elsewhere, we have also used the Sequent Calculus and the coherence theorem to build a surprising bijection between intervals of the Tamari order and a natural fragment of lambda Calculus, consisting of the beta-normal planar lambda terms with no closed proper subterms.
Francesca Poggiolesi - One of the best experts on this subject based on the ideXlab platform.
-
What Is a Good Sequent Calculus
Gentzen Calculi for Modal Propositional Logic, 2010Co-Authors: Francesca PoggiolesiAbstract:In his doctoral thesis of 1935, the young and brilliant student Gerhard Gentzen introduced what is today known as the Sequent Calculus. Over the last eighty years the Sequent Calculus has been the central interest of several illustrious proof theorists. This has given rise to a broad literature and numerous results. Nevertheless, there still are problems and issues concerning the Sequent Calculus that need to be further developed and tackled. Amongst these, our attention has been attracted by one question that can be expressed as follows: what is a good Sequent Calculus? What, in other words, are the properties that a Sequent Calculus needs to satisfy to be considered good? The aim of this chapter is to attempt to find an answer to this question.
-
Comparing the Different Generalisations of the Sequent Calculus
Gentzen Calculi for Modal Propositional Logic, 2010Co-Authors: Francesca PoggiolesiAbstract:We have thus introduced the main generalisations of the Sequent Calculus for modal propositional logic. Their analysis may be further developed, in particular from the perspective of deepening our understanding of the links between these generalisations. Wansing [147, p. 171] stresses the importance of this issue:
-
A Contraction-free and Cut-free Sequent Calculus for Propositional Dynamic Logic
2010Co-Authors: Brian Hill, Francesca PoggiolesiAbstract:In this paper we present a Sequent Calculus for propositional dynamic logic built using an enriched version of the tree-hyperSequent method and including an infinitary rule for the iteration operator. We prove that this Sequent Calculus is theoremwise equivalent to the corresponding Hilbert-style system, and that it is contraction-free and cut-free. All results are proved in a purely syntactic way.
-
A PURELY SYNTACTIC AND CUT-FREE Sequent Calculus FOR THE MODAL LOGIC OF PROVABILITY
The Review of Symbolic Logic, 2009Co-Authors: Francesca PoggiolesiAbstract:In this paper we present a Sequent Calculus for the modal propositional logic GL (the logic of provability) obtained by means of the tree-hyperSequent method, a method in which the metalinguistic strength of hyperSequents is improved, so that we can simulate trees shapes. We prove that this Sequent Calculus is sound and complete with respect to the Hilbert-style system GL, that it is contraction free and cut free and that its logical and modal rules are invertible. No explicit semantic element is used in the Sequent Calculus and all the results are proved in a purely syntactic way.
-
A CUT-FREE SIMPLE Sequent Calculus FOR MODAL LOGIC S5
The Review of Symbolic Logic, 2008Co-Authors: Francesca PoggiolesiAbstract:In this paper, we present a simple Sequent Calculus for the modal propositional logic S5. We prove that this Sequent Calculus is theoremwise equivalent to the Hilbert-style system S5, that it is contraction-free and cut-free, and finally that it is decidable. All results are proved in a purely syntactic way.
Nicola Olivetti - One of the best experts on this subject based on the ideXlab platform.
-
a Sequent Calculus for skeptical default logic
Theorem Proving with Analytic Tableaux and Related Methods, 1997Co-Authors: Piero A. Bonatti, Nicola OlivettiAbstract:In this paper, we contribute to the proof-theory of Reiter's Default Logic by introducing a Sequent Calculus for skeptical reasoning. The main features of this Calculus are simplicity and regularity, and the fact that proofs can be surprisingly concise and, in many cases, involve only a small part of the default theory.
-
CSL - A Sequent Calculus for Circumscription
Computer Science Logic, 1997Co-Authors: Piero A. Bonatti, Nicola OlivettiAbstract:In this paper, we introduce a Sequent Calculus CIRC for propositional Circumscription. This work is part of a larger project, aiming at a uniform proof-theoretic reconstruction of the major families of non-monotonic logics. Among the novelties of the Calculus, we mention that CIRC is analytic and comprises an axiomatic rejection method, which allows for a fully detailed formalization of the nonmonotonic aspects of inference.
-
TABLEAUX - A Sequent Calculus for Skeptical Default Logic
Lecture Notes in Computer Science, 1997Co-Authors: Piero A. Bonatti, Nicola OlivettiAbstract:In this paper, we contribute to the proof-theory of Reiter's Default Logic by introducing a Sequent Calculus for skeptical reasoning. The main features of this Calculus are simplicity and regularity, and the fact that proofs can be surprisingly concise and, in many cases, involve only a small part of the default theory.
Katsuhiko Sano - One of the best experts on this subject based on the ideXlab platform.
-
axiomatizing epistemic logic of friendship via tree Sequent Calculus
International Workshop on Logic Rationality and Interaction, 2017Co-Authors: Katsuhiko SanoAbstract:This paper positively solves an open problem if it is possible to provide a Hilbert system to Epistemic Logic of Friendship (EFL) by Seligman, Girard and Liu. To find a Hilbert system, we first introduce a sound, complete and cut-free tree (or nested) Sequent Calculus for EFL, which is an integrated combination of Seligman’s Sequent Calculus for basic hybrid logic and a tree Sequent Calculus for modal logic. Then we translate a tree Sequent into an ordinary formula to specify a Hilbert system of EFL and finally show that our Hilbert system is sound and complete for an intended two-dimensional semantics.
-
LORI - Axiomatizing Epistemic Logic of Friendship via Tree Sequent Calculus
Logic Rationality and Interaction, 2017Co-Authors: Katsuhiko SanoAbstract:This paper positively solves an open problem if it is possible to provide a Hilbert system to Epistemic Logic of Friendship (EFL) by Seligman, Girard and Liu. To find a Hilbert system, we first introduce a sound, complete and cut-free tree (or nested) Sequent Calculus for EFL, which is an integrated combination of Seligman’s Sequent Calculus for basic hybrid logic and a tree Sequent Calculus for modal logic. Then we translate a tree Sequent into an ordinary formula to specify a Hilbert system of EFL and finally show that our Hilbert system is sound and complete for an intended two-dimensional semantics.
-
Axiomatizing Epistemic Logic of Friendship via Tree Sequent Calculus
arXiv: Logic in Computer Science, 2017Co-Authors: Katsuhiko SanoAbstract:This paper positively solves an open problem if it is possible to provide a Hilbert system to Epistemic Logic of Friendship (EFL) by Seligman, Girard and Liu. To find a Hilbert system, we first introduce a sound, complete and cut-free tree (or nested) Sequent Calculus for EFL, which is an integrated combination of Seligman's Sequent Calculus for basic hybrid logic and a tree Sequent Calculus for modal logic. Then we translate a tree Sequent into an ordinary formula to specify a Hilbert system of EFL and finally show that our Hilbert system is sound and complete for the intended two-dimensional semantics.
-
sound and complete tree Sequent Calculus for inquisitive logic
Workshop on Logic Language Information and Computation, 2009Co-Authors: Katsuhiko SanoAbstract:We introduce a tree-Sequent Calculus for inquisitive logic (Groenendijk 2008) as a special form of labelled deductive system (Gabbay 1996). In particular, we establish that (i) our tree-Sequent Calculus is sound and complete with respect to Groenendijk's inquisitive semantics and that (ii) our tree-Sequent Calculus is decidable and enjoys cut-elimination theorem. (ii) is semantically revealed by our argument for (i). The key idea which allows us to obtain these results is as follows: In Groenendijk's inquisitive semantics, a formula of propositional logic is evaluated against a pair of worlds on a model. Given the appropriate pre-order on the set of such pairs, any inquisitive model can be regarded as a Kripke model for intuitionistic logic. This representation enables us to connect inquisitive semantics with the tree-Sequent technique for non-classical logics (Kashima 1999).
-
WoLLIC - Sound and Complete Tree-Sequent Calculus for Inquisitive Logic
Logic Language Information and Computation, 2009Co-Authors: Katsuhiko SanoAbstract:We introduce a tree-Sequent Calculus for inquisitive logic (Groenendijk 2008) as a special form of labelled deductive system (Gabbay 1996). In particular, we establish that (i) our tree-Sequent Calculus is sound and complete with respect to Groenendijk's inquisitive semantics and that (ii) our tree-Sequent Calculus is decidable and enjoys cut-elimination theorem. (ii) is semantically revealed by our argument for (i). The key idea which allows us to obtain these results is as follows: In Groenendijk's inquisitive semantics, a formula of propositional logic is evaluated against a pair of worlds on a model. Given the appropriate pre-order on the set of such pairs, any inquisitive model can be regarded as a Kripke model for intuitionistic logic. This representation enables us to connect inquisitive semantics with the tree-Sequent technique for non-classical logics (Kashima 1999).
Tarmo Uustalu - One of the best experts on this subject based on the ideXlab platform.
-
The Sequent Calculus of Skew Monoidal Categories.
arXiv: Logic in Computer Science, 2020Co-Authors: Tarmo Uustalu, Niccolò Veltri, Noam ZeilbergerAbstract:Szlachanyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a Sequent Calculus for skew monoidal categories, building on the recent formulation by one of the authors of a Sequent Calculus for the Tamari order (skew semigroup categories). In this Calculus, antecedents consist of a stoup (an optional formula) followed by a context, and the connectives behave like in the standard monoidal Sequent Calculus except that the left rules may only be applied in stoup position. We prove that this Calculus is sound and complete with respect to existence of maps in the free skew monoidal category, and moreover that it captures equality of maps once a suitable equivalence relation is imposed on derivations. We then identify a subsystem of focused derivations and establish that it contains exactly one canonical representative from each equivalence class. This coherence theorem leads directly to simple procedures for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates. Finally, and in the spirit of Lambek's work, we describe the close connection between this proof-theoretic analysis and Bourke and Lack's recent characterization of skew monoidal categories as left representable skew multicategories. We have formalized this development in the dependently typed programming language Agda.
-
the Sequent Calculus of skew monoidal categories
Electronic Notes in Theoretical Computer Science, 2018Co-Authors: Tarmo Uustalu, Niccolò Veltri, Noam ZeilbergerAbstract:Abstract Szlachanyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a Sequent Calculus for skew monoidal categories, building on the recent formulation by one of the authors of a Sequent Calculus for the Tamari order (skew semigroup categories). In this Calculus, antecedents consist of a stoup (an optional formula) followed by a context (a list of formulae), and the connectives unit and tensor behave like in intuitionistic non-commutative linear logic (the logic of monoidal categories) except that the left rules may only be applied in stoup position. We show the admissibility of two forms cut (stoup cut and context cut), and prove the Calculus sound and complete with respect to existence of maps in the free skew monoidal category. We then introduce an equivalence relation on Sequent Calculus derivations and prove that there is a one-to-one correspondence between equivalence classes of derivations and maps in the free skew monoidal category. Finally, we identify a subCalculus of focused derivations, and establish that it contains exactly one canonical representative from each equivalence class. As an end result, we obtain simple algorithms both for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates, in particular, for deciding whether there is a map. We have formalized this development in the dependently typed programming language Agda.
-
MFPS - The Sequent Calculus of Skew Monoidal Categories
Electronic Notes in Theoretical Computer Science, 2018Co-Authors: Tarmo Uustalu, Niccolò Veltri, Noam ZeilbergerAbstract:Abstract Szlachanyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a Sequent Calculus for skew monoidal categories, building on the recent formulation by one of the authors of a Sequent Calculus for the Tamari order (skew semigroup categories). In this Calculus, antecedents consist of a stoup (an optional formula) followed by a context (a list of formulae), and the connectives unit and tensor behave like in intuitionistic non-commutative linear logic (the logic of monoidal categories) except that the left rules may only be applied in stoup position. We show the admissibility of two forms cut (stoup cut and context cut), and prove the Calculus sound and complete with respect to existence of maps in the free skew monoidal category. We then introduce an equivalence relation on Sequent Calculus derivations and prove that there is a one-to-one correspondence between equivalence classes of derivations and maps in the free skew monoidal category. Finally, we identify a subCalculus of focused derivations, and establish that it contains exactly one canonical representative from each equivalence class. As an end result, we obtain simple algorithms both for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates, in particular, for deciding whether there is a map. We have formalized this development in the dependently typed programming language Agda.