uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Qualitative Analysis of VASS-Induced MDPs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Univ Edinburgh, Edinburgh, Midlothian, Scotland..
Univ Edinburgh, Edinburgh, Midlothian, Scotland..
Univ Paris Diderot, CNRS, LIAFA, Sorbonne Paris Cite, Paris, France..
Show others and affiliations
2016 (English)In: Foundations Of Software Science And Computation Structures (FOSSACS 2016) / [ed] Jacobs, B Loding, C, 2016, p. 319-334Conference paper, Published paper (Refereed)
Abstract [en]

We consider infinite-state Markov decision processes (MDPs) that are induced by extensions of vector addition systems with states (VASS). Verification conditions for these MDPs are described by reachability and Buchi objectives w.r.t. given sets of control-states. We study the decidability of some qualitative versions of these objectives, i.e., the decidability of whether such objectives can be achieved surely, almostsurely, or limit-surely. While most such problems are undecidable in general, some are decidable for large subclasses in which either only the controller or only the random environment can change the counter values (while the other side can only change control-states).

Place, publisher, year, edition, pages
2016. p. 319-334
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9634
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:uu:diva-332916DOI: 10.1007/978-3-662-49630-5_19ISI: 000401936500019ISBN: 978-3-662-49630-5 (electronic)ISBN: 978-3-662-49629-9 (print)OAI: oai:DiVA.org:uu-332916DiVA, id: diva2:1154559
Conference
19th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS) Held as Part of the European Joint Conferences on Theory and Practice of Software (ETAPS), APR 04-07, 2016, Eindhoven, NETHERLANDS
Available from: 2017-11-02 Created: 2017-11-02 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Abdulla, Parosh

Search in DiVA

By author/editor
Abdulla, Parosh
By organisation
Computer Systems
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 61 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf