NDLI: An Abstraction-Refinement Framework for Multi-Agent Systems

Content Provider	IEEE Xplore Digital Library
Author	Ball, T. Kupferman, O.
Copyright Year	2006
Description	Author affiliation: Microsoft Res., Redmond, WA (Ball, T.)
Abstract	Abstraction is a key technique for reasoning about systems with very large or even infinite state spaces. When a system is composed of reactive components, the interaction between the components is modeled by a multi-player game and verification corresponds to finding winners in the game. We describe an abstraction-refinement framework for multi-player games, with respect to specifications in the alternating mu-calculus (AMC). Our framework is based on abstract alternating transition systems (AATSs). Each agent in an AATS has transitions that over-approximate its power and transitions that under-approximate its power. We define the framework, define a 3-valued semantics for AMC formulas in an AATS, study the model-checking problem, define an abstraction preorder between AATSs, suggest a refinement procedure (in case model checking returns an indefinite answer), and study the completeness of the framework. For the case of predicate abstraction, we show how reasoning can be automated with a theorem prover. Abstractions of multi-player games have been studied in the past. Our main contribution with respect to earlier work is that we study general (rather than only turn-based) ATSs, we add a refinement procedure on top of the model checking procedure, and our abstraction preorder is parameterized by a set of agents
Sponsorship	IEEE Comput. Soc. Tech. Committ. on Mathematical Found. of Comput
Starting Page	379
Ending Page	388
File Size	215677
Page Count	10
File Format	PDF
ISBN	0769526314
ISSN	10436871
DOI	10.1109/LICS.2006.10
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-08-12
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Multiagent systems State-space methods Power system modeling Open systems Game theory Concrete Automata Computer science Logic Security
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Predicate abstraction in protocol verification

An abstraction-refinement framework for multi-agent systems (2006)

Fuzzy multi-agent cooperative Q-learning

A brief survey on cooperation in multi-agent system

Origins and metamorphoses of the Trinity: logic, nets, automata

An intelligent agent-based model for security management

Select Reliable Strategy in Multi-Agent Systems Using Fuzzy Logic-Based Fusion

Strategies in multi-agent systems

Model-checking real-time concurrent systems

An Abstraction-Refinement Framework for Multi-Agent Systems

Similar Documents

Predicate abstraction in protocol verification

An abstraction-refinement framework for multi-agent systems (2006)

Fuzzy multi-agent cooperative Q-learning

A brief survey on cooperation in multi-agent system

Origins and metamorphoses of the Trinity: logic, nets, automata

An intelligent agent-based model for security management

Select Reliable Strategy in Multi-Agent Systems Using Fuzzy Logic-Based Fusion

Strategies in multi-agent systems

Model-checking real-time concurrent systems

An Abstraction-Refinement Framework for Multi-Agent Systems