Automata for Epistemic Temporal Logic with Synchronous Communication

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of logic, language, and information language, and information, 2010-10, Vol.19 (4), p.451-484
Main Authors: Mohalik, Swamp, Ramanujam, R.
Format: Article
Language:English
Subjects:
Alphabets
Automata
Automata theory
Education
Induction assumption
Information Systems Applications (incl.Internet)
Logic
Logical theorems
Model theory
Philosophy
Reasoning
Semantics
Temporal logic
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0925-8531
1572-9583
DOI:10.1007/s10849-009-9118-5