Jurdzinski, Marcin and Trivedi, Ashutosh (2008) Average-time games. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Bangalore, India, 9-11 Dec 2008. Published in: Leibniz International Proceedings in Informatics, Vol.2 pp. 340-351.

Full text not available from this repository.

Abstract

An average-time game is played on the infinite graph of configurations of a finite timed automaton. The two players, Min and Max, construct an infinite run of the automaton by taking turns to perform a timed transition. Player Min wants to minimize the average time per transition and player Max wants to maximize it. A solution of average-time games is presented using a reduction to average-price game on a finite graph. A direct consequence is an elementary proof of determinacy for average-time games. This complements our results for reachability-time games and partially solves a problem posed by Bouyer et al., to design an algorithm for solving average-price games on priced timed automata. The paper also establishes the exact computational complexity of solving average-time games: the problem is EXPTIME-complete for timed automata with at least two clocks.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	Leibniz International Proceedings in Informatics
Publisher:	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
ISSN:	1868-8969
Date:	2008
Volume:	Vol.2
Page Range:	pp. 340-351
Identification Number:	10.4230/LIPIcs.FSTTCS.2008.1765
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Type of Event:	Conference
Location of Event:	Bangalore, India
Date(s) of Event:	9-11 Dec 2008
URI:	http://wrap.warwick.ac.uk/id/eprint/42353

Request changes to a record

Actions (login required)

View Item