About: Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives

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

About: Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives 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	We show that the controller synthesis and verification problems for Markov decision processes with qualitative PECTL* objectives are 2-EXPTIME complete. More precisely, the algorithms are polynomial in the size of a given Markov decision process and doubly exponential in the size of a given qualitative PECTL* formula. Moreover, we show that if a given qualitative PECTL* objective is achievable by some strategy, then it is also achievable by an effectively constructible one-counter strategy, where the associated complexity bounds are essentially the same as above. For the fragment of qualitative PCTL objectives, we obtain EXPTIME completeness and the algorithms are only singly exponential in the size of the formula. We show that the controller synthesis and verification problems for Markov decision processes with qualitative PECTL* objectives are 2-EXPTIME complete. More precisely, the algorithms are polynomial in the size of a given Markov decision process and doubly exponential in the size of a given qualitative PECTL* formula. Moreover, we show that if a given qualitative PECTL* objective is achievable by some strategy, then it is also achievable by an effectively constructible one-counter strategy, where the associated complexity bounds are essentially the same as above. For the fragment of qualitative PCTL objectives, we obtain EXPTIME completeness and the algorithms are only singly exponential in the size of the formula. (en)
Title	Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives (en)
skos:prefLabel	Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives (en)
skos:notation	RIV/00216224:14330/08:00024825!RIV10-GA0-14330___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), P(GD102/05/H050), Z(MSM0021622419)
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Brázdil, Tomáš Forejt, Vojtěch Kučera, Antonín
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
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	361276
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/08:00024825
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Markov decision processes; Probabilistic Temporal Logics (en)
http://linked.open.../riv/klicoveSlovo	Markov decision processes Probabilistic Temporal Logics
http://linked.open...ontrolniKodProRIV	[15D0F2DC0BCD]
http://linked.open...v/mistoKonaniAkce	Reykjavik, Iceland
http://linked.open...i/riv/mistoVydani	Berlin, Heidelberg, New York
http://linked.open...i/riv/nazevZdroje	Automata, Languages and Programming. 35th International Colloquium, ICALP 2008. Reykjavik, Iceland, July 2008. Proceedings, Part II.
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science Integrated Approach to Education of PhD Students in the Area of Parallel and Distributed Systems
http://linked.open...UplatneniVysledku	2008
http://linked.open...iv/tvurceVysledku	Brázdil, Tomáš Forejt, Vojtěch Kučera, Antonín
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open...ain/vavai/riv/wos	00025766310
http://linked.open.../riv/zahajeniAkce	2008-07-07 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
number of pages	12 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Springer-Verlag
https://schema.org/isbn	3-540-70582-1
http://localhost/t...ganizacniJednotka	14330
is http://linked.open...avai/riv/vysledek of	Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives

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, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software