On the expressiveness of spatial constraint systems

Abstract : Epistemic, mobile and spatial behaviour are common place in today’s distributed systems. The intrinsic epistemic nature of these systems arises from the interactions of the elements taking part of them. Most people are familiar with digital systems where users share their beliefs, opinions and even intentional lies (hoaxes). Models of those systems must take into account the interactions with others as well as the distributed quality these systems present. Spatial and mobile behaviour are exhibited by applications and data moving across (possibly nested) spaces defined by, for example, friend circles, groups, and shared folders. We therefore believe that a solid understanding of the notion of space and spatial mobility as well as the flow of epistemic information is relevant in many models of today’s distributed systems.Constraint systems (cs’s) provide the basic domains and opera- tions for the semantic foundations of the family of formal declarative models from concurrency theory known as concurrent constraint programming (ccp). Spatial constraint systems (scs’s) are algebraic structures that extend cs’s for reasoning about basic spatial and epistemic behaviour such as belief and extrusion. Both spatial and epistemic assertions can be viewed as specific modalities. Other modalities can be used for assertions about time, knowledge and even the analysis of groups among other concepts used in the specification and verification of concurrent systems.In this thesis we study the expressiveness of spatial constraint systems in the broader perspective of modal and epistemic behaviour. We shall show that spatial constraint systems are sufficiently robust to capture inverse modalities and to derive new results for modal logics. We shall show that we can use scs’s to express a fundamental epistemic behaviour such as knowledge. Finally we shall give an algebraic characterization of the notion of distributed information by means of constructors over scs’s.
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01674956
Contributor : Abes Star <>
Submitted on : Tuesday, December 12, 2017 - 12:05:58 AM
Last modification on : Sunday, April 21, 2019 - 1:23:48 AM

File

65210_GUZMAN_2017_archivage.pd...
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01674956, version 2

Citation

Michell Guzmán. On the expressiveness of spatial constraint systems. Logic in Computer Science [cs.LO]. Université Paris-Saclay, 2017. English. ⟨NNT : 2017SACLX064⟩. ⟨tel-01674956v2⟩

Share

Metrics

Record views

540

Files downloads

130