Approximating Markov processes through filtration (Q442296): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Ming Sheng Ying / rank | |||
Property / author | |||
Property / author: Ming Sheng Ying / rank | |||
Normal rank | |||
Property / review text | |||
The Hennessy-Milner theorem states that image finite Kripke models are bisimilar if and only if they are logically equivalent. This holds for modal logics that are interpreted through Kripke models. The extension of this property to probabilistic logics with probabilistic Kripke models based on continuous state spaces has turned out to present a considerable challenge; it was answered in the positive for analytic spaces by \textit{J. Desharnais} et al. [Inf. Comput. 179, No. 2, 163--193 (2002; Zbl 1096.68103)] through a laborious construction using disintegration of measures, and for Polish spaces by this reviewer [SIAM J. Comput. 35, No. 3, 590--626 (2006; Zbl 1095.68063)] through selection arguments. The present paper deals with this problem through an approximation argument; approximating Markov transition systems has been proposed and studied by \textit{J. Desharnais} et al. [Theor. Comput. Sci. 318, No. 3, 323--354 (2004; Zbl 1068.68093)] and by \textit{F. van Breughel} and \textit{J. Worrell} [Theor. Comput. Sci. 331, No. 1, 115--142 (2005; Zbl 1070.68109)]. These papers construct metrics, so that approximation becomes metric approximation. The present paper constructs a metric as well, but in contrast to the papers mentioned above the metrics are constructed through novel process using filtration, taking a discount factor into account (the later two formulas differ the smaller the distance gets). It is shown that a Polish space is obtained, but, strictly speaking, the authors obtain a pseudometric space which is shown to be Polish after canonically factoring it. The techniques are derived mainly from the first author's Ph.D. thesis and a subsequent paper of his [J. Log. Comput. 19, No. 6, 1427--1454 (2009; Zbl 1191.03018)]. The paper is well written; it carefully explains the development, the proofs are accessible, albeit, as to be expected, fairly technical. It provides a wealth of information about Markov transition systems; the references reflect the state of the art. | |||
Property / review text: The Hennessy-Milner theorem states that image finite Kripke models are bisimilar if and only if they are logically equivalent. This holds for modal logics that are interpreted through Kripke models. The extension of this property to probabilistic logics with probabilistic Kripke models based on continuous state spaces has turned out to present a considerable challenge; it was answered in the positive for analytic spaces by \textit{J. Desharnais} et al. [Inf. Comput. 179, No. 2, 163--193 (2002; Zbl 1096.68103)] through a laborious construction using disintegration of measures, and for Polish spaces by this reviewer [SIAM J. Comput. 35, No. 3, 590--626 (2006; Zbl 1095.68063)] through selection arguments. The present paper deals with this problem through an approximation argument; approximating Markov transition systems has been proposed and studied by \textit{J. Desharnais} et al. [Theor. Comput. Sci. 318, No. 3, 323--354 (2004; Zbl 1068.68093)] and by \textit{F. van Breughel} and \textit{J. Worrell} [Theor. Comput. Sci. 331, No. 1, 115--142 (2005; Zbl 1070.68109)]. These papers construct metrics, so that approximation becomes metric approximation. The present paper constructs a metric as well, but in contrast to the papers mentioned above the metrics are constructed through novel process using filtration, taking a discount factor into account (the later two formulas differ the smaller the distance gets). It is shown that a Polish space is obtained, but, strictly speaking, the authors obtain a pseudometric space which is shown to be Polish after canonically factoring it. The techniques are derived mainly from the first author's Ph.D. thesis and a subsequent paper of his [J. Log. Comput. 19, No. 6, 1427--1454 (2009; Zbl 1191.03018)]. The paper is well written; it carefully explains the development, the proofs are accessible, albeit, as to be expected, fairly technical. It provides a wealth of information about Markov transition systems; the references reflect the state of the art. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ernst-Erich Doberkat / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q85 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q87 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03B48 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60J05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6064625 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Markov transition systems | |||
Property / zbMATH Keywords: Markov transition systems / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
probability logic | |||
Property / zbMATH Keywords: probability logic / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
coalgebra, Kripke models | |||
Property / zbMATH Keywords: coalgebra, Kripke models / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
bisimilarity | |||
Property / zbMATH Keywords: bisimilarity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
filtration | |||
Property / zbMATH Keywords: filtration / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
metric approximation | |||
Property / zbMATH Keywords: metric approximation / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.026 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2079922371 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Game Refinement Relations and Metrics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3999603 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Interactive epistemology. II: Probability / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Model-checking continuous-time Markov chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4836494 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2744124 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximating Markov Processes by Averaging / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2844076 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bisimulation and cocongruence for probabilistic systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bisimulation for probabilistic transition systems: A coalgebraic approach / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bisimulation for labelled Markov processes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximating labelled Markov processes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Metrics for labelled Markov processes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Continuous stochastic logic characterizes bisimulation of continuous-time Markov processes. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coalgebraic logic over general measurable spaces – a survey / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topological Completeness in an Ideal Model for Polymorphic Types / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Semi-pullbacks for stochastic relations over analytic spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Hennessy-Milner equivalence for continuous time stochastic logic with mu-operator / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Stochastic Relations: Congruences, Bisimulations and the Hennessy--Milner Theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Stochastic coalgebraic logic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4375489 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3946875 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4495853 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Deduction Systems for Coalgebras Over Measurable Spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5799972 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Probability logic for type spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topology-free typology of beliefs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algebraic laws for nondeterminism and concurrency / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Exemplaric Expressivity of Modal Logics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A probabilistic PDL / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3992568 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Final coalgebras for functors on measurable spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Universal coalgebra: A theory of systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Probabilistic systems coalgebraically: a survey / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recursively defined metric spaces without contraction / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A behavioural pseudometric for probabilistic transition systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximating and computing behavioural distances in probabilistic transition systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: \(\pi\)-calculus with noisy channels / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2767183 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Complete Deductive System for Probability Logic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Probability logic of finitely additive beliefs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 13:45, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximating Markov processes through filtration |
scientific article |
Statements
Approximating Markov processes through filtration (English)
0 references
10 August 2012
0 references
The Hennessy-Milner theorem states that image finite Kripke models are bisimilar if and only if they are logically equivalent. This holds for modal logics that are interpreted through Kripke models. The extension of this property to probabilistic logics with probabilistic Kripke models based on continuous state spaces has turned out to present a considerable challenge; it was answered in the positive for analytic spaces by \textit{J. Desharnais} et al. [Inf. Comput. 179, No. 2, 163--193 (2002; Zbl 1096.68103)] through a laborious construction using disintegration of measures, and for Polish spaces by this reviewer [SIAM J. Comput. 35, No. 3, 590--626 (2006; Zbl 1095.68063)] through selection arguments. The present paper deals with this problem through an approximation argument; approximating Markov transition systems has been proposed and studied by \textit{J. Desharnais} et al. [Theor. Comput. Sci. 318, No. 3, 323--354 (2004; Zbl 1068.68093)] and by \textit{F. van Breughel} and \textit{J. Worrell} [Theor. Comput. Sci. 331, No. 1, 115--142 (2005; Zbl 1070.68109)]. These papers construct metrics, so that approximation becomes metric approximation. The present paper constructs a metric as well, but in contrast to the papers mentioned above the metrics are constructed through novel process using filtration, taking a discount factor into account (the later two formulas differ the smaller the distance gets). It is shown that a Polish space is obtained, but, strictly speaking, the authors obtain a pseudometric space which is shown to be Polish after canonically factoring it. The techniques are derived mainly from the first author's Ph.D. thesis and a subsequent paper of his [J. Log. Comput. 19, No. 6, 1427--1454 (2009; Zbl 1191.03018)]. The paper is well written; it carefully explains the development, the proofs are accessible, albeit, as to be expected, fairly technical. It provides a wealth of information about Markov transition systems; the references reflect the state of the art.
0 references
Markov transition systems
0 references
probability logic
0 references
coalgebra, Kripke models
0 references
bisimilarity
0 references
filtration
0 references
metric approximation
0 references
0 references