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, 319-334 p.Conference 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. 319-334 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9634
National Category
Computer and Information Science
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: 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: 2017-11-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 10 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