Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Expressiveness of probabilistic modal logics, revisited

Tools
- Tools
+ Tools

Fijalkow, Nathanael, Klin, Bartek and Panangaden, Prakash (2017) Expressiveness of probabilistic modal logics, revisited. In: 44th International Colloquium on Automata, Languages, and Programming, Warsaw, Poland, 10-14 Jul 2017. Published in: 44th International Colloquium on Automata, Languages, and Programming,, 80 105.1-105.12. ISSN 1868-8969. doi:10.4230/LIPIcs.ICALP.2017.105

[img]
Preview
PDF
WRAP-Expressive-probabilistic-modal-revisited-Fijalkow-2017.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.

Download (507Kb) | Preview
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.105

Request Changes to record.

Abstract

Labelled Markov processes are probabilistic versions of labelled transition systems. In general, the state space of a labelled Markov process may be a continuum. Logical characterizations of probabilistic bisimulation and simulation were given by Desharnais et al. These results hold for systems defined on analytic state spaces and assume that there are countably many labels in the case of bisimulation and finitely many labels in the case of simulation.

In this paper, we first revisit these results by giving simpler and more streamlined proofs. In particular, our proof for simulation has the same structure as the one for bisimulation, relying on a new result of a topological nature. This departs from the known proof for this result, which uses domain theory techniques and falls out of a theory of approximation of Labelled Markov processes.

Both our proofs assume the presence of countably many labels. We investigate the necessity of this assumption, and show that the logical characterization of bisimulation may fail when there are uncountably many labels. However, with a stronger assumption on the transition functions (continuity instead of just measurability), we can regain the logical characterization result, for arbitrarily many labels. These new results arose from a new game-theoretic way of understanding probabilistic simulation and bisimulation

Item Type: Conference Item (Paper)
Alternative Title:
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Markov processes -- Numerical solutions, Bisimulation
Journal or Publication Title: 44th International Colloquium on Automata, Languages, and Programming,
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
ISSN: 1868-8969
Official Date: 14 April 2017
Dates:
DateEvent
14 April 2017Accepted
Volume: 80
Page Range: 105.1-105.12
DOI: 10.4230/LIPIcs.ICALP.2017.105
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access
Funder: Alan Turing Institute (London, England), Engineering and Physical Sciences Research Council (EPSRC), Narodowe Centrum Nauki [National Science Centre] (NCN), Natural Sciences and Engineering Research Council of Canada (NSERC)
Grant number: EP/N510129/1 (EPSRC), 2012/07/E/ST6/03026 (NCN)
Conference Paper Type: Paper
Title of Event: 44th International Colloquium on Automata, Languages, and Programming
Type of Event: Conference
Location of Event: Warsaw, Poland
Date(s) of Event: 10-14 Jul 2017

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us