NDLI: Concurrent omega-regular games

Content Provider	IEEE Xplore Digital Library
Author	de Alfaro, L. Henzinger, T.A.
Copyright Year	2000
Description	Author affiliation: Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA, USA (de Alfaro, L.)
Abstract	We consider two-player games which are played on a finite state space for an infinite number of rounds. The games are concurrent, that is, in each round, the two players choose their moves independently and simultaneously; the current state and the two moves determine a successor state. We consider omega-regular winning conditions on the resulting infinite state sequence. To model the independent choice of moves, both players are allowed to use randomization for selecting their moves. This gives rise to the following qualitative modes of winning, which can be studied without numerical considerations concerning probabilities: sure-win (player 1 can ensure winning with certainty); almost-sure-win (player 1 can ensure winning with probability 1); limit-win (player 1 can ensure winning with probability arbitrarily close to 1); bounded-win (player 1 can ensure winning with probability bounded away from 0); positive-win (player 1 can ensure winning with positive probability); and exist-win (player 1 can ensure that at least one possible outcome of the game satisfies the winning condition). We provide algorithms for computing the sets of winning states for each of these winning modes. In particular, we solve concurrent Rabin-chain games in n/sup O/(m) time, where n is the size of the game structure and m is the number of pairs in the Rabin-chain condition. While this complexity is in line with traditional turn-based games, our algorithms are considerably more involved. This is because concurrent games violate two of the most basic properties of turn-based games: concurrent games are not determined, but rather exhibit a more general duality property which involves multiple modes of winning; and winning strategies for concurrent games may require infinite memory.
Starting Page	141
Ending Page	154
File Size	443470
Page Count	14
File Format	PDF
ISBN	0769507255
ISSN	10436871
DOI	10.1109/LICS.2000.855763
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2000-06-28
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	State-space methods Engineering profession Safety Automata History
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

Concurrent Omega-Regular Games (2000)

Concurrent omega-regular games (2000).

Concurrent reachability games

Weak alternating automata are not that weak

Regular Repair of Specifications

Explicitly Parallel Regular Expressions

From verification to control: dynamic programs for omega-regular objectives

Concurrent Omega-Regular Games (2000)

Concurrent Omega-Regular Games (2000)

Concurrent omega-regular games

Similar Documents

Concurrent Omega-Regular Games (2000)

Concurrent omega-regular games (2000).

Concurrent reachability games

Weak alternating automata are not that weak

Regular Repair of Specifications

Explicitly Parallel Regular Expressions

From verification to control: dynamic programs for omega-regular objectives

Concurrent Omega-Regular Games (2000)

Concurrent Omega-Regular Games (2000)

Concurrent omega-regular games