A master thesis from Aalborg University
A Complete Approximation Theory for Weighted Transition Systems
Author(s)
Term
4. term
Education
Publication year
2015
Submitted on
2015-06-01
Pages
32 pages
Abstract
In this paper we explore a proof theoretic approach to approximate reasoning about weighted transition systems. We introduce generalized weighted transition systems (GTS) as an extension of the classical notion of a weighted transition system by replacing exact transition weights with intervals over non-negative real numbers. We define a modal logic over GTSs that can reason about said intervals by taking operators known from probabilistic logics and adjusting their interpretation for a weighted context. Semantically we can then describe whether a transition with at least some weight or at most some weight can be taken to a state satisfying some property. We show that our logic has the Hennesy-Milner property, i.e. it is semantically invariant under an appropriate bisimulation relation. As our main contribution we provide a sound and weak-complete axiomatization of our logic. To achieve the completeness result we have used a common technique for modal and Markovian logics involving the construction of a canonical model.
Keywords
Documents
Colophon: This page is part of the AAU Student Projects portal, which is run by Aalborg University. Here, you can find and download publicly available bachelor's theses and master's projects from across the university dating from 2008 onwards. Student projects from before 2008 are available in printed form at Aalborg University Library.
If you have any questions about AAU Student Projects or the research registration, dissemination and analysis at Aalborg University, please feel free to contact the VBN team. You can also find more information in the AAU Student Projects FAQs.