Noncommutative Logic
   HOME
*





Noncommutative Logic
Noncommutative logic is an extension of linear logic which combines the commutative connectives of linear logic with the noncommutative multiplicative connectives of the Lambek calculus. Its sequent calculus relies on the structure of order varieties (a family of cyclic orders which may be viewed as a species of structure), and the correctness criterion for its proof nets is given in terms of partial permutations. It also has a denotational semantics in which formulas are interpreted by modules over some specific Hopf algebras. Noncommutativity in logic By extension, the term noncommutative logic is also used by a number of authors to refer to a family of substructural logics in which the exchange rule is inadmissible. The remainder of this article is devoted to a presentation of this acceptance of the term. The oldest noncommutative logic is the Lambek calculus, which gave rise to the class of logics known as categorial grammars. Since the publication of Jean-Yves Girard's lin ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Linear Logic
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also been studied for its own sake, more broadly, ideas from linear logic have been influential in fields such as programming languages, game semantics, and quantum physics (because linear logic can be seen as the logic of quantum information theory), as well as linguistics, particularly because of its emphasis on resource-boundedness, duality, and interaction. Linear logic lends itself to many different presentations, explanations, and intuitions. Proof-theoretically, it derives from an analysis of classical sequent calculus in which uses of (the structural rules) contraction and weakening are carefully controlled. Operationally, this means that logical deduction is no longer merely about an ever-expanding collection of persistent "truths", ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Substructural Type System
Substructural type systems are a family of type systems analogous to substructural logics where one or more of the structural rules are absent or only allowed under controlled circumstances. Such systems are useful for constraining access to system resources such as files, locks and memory by keeping track of changes of state that occur and preventing invalid states. Different substructural type systems Several type systems have emerged by discarding some of the structural rules of exchange, weakening, and contraction: *Ordered type systems (discard exchange, weakening and contraction): Every variable is used exactly once in the order it was introduced. *Linear type systems (allow exchange, but neither weakening nor contraction): Every variable is used exactly once. *Affine type systems (allow exchange and weakening, but not contraction): Every variable is used at most once. *Relevant type systems (allow exchange and contraction, but not weakening): Every variable is used ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Ordered Type System
Substructural type systems are a family of type systems analogous to substructural logics where one or more of the structural rules are absent or only allowed under controlled circumstances. Such systems are useful for constraining access to system resources such as files, locks and memory by keeping track of changes of state that occur and preventing invalid states. Different substructural type systems Several type systems have emerged by discarding some of the structural rules of exchange, weakening, and contraction: *Ordered type systems (discard exchange, weakening and contraction): Every variable is used exactly once in the order it was introduced. *Linear type systems (allow exchange, but neither weakening nor contraction): Every variable is used exactly once. *Affine type systems (allow exchange and weakening, but not contraction): Every variable is used at most once. *Relevant type systems (allow exchange and contraction, but not weakening): Every variable is used ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Sequent
In mathematical logic, a sequent is a very general kind of conditional assertion. : A_1,\,\dots,A_m \,\vdash\, B_1,\,\dots,B_n. A sequent may have any number ''m'' of condition formulas ''Ai'' (called " antecedents") and any number ''n'' of asserted formulas ''Bj'' (called "succedents" or "consequents"). A sequent is understood to mean that if all of the antecedent conditions are true, then at least one of the consequent formulas is true. This style of conditional assertion is almost always associated with the conceptual framework of sequent calculus. Introduction The form and semantics of sequents Sequents are best understood in the context of the following three kinds of logical judgments: Unconditional assertion. No antecedent formulas. * Example: ⊢ ''B'' * Meaning: ''B'' is true. Conditional assertion. Any number of antecedent formulas. Simple conditional assertion. Single consequent formula. * Example: ''A1'', ''A2'', ''A3'' ⊢ ''B'' * Meaning: IF ''A1'' AND ''A ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Deep Inference
Deep inference names a general idea in structural proof theory that breaks with the classical sequent calculus by generalising the notion of structure to permit inference to occur in contexts of high structural complexity. The term ''deep inference'' is generally reserved for proof calculi where the structural complexity is unbounded; in this article we will use non-shallow inference to refer to calculi that have structural complexity greater than the sequent calculus, but not unboundedly so, although this is not at present established terminology. Deep inference is not important in logic outside of structural proof theory, since the phenomena that lead to the proposal of formal systems with deep inference are all related to the cut-elimination theorem. The first calculus of deep inference was proposed by Kurt Schütte,Kurt Schütte. Proof Theory. Springer-Verlag, 1977. but the idea did not generate much interest at the time. Nuel Belnap proposed display logic in an attempt to ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Calculus Of Structures
The calculus of structures is a proof calculus with deep inference for studying the structural proof theory of noncommutative logic. The calculus has since been applied to study linear logic, classical logic, modal logic, and process calculi, and many benefits are claimed to follow in these investigations from the way in which deep inference is made available in the calculus. References * Alessio Guglielmi (2004)., 'A System of Interaction and Structure'. ACM Transactions on Computational Logic. * Kai Brünnler (2004). ''Deep Inference and Symmetry in Classical Proofs''. Logos Verlag. External links Calculus of structures homepage page documenting implementations of logical systems in the calculus of structures, using the Maude system The Maude system is an implementation of rewriting logic. It is similar in its general approach to Joseph Goguen's OBJ3 implementation of equational logic, but based on rewriting logic rather than order-sorted equational logic, and with a heavy ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Alessio Guglielmi
Alessio is a mostly Italian male name, Italian form of Alexius. Individuals with the given name Alessio *Alessio Ascalesi (1872–1952), Italian cardinal *Alessio Boni (born 1966), Italian actor *Alessio Cerci (born 1987), Italian footballer *Alessio Cragno (born 1994), Italian footballer * Alessio Da Cruz (born 1997), Dutch footballer *Alessio Deledda (born 1994), Italian racing driver *Alessio Di Chirico (born 1989), Italian martial artist * Alessio di Giovanni (1872-1946), Italian poet * Alessio di Savino (born 1984), Italian boxer * Alessio Donnarumma (born 1998), Italian footballer *Alessio Figalli (born 1984), Italian mathematician (Fields medalist) * Alessio Locatelli (born 1978), Italian footballer *Alessio Lorandi (born 1998), Italian racing driver *Alessio Morosin (born 1955), Italian lawyer *Alessio Riccardi (born 2001), Italian footballer *Miguel Alessio Robles, Mexican lawyer *Vito Alessio Robles (1879–1957), Mexican general *Alessio Romagnoli (born 1995), Italian ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Cut-elimination Theorem
The cut-elimination theorem (or Gentzen's ''Hauptsatz'') is the central result establishing the significance of the sequent calculus. It was originally proved by Gerhard Gentzen in his landmark 1934 paper "Investigations in Logical Deduction" for the systems LJ and LK formalising intuitionistic and classical logic respectively. The cut-elimination theorem states that any judgement that possesses a proof in the sequent calculus making use of the cut rule also possesses a cut-free proof, that is, a proof that does not make use of the cut rule. The cut rule A sequent is a logical expression relating multiple formulas, in the form , which is to be read as proves , and (as glossed by Gentzen) should be understood as equivalent to the truth-function "If (A_1 and A_2 and A_3 …) then (B_1 or B_2 or B_3 …)." Note that the left-hand side (LHS) is a conjunction (and) and the right-hand side (RHS) is a disjunction (or). The LHS may have arbitrarily many or few formulae; when the LH ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Computational Linguistics
Computational linguistics is an Interdisciplinarity, interdisciplinary field concerned with the computational modelling of natural language, as well as the study of appropriate computational approaches to linguistic questions. In general, computational linguistics draws upon linguistics, computer science, artificial intelligence, mathematics, logic, philosophy, cognitive science, cognitive psychology, psycholinguistics, anthropology and neuroscience, among others. Sub-fields and related areas Traditionally, computational linguistics emerged as an area of artificial intelligence performed by computer scientists who had specialized in the application of computers to the processing of a natural language. With the formation of the Association for Computational Linguistics (ACL) and the establishment of independent conference series, the field consolidated during the 1970s and 1980s. The Association for Computational Linguistics defines computational linguistics as: The term "comp ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Joachim Lambek
Joachim "Jim" Lambek (5 December 1922 – 23 June 2014) was a German-born Canadian mathematician. He was Peter Redpath Emeritus Professor of Pure Mathematics at McGill University, where he earned his PhD degree in 1950 with Hans Zassenhaus as advisor. Biography Lambek was born in Leipzig, Germany, where he attended a Gymnasium. He came to England in 1938 as a refugee on the ''Kindertransport''. From there he was interned as an enemy alien and deported to a prison work camp in New Brunswick, Canada. There, he began in his spare time a mathematical apprenticeship with Fritz Rothberger, also interned, and wrote the McGill Junior Matriculation in fall of 1941. In the spring of 1942, he was released and settled in Montreal, where he entered studies at McGill University, graduating with an honours mathematics degree in 1945 and an MSc a year later. In 1950, he completed his doctorate under Hans Zassenhaus becoming McGill's first PhD in mathematics. Lambek became assistant p ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Noncommutative Logic
Noncommutative logic is an extension of linear logic which combines the commutative connectives of linear logic with the noncommutative multiplicative connectives of the Lambek calculus. Its sequent calculus relies on the structure of order varieties (a family of cyclic orders which may be viewed as a species of structure), and the correctness criterion for its proof nets is given in terms of partial permutations. It also has a denotational semantics in which formulas are interpreted by modules over some specific Hopf algebras. Noncommutativity in logic By extension, the term noncommutative logic is also used by a number of authors to refer to a family of substructural logics in which the exchange rule is inadmissible. The remainder of this article is devoted to a presentation of this acceptance of the term. The oldest noncommutative logic is the Lambek calculus, which gave rise to the class of logics known as categorial grammars. Since the publication of Jean-Yves Girard's lin ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]