About: Faster algorithms for mean-payoff games

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Faster algorithms for mean-payoff games Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	In this paper, we study algorithmic problems for quantitative models that are motivated by the applications in modeling embedded systems. We consider two-player games played on a weighted graph with mean-payoff objective and with energy constraints. We present a new pseudopolynomial algorithm for solving such games, improving the best known worst-case complexity for pseudopolynomial mean-payoff algorithms. Our algorithm can also be combined with the procedure by Andersson and Vorobyov to obtain a randomized algorithm with currently the best expected time complexity. The proposed solution relies on a simple fixpoint iteration to solve the log-space equivalent problem of deciding the winner of energy games. Our results imply also that energy games and mean-payoff games can be reduced to safety games in pseudopolynomial time. In this paper, we study algorithmic problems for quantitative models that are motivated by the applications in modeling embedded systems. We consider two-player games played on a weighted graph with mean-payoff objective and with energy constraints. We present a new pseudopolynomial algorithm for solving such games, improving the best known worst-case complexity for pseudopolynomial mean-payoff algorithms. Our algorithm can also be combined with the procedure by Andersson and Vorobyov to obtain a randomized algorithm with currently the best expected time complexity. The proposed solution relies on a simple fixpoint iteration to solve the log-space equivalent problem of deciding the winner of energy games. Our results imply also that energy games and mean-payoff games can be reduced to safety games in pseudopolynomial time. (en)
Title	Faster algorithms for mean-payoff games Faster algorithms for mean-payoff games (en)
skos:prefLabel	Faster algorithms for mean-payoff games Faster algorithms for mean-payoff games (en)
skos:notation	RIV/00216224:14330/11:00050261!RIV12-GA0-14330___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GA201/09/1389), Z(MSM0021622419)
http://linked.open...iv/cisloPeriodika	2
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Chaloupka, Jakub Brim, Luboš
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	199378
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/11:00050261
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Mean payoff objectives; Algorithms and complexity upper bounds (en)
http://linked.open.../riv/klicoveSlovo	Algorithms and complexity upper bounds Mean payoff objectives
http://linked.open...odStatuVydavatele	DE - Spolková republika Německo
http://linked.open...ontrolniKodProRIV	[4CD524B25019]
http://linked.open...i/riv/nazevZdroje	Formal Methods in System Design
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	5 (xsd:int)
http://linked.open...vavai/riv/projekt	Verification and Analysis of Large-Scale Computer Systems
http://linked.open...UplatneniVysledku	2011
http://linked.open...v/svazekPeriodika	38
http://linked.open...iv/tvurceVysledku	Brim, Luboš Chaloupka, Jakub Doyen, Laurent Gentilini, Raffaella Raskin, Jean-François
http://linked.open...ain/vavai/riv/wos	000288671700001
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
issn	0925-9856
number of pages	22 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/s10703-010-0105-x
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software