Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Note on Switching Conditions for the Generalized Logical Connectives in Multiplicative Linear Logic
62
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Danos and Regnier (1989) introduced the par-switching condition for the multiplicative proof-structures and simplified the sequentialization theorem of Girard (1987) by the use of par-switching. Danos and Regner (1989) also generalized the par-switching to a switching for $n$-ary connectives (an $n$-ary switching, in short) and showed that the expansion property which means that any excluded-middle formula has a correct proof-net in the sense of their $n$-ary switching. They added a remark that the sequentialization theorem does not hold with their switching. Their definition of switching for $n$-ary connectives is a natural generalization of the original switching for the binary connectives. However, there are many other possible definitions of switching for $n$-ary connectives. We give an alternative and natural definition of $n$-ary switching, and we remark that the proof of sequentialization theorem by Olivier Laurent with the par-switching works for our $n$-ary switching; hence that the sequentialization theorem holds for our $n$-ary switching. On the other hand, we remark that the expansion property does not hold with our switching anymore. We point out that no definition of $n$-ary switching satisfies both the sequentialization theorem and the expansion property at the same time except for the purely tensor-based (or purely par-based) connectives.
rate research
Read More
The purpose of this note is to discuss some of the questions raised by Dunn, J. Michael; Moss, Lawrence S.; Wang, Zhenghan in Editors introduction: the third life of quantum logic: quantum logic inspired by quantum computing.
Linear logical frameworks with subexponentials have been used for the specification of among other systems, proof systems, concurrent programming languages and linear authorization logics. In these frameworks, subexponentials can be configured to allow or not for the application of the contraction and weakening rules while the exchange rule can always be applied. This means that formulae in such frameworks can only be organized as sets and multisets of formulae not being possible to organize formulae as lists of formulae. This paper investigates the proof theory of linear logic proof systems in the non-commutative variant. These systems can disallow the application of exchange rule on some subexponentials. We investigate conditions for when cut-elimination is admissible in the presence of non-commutative subexponentials, investigating the interaction of the exchange rule with local and non-local contraction rules. We also obtain some new undecidability and decidability results on non-commutative linear logic with subexponentials.
We continue the study of computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree structure. Our main result shows that although ${omega cdot 2, omega^star cdot 2}$ is computably embeddable in ${omega^2, {(omega^2)}^star}$, the class ${omega cdot k,omega^star cdot k}$ is emph{not} computably embeddable in ${omega^2, {(omega^2)}^star}$ for any natural number $k geq 3$.
We use the geometric axioms point of view to give an effective listing of the complete types of the theory $DCF_{0}$ of differentially closed fields of characteristic $0$. This gives another account of observations made in earlier papers.
We use the framework of reverse mathematics to address the question of, given a mathematical problem, whether or not it is easier to find an infinite partial solution than it is to find a complete solution. Following Flood, we say that a Ramsey-type variant of a problem is the problem with the same instances but whose solutions are the infinite partial solutions to the original problem. We study Ramsey-type variants of problems related to Konigs lemma, such as restrictions of Konigs lemma, Boolean satisfiability problems, and graph coloring problems. We find that sometimes the Ramsey-type variant of a problem is strictly easier than the original problem (as Flood showed with weak Konigs lemma) and that sometimes the Ramsey-type variant of a problem is equivalent to the original problem. We show that the Ramsey-type variant of weak Konigs lemma is robust in the sense of Montalban: it is equivalent to several perturbations of itself. We also clarify the relationship between Ramsey-type weak Konigs lemma and algorithmic randomness by showing that Ramsey-type weak weak Konigs lemma is equivalent to the problem of finding diagonally non-recursive functions and that these problems are strictly easier than Ramsey-type weak Konigs lemma. This answers a question of Flood.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
