Abstract
We introduce spatial and epistemic process calculi for reasoning about spatial information and knowledge distributed among the agents of a system. We introduce domain-theoretical structures to represent spatial and epistemic information. We provide operational and denotational techniques for reasoning about the potentially infinite behaviour of spatial and epistemic processes. We also give compact representations of infinite objects that can be used by processes to simulate announcements of common knowledge and global information.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abramsky, S., Jung, A.: Domain theory. In: Maibaum, T.S.E., Abramsky, S., Gabbay, D.M. (eds.) Handbook of Logic in Computer Science, vol. III. Oxford University Press (1994)
Bengtson, J., Johansson, M., Parrow, J., Victor, B.: Psi-calculi: Mobile processes, nominal data, and logic. In: LICS (2009)
Buscemi, M.G., Montanari, U.: CC-Pi: A Constraint-Based Language for Specifying Service Level Agreements. In: De Nicola, R. (ed.) ESOP 2007. LNCS, vol. 4421, pp. 18–32. Springer, Heidelberg (2007)
Caires, L., Cardelli, L.: A spatial logic for concurrency - i. Inf. and Comp (2003)
Caires, L., Cardelli, L.: A spatial logic for concurrency - ii. Theor. Comp. Sci. (2004)
Cardelli, L., Gordon, A.D.: Mobile ambients. Theor. Comput. Sci. 240(1), 177–213 (2000)
Chadha, R., Delaune, S., Kremer, S.: Epistemic Logic for the Applied Pi Calculus. In: Lee, D., Lopes, A., Poetzsch-Heffter, A. (eds.) FMOODS/FORTE 2009. LNCS, vol. 5522, pp. 182–197. Springer, Heidelberg (2009)
de Boer, F.S., Pierro, A.D., Palamidessi, C.: Nondeterminism and infinite computations in constraint programming. Theor. Comput. Sci. 151(1), 37–78 (1995)
Dechesne, F., Mousavi, M.R., Orzan, S.: Operational and Epistemic Approaches to Protocol Analysis: Bridging the Gap. In: Dershowitz, N., Voronkov, A. (eds.) LPAR 2007. LNCS (LNAI), vol. 4790, pp. 226–241. Springer, Heidelberg (2007)
Fages, F., Ruet, P., Soliman, S.: Linear concurrent constraint programming: Operational and phase semantics. Inf. Comput. 165(1), 14–41 (2001)
Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning About Knowledge. MIT Press (1995)
Falaschi, M., Gabbrielli, M., Marriott, K., Palamidessi, C.: Confluence in concurrent constraint programming. Theor. Comput. Sci. 183(2), 281–315 (1997)
Halpern, J.Y., Moses, Y.: Knowledge and common knowledge in a distributed environment. In: Proc. of Principles of Distributed Computing, pp. 50–61 (1984)
Hughes, D., Shmatikov, V.: Information hiding, anonymity and privacy: a modular approach. Journal of Computer Security 12(1), 3–36 (2004)
Kripke, S.: Semantical analysis of modal logic. Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik (1963)
Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publishers (1996)
McKinsey, J.C.C., Tarski, A.: The algebra of topology. The Annals of Mathematics, second series (1944)
Mendler, N.P., Panangaden, P., Scott, P.J., Seely, R.A.G.: A logical view of concurrent constraint programming. Nordic Journal of Computing 2, 182–221 (1995)
Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes i and ii. Information and Computation 100, 1–77 (1992)
Panangaden, P.: Knowledge and Information in Probabilistic Systems. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol. 5201, p. 4. Springer, Heidelberg (2008)
Panangaden, P., Saraswat, V., Scott, P., Seely, R.: A Hyperdoctrinal View of Concurrent Constraint Programming. In: de Bakker, J.W., de Roever, W.-P., Rozenberg, G. (eds.) REX 1992. LNCS, vol. 666, pp. 457–476. Springer, Heidelberg (1993)
Popkorn, S.: First Steps in Modal Logic. Cambridge University Press (1994)
Réty, J.-H.: Distributed concurrent constraint programming. Fundam. Inform. (1998)
Saraswat, V.A.: Concurrent Constraint Programming Languages. PhD thesis, CMU (1989)
Saraswat, V.A., Rinard, M., Panangaden, P.: Semantic foundations of concurrent constraint programming. In: POPL 1991 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Knight, S., Palamidessi, C., Panangaden, P., Valencia, F.D. (2012). Spatial and Epistemic Modalities in Constraint-Based Process Calculi. In: Koutny, M., Ulidowski, I. (eds) CONCUR 2012 – Concurrency Theory. CONCUR 2012. Lecture Notes in Computer Science, vol 7454. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32940-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-32940-1_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32939-5
Online ISBN: 978-3-642-32940-1
eBook Packages: Computer ScienceComputer Science (R0)