Algebra i logika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Algebra Logika:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Algebra i logika, 2022, Volume 61, Number 4, Pages 401–423
DOI: https://doi.org/10.33048/alglog.2022.61.402
(Mi al2719)
 

Versions of a local contraction subexponential in the Lambek calculus

M. V. Valinkin

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
References:
Abstract: The Lambek calculus was introduced as a tool for examining linguistic constructions. Then this calculus was complemented with both new connectives and structural rules like contraction, weakening, and permutation. The structural rules are allowed only for formulas under the symbol of a specific modality called exponential. The Lambek calculus itself is a noncommutative structural logic, and for arbitrary formulas, the structural rules mentioned are not allowed. The next step is the introduction of a system of subexponentials: under the symbol of such a modality, only certain structural rules are admitted.
The following question arises: is it possible to formulate a system with a certain version of the local contraction rule (for formulas under subexponential) to recover the cut elimination property? We consider two approaches to solving this problem: one can both weaken the rule of introducing ${!}$ in the right-hand side of a sequent (LSCLC) and extend the local contraction rule from individual formulas to their subsequents (LMCLC). It is also worth mentioning that in commutative calculi, such a problem is missing since formulas in a sequent are allowed to be permuted (i.e, the local contraction rule coincides with the nonlocal one).
The following results are proved:
cut eliminability in the LMCLC and LSCLC calculi;
algorithmic decidability of fragments of these calculi in which ${!}$ is allowed to be applied only to variables;
algorithmic undecidability of LMCLC (for LSCLC, decidability remains an open question);
correctness and absence of strong completeness of LSCLC with respect to a class of relational models;
various results on equivalence for the calculi in question and the calculi with other versions of the contraction subexponential.
Keywords: Lambek calculus, local contraction subexponential.
Received: 10.03.2022
Revised: 29.03.2023
Bibliographic databases:
Document Type: Article
UDC: 515.125
Language: Russian
Citation: M. V. Valinkin, “Versions of a local contraction subexponential in the Lambek calculus”, Algebra Logika, 61:4 (2022), 401–423
Citation in format AMSBIB
\Bibitem{Val22}
\by M.~V.~Valinkin
\paper Versions of a local contraction subexponential in the Lambek calculus
\jour Algebra Logika
\yr 2022
\vol 61
\issue 4
\pages 401--423
\mathnet{http://mi.mathnet.ru/al2719}
\crossref{https://doi.org/10.33048/alglog.2022.61.402}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4586306}
Linking options:
  • https://www.mathnet.ru/eng/al2719
  • https://www.mathnet.ru/eng/al/v61/i4/p401
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Алгебра и логика Algebra and Logic
    Statistics & downloads:
    Abstract page:91
    Full-text PDF :31
    References:17
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024