Automata for Epistemic Temporal Logic with Synchronous Communication

Abstract
We suggest that developing automata theoretic foundations is relevant for knowledge theory, so that we study not only what is known by agents, but also the mechanisms by which such knowledge is arrived at. We define a class of epistemic automata, in which agents’ local states are annotated with abstract knowledge assertions about others. These are finite state agents who communicate synchronously with each other and information exchange is ‘perfect’. We show that the class of recognizable languages has good closure properties, leading to a Kleene-type theorem using what we call regular knowledge expressions. These automata model distributed causal knowledge in the following way: each agent in the system has a partial knowledge of the temporal evolution of the system, and every time agents synchronize, they update each other’s knowledge, resulting in a more up-to-date view of the system state. Hence we show that these automata can be used to solve the satisfiability problem for a natural epistemic temporal logic for local properties. Finally, we characterize the class of languages recognized by epistemic automata as the regular consistent languages studied in concurrency theory
Keywords Epistemic logic  Automata theory  Decidability  Knowledge expressions
Categories (categorize this paper)
DOI 10.1007/s10849-009-9118-5
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 34,515
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Reasoning About Knowledge.Ronald Fagin (ed.) - 1995 - MIT Press.
Defaults in Update Semantics.Frank Veltman - 1996 - Journal of Philosophical Logic 25 (3):221 - 261.
Merging Frameworks for Interaction.Johan van Benthem, Jelle Gerbrandy, Tomohiro Hoshi & Eric Pacuit - 2009 - Journal of Philosophical Logic 38 (5):491-526.
A Knowledge Based Semantics of Messages.Rohit Parikh & Ramaswamy Ramanujam - 2003 - Journal of Logic, Language and Information 12 (4):453-467.

View all 7 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Analytics

Added to PP index
2010-01-23

Total downloads
34 ( #179,720 of 2,268,169 )

Recent downloads (6 months)
1 ( #373,366 of 2,268,169 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature