Subexponential concurrent constraint programming

详细信息    查看全文

• 作者：Carlos Olarte^a ; ^{carlos.olarte@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Elaine Pimentel^a ; ^{elaine.pimentel@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Vivek Nigam^b ; ^{vivek.nigam@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Linear logic ; Concurrent constraint programming ; Proof systems
• 刊名：Theoretical Computer Science
• 出版年：2015
• 出版时间：16 November 2015
• 年：2015
• 卷：606
• 期：Complete
• 页码：98-120
• 全文大小：693 K

文摘

In previous works we have shown that linear logic with subexponentials (SELL), a refinement of linear logic, can be used to specify emergent features of concurrent constraint programming (CCP) languages, such as preferences and spatial, epistemic and temporal modalities. In order to do so, we introduced a number of extensions to SELL, such as subexponential quantifiers for the specification of modalities, and more elaborated subexponential structures for the specification of preferences. These results provided clear proof theoretic foundations to existing systems. This paper goes in the opposite direction, answering positively the question: can the proof theory of linear logic with subexponentials contribute to the development of new CCP languages? We propose a CCP language with the following powerful features: 1) computational spaces where agents can tell and ask preferences (soft-constraints); 2) systems where spatial and temporal modalities can be combined; 3) shared spaces for communication that can be dynamically established; and 4) systems that can dynamically create nested spaces. In order to provide the proof theoretic foundations for such a language, we propose a unified logical framework (SELLS^⋒${\mathrm{SELLS}}^{⋒}$) combining the extensions of linear logic with subexponentials mentioned above, and showing that this new framework has interesting proof theoretical properties such as cut-elimination and a sound and complete focused proof system.