Tameness and the power of programs over monoids in DA

Autor: Grosshans, Nathan, Mckenzie, Pierre, Segoufin, Luc

Publikováno v: Logical Methods in Computer Science
Logical Methods in Computer Science, 2022, 18 (3), pp.14:1-14:34. ⟨10.46298/lmcs-18(3:14)2022⟩

International audience; The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a6bfc0044029e6e3740b3df6122dbaff
https://lmcs.episciences.org/7110

Multiplicative Linear Logic from Logic Programs and Tilings

Autor: Eng, Boris, Seiller, Thomas

We present a non-deterministic model of computation related to Robinson’s first-order resolution. This model formalises and extends ideas sketched by Girard in his Transcendental Syntax programme. After establishing formal defini- tions and basic p

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::26e1cb1a02a442f203dd5bae2d19f416
https://hal.archives-ouvertes.fr/hal-02895111v3/file/main.pdf

Stellar Resolution: Multiplicatives - for the linear logician, through examples

Autor: Eng, Boris

The stellar resolution is an asynchronous model of computation used in Girard's Transcendental Syntax which is based on Robinson's first-order clausal resolution. By using methods of realisability for linear logic, we obtain a new model of multiplica

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::52f516a6fb59f7418a6fb004bc24b336
https://hal.archives-ouvertes.fr/hal-02977750v2/file/main.pdf

Forward Analysis for WSTS, Part III: Karp-Miller Trees

Autor: Blondin, Michael, Finkel, Alain, Goubault-Larrecq, Jean

Publikováno v: Logical Methods in Computer Science
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2020, 16 (2)
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2017, Kanpur, India. ⟨10.4230/LIPIcs.FSTTCS.2017.16⟩

Logical Methods in Computer Science ; Volume 16, Issue 2 ; 1860-5974
This paper is a sequel of "Forward Analysis for WSTS, Part I: Completions" [STACS 2009, LZI Intl. Proc. in Informatics 3, 433-444] and "Forward Analysis for WSTS, Part II: Comp

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::942c6e7444a6e4156c373cceaecf461d
https://hal.inria.fr/hal-03216116

A gentle introduction to Girard's Transcendental Syntax for the linear logician

Autor: ENG, Boris

Technically speaking, the transcendental syntax is about designing logics with a computational foundation. It suggests a new framework for proof theory where logic (proofs, formulas, truth, ...) is no more primitive but computation is. All the logica

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::532db5da4c370f726ac2f14ae3179e63