19th International Conference on Relational and Algebraic Methods in Computer Science / 19ème Conférence internationale de méthodes relationnelles et algébriques en informatique

Collection 19th International Conference on Relational and Algebraic Methods in Computer Science / 19ème Conférence internationale de méthodes relationnelles et algébriques en informatique

Organizer(s) Fahrenberg, Uli ; Gehrke, Mai ; Santocanale, Luigi ; Winter, Michael

Date(s) 02/11/2021 - 06/11/2021

linked URL https://conferences.cirm-math.fr/2398.html

00:00:00 / 00:00:00

5 5

Relational models for the Lambek calculus with intersection and unit

By Stepan Kuznetsov

We consider the Lambek calculus extended with intersection (meet) operation. For its variant which does not allow empty antecedents, Andreka and Mikulas (1994) prove strong completeness w.r.t. relational models (R-models). Without the antecedent non-emptiness restriction, however, only weak completeness w.r.t. R-models (so-called square ones) holds (Mikulas 2015). Our goals are as follows. First, we extend the calculus with the unit constant, introduce a class of non-standard R-models for it, and prove completeness. This gives a simpler proof of Mikulas' result. Second, we prove that strong completeness does not hold. Third, we extend our weak completeness proof to the infinitary setting, to so-called iterative divisions (Kleene star under division).

Information about the video

Date of recording 05/11/2021
Date of publication 26/11/2021
Institution CIRM
Licence CC BY NC ND
Language English
Audience Researchers
Director(s) Luca Recanzone
Format MP4

Citation data

DOI 10.24350/CIRM.V.19828603
Cite this video Kuznetsov, Stepan (05/11/2021). Relational models for the Lambek calculus with intersection and unit. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19828603
URL https://dx.doi.org/10.24350/CIRM.V.19828603

Domain(s)

Bibliography

ANDRÉKA, Hajnal et MIKULÁS, Szabolcs. Lambek calculus and its relational semantics: completeness and incompleteness. Journal of Logic, Language and Information, 1994, vol. 3, no 1, p. 1-37. - https://doi.org/10.1007/BF01066355
LAMBEK, Joachim. The mathematics of sentence structure. The American Mathematical Monthly, 1958, vol. 65, no 3, p. 154-170. - https://doi.org/10.1080/00029890.1958.11989160
MIKULÁS, Szabolcs. The equational theories of representable residuated semigroups. Synthese, 2015, vol. 192, no 7, p. 2151-2158. - https://doi.org/10.1007/s11229-014-0513-3
MIKULÁS, Szabolcs. Lower semilattice-ordered residuated semigroups and substructural logics. Studia Logica, 2015, vol. 103, no 3, p. 453-478. - https://doi.org/10.1007/s11225-014-9574-z
KUZNETSOV, Stepan L. Relational Models for the Lambek Calculus with Intersection and Unit. In : International Conference on Relational and Algebraic Methods in Computer Science. Springer, Cham, 2021. p. 258-274. - https://doi.org/10.1007/978-3-030-88701-8_16

MSC codes

Document(s)

https://www.cirm-math.fr/RepOrga/2398/Slides/Kuznetsov.pdf

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

All the collection videos

01:03:09

published on November 26, 2021

Relational tight field bounds for distributed analysis of programs

By Marcelo Frias

44:23

published on November 26, 2021

Quantified constraint satisfaction problem: towards the classification of complexity

By Dmitriy Zhuk

25:24

published on November 26, 2021

Time warps, from algebra to algorithms

By Simon Santschi

01:00:52

published on November 26, 2021

Fixpoint games

By Barbara König

29:45

published on November 26, 2021

Relational models for the Lambek calculus with intersection and unit

By Stepan Kuznetsov

Copyright Carmin.tv 2024

Give feedback