You are in : Home » Results & submissions » Select UOA » 11 - Computer Science and Informatics » View submission: University of Edinburgh » Outputs » Detail

Output details

11 - Computer Science and Informatics

University of Edinburgh

Return to search Previous output Next output

Output 0 of 0 in the submission

Article title

Approximating the termination value of one-counter MDPs and stochastic games

Type

D - Journal article

DOI

10.1016/j.ic.2012.01.008

Title of journal

Information and Computation

Article number

Volume number

222

Issue number

First page of article

121

ISSN of journal

0890-5401

Year of publication

2013

URL

http://www.sciencedirect.com/science/article/pii/S0890540112001599

Number of additional authors

Additional information

<10> Originality: First computability result for approximating, within any desired precision, the optimal (maximum or minimum) termination probabilities for One-Counter Markov Decision Processes (OC-MDPs) and One-Counter Stochastic games. Uses a novel martingale construction, obtained from certain linear programs one can associate with OC-MDPs.

Significance: Extends our purely qualitative results from SODA'10 to allow quantitative analysis of OC-MDPs. OC-MDPs extend discrete-time QBDs, a model studied heavily in queuing theory and performance evaluation, by allowing also control.

Rigour: Refereed journal paper with detailed mathematical proofs (18 pages) appears in the special issue of Information and Computation of selected invited papers from ICALP'11.

Interdisciplinary

Cross-referral requested

Research group

F - Laboratory for Foundations of Computer Science

Citation count

Proposed double-weighted

Double-weighted statement

Reserve for a double-weighted output

Non-English

English abstract