A Probabilistic Logic for Verifying Continuous-time Markov Chains Article Swipe

PDF

Ji Guan , Nengkun Yu ·

YOU? · · 2022 · Open Access · · DOI: https://doi.org/10.1007/978-3-030-99527-0_1

A continuous-time Markov chain (CTMC) execution is a continuous class of probability distributions over states. This paper proposes a probabilistic linear-time temporal logic, namely continuous-time linear logic (CLL), to reason about the probability distribution execution of CTMCs. We define the syntax of CLL on the space of probability distributions. The syntax of CLL includes multiphase timed until formulas, and the semantics of CLL allows time reset to study relatively temporal properties. We derive a corresponding model-checking algorithm for CLL formulas. The correctness of the model-checking algorithm depends on Schanuel’s conjecture, a central open problem in transcendental number theory. Furthermore, we provide a running example of CTMCs to illustrate our method.

Related Topics

Computer Science

Algorithm

Theoretical Computer Science

Artificial Intelligence

Mathematics

Statistics

Machine Learning

Concepts

Computer science Markov chain Probabilistic logic Probabilistic CTL Algorithm Markov process Theoretical computer science Temporal logic Probabilistic analysis of algorithms Artificial intelligence Mathematics Statistics Machine learning

Metadata

Type: book-chapter
Language: en
Landing Page: https://doi.org/10.1007/978-3-030-99527-0_1
PDF: https://link.springer.com/content/pdf/10.1007/978-3-030-99527-0_1.pdf
OA Status: hybrid
Cited By: 3
References: 48
Related Works: 10
OpenAlex ID: https://openalex.org/W3160709386

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W3160709386

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1007/978-3-030-99527-0_1

Digital Object Identifier
Title: A Probabilistic Logic for Verifying Continuous-time Markov Chains

Work title
Type: book-chapter

OpenAlex work type
Language: en

Primary language
Publication year: 2022

Year of publication
Publication date: 2022-01-01

Full publication date if available
Authors: Ji Guan, Nengkun Yu

List of authors in order
Landing page: https://doi.org/10.1007/978-3-030-99527-0_1

Publisher landing page
PDF URL: https://link.springer.com/content/pdf/10.1007/978-3-030-99527-0_1.pdf

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: hybrid

Open access status per OpenAlex
OA URL: https://link.springer.com/content/pdf/10.1007/978-3-030-99527-0_1.pdf

Direct OA link when available
Concepts: Computer science, Markov chain, Probabilistic logic, Probabilistic CTL, Algorithm, Markov process, Theoretical computer science, Temporal logic, Probabilistic analysis of algorithms, Artificial intelligence, Mathematics, Statistics, Machine learning

Top concepts (fields/topics) attached by OpenAlex
Cited by: 3

Total citation count in OpenAlex
Citations by year (recent): 2024: 2, 2023: 1

Per-year citation counts (last 5 years)
References (count): 48

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W3160709386
doi	https://doi.org/10.1007/978-3-030-99527-0_1
ids.doi	https://doi.org/10.1007/978-3-030-99527-0_1
ids.mag	3160709386
ids.openalex	https://openalex.org/W3160709386
fwci	2.07601439
type	book-chapter
title	A Probabilistic Logic for Verifying Continuous-time Markov Chains
biblio.issue
biblio.volume
biblio.last_page	21
biblio.first_page	3
topics[0].id	https://openalex.org/T10142
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998000264167786
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Formal Methods in Verification
topics[1].id	https://openalex.org/T11125
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9948999881744385
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Petri Nets in System Modeling
topics[2].id	https://openalex.org/T10933
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9872999787330627
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1708
topics[2].subfield.display_name	Hardware and Architecture
topics[2].display_name	Real-Time Systems Scheduling
is_xpac	False
apc_list.value	5000
apc_list.currency	EUR
apc_list.value_usd	5392
apc_paid.value	5000
apc_paid.currency	EUR
apc_paid.value_usd	5392
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.8151633739471436
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C98763669
concepts[1].level	2
concepts[1].score	0.7575587034225464
concepts[1].wikidata	https://www.wikidata.org/wiki/Q176645
concepts[1].display_name	Markov chain
concepts[2].id	https://openalex.org/C49937458
concepts[2].level	2
concepts[2].score	0.7274871468544006
concepts[2].wikidata	https://www.wikidata.org/wiki/Q2599292
concepts[2].display_name	Probabilistic logic
concepts[3].id	https://openalex.org/C52063229
concepts[3].level	4
concepts[3].score	0.5555037260055542
concepts[3].wikidata	https://www.wikidata.org/wiki/Q7246845
concepts[3].display_name	Probabilistic CTL
concepts[4].id	https://openalex.org/C11413529
concepts[4].level	1
concepts[4].score	0.4381864368915558
concepts[4].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[4].display_name	Algorithm
concepts[5].id	https://openalex.org/C159886148
concepts[5].level	2
concepts[5].score	0.42349669337272644
concepts[5].wikidata	https://www.wikidata.org/wiki/Q176645
concepts[5].display_name	Markov process
concepts[6].id	https://openalex.org/C80444323
concepts[6].level	1
concepts[6].score	0.415966272354126
concepts[6].wikidata	https://www.wikidata.org/wiki/Q2878974
concepts[6].display_name	Theoretical computer science
concepts[7].id	https://openalex.org/C25016198
concepts[7].level	2
concepts[7].score	0.41465625166893005
concepts[7].wikidata	https://www.wikidata.org/wiki/Q781833
concepts[7].display_name	Temporal logic
concepts[8].id	https://openalex.org/C24404364
concepts[8].level	3
concepts[8].score	0.21800744533538818
concepts[8].wikidata	https://www.wikidata.org/wiki/Q7246846
concepts[8].display_name	Probabilistic analysis of algorithms
concepts[9].id	https://openalex.org/C154945302
concepts[9].level	1
concepts[9].score	0.17410629987716675
concepts[9].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[9].display_name	Artificial intelligence
concepts[10].id	https://openalex.org/C33923547
concepts[10].level	0
concepts[10].score	0.13329705595970154
concepts[10].wikidata	https://www.wikidata.org/wiki/Q395
concepts[10].display_name	Mathematics
concepts[11].id	https://openalex.org/C105795698
concepts[11].level	1
concepts[11].score	0.08136388659477234
concepts[11].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[11].display_name	Statistics
concepts[12].id	https://openalex.org/C119857082
concepts[12].level	1
concepts[12].score	0.07628339529037476
concepts[12].wikidata	https://www.wikidata.org/wiki/Q2539
concepts[12].display_name	Machine learning
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.8151633739471436
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/markov-chain
keywords[1].score	0.7575587034225464
keywords[1].display_name	Markov chain
keywords[2].id	https://openalex.org/keywords/probabilistic-logic
keywords[2].score	0.7274871468544006
keywords[2].display_name	Probabilistic logic
keywords[3].id	https://openalex.org/keywords/probabilistic-ctl
keywords[3].score	0.5555037260055542
keywords[3].display_name	Probabilistic CTL
keywords[4].id	https://openalex.org/keywords/algorithm
keywords[4].score	0.4381864368915558
keywords[4].display_name	Algorithm
keywords[5].id	https://openalex.org/keywords/markov-process
keywords[5].score	0.42349669337272644
keywords[5].display_name	Markov process
keywords[6].id	https://openalex.org/keywords/theoretical-computer-science
keywords[6].score	0.415966272354126
keywords[6].display_name	Theoretical computer science
keywords[7].id	https://openalex.org/keywords/temporal-logic
keywords[7].score	0.41465625166893005
keywords[7].display_name	Temporal logic
keywords[8].id	https://openalex.org/keywords/probabilistic-analysis-of-algorithms
keywords[8].score	0.21800744533538818
keywords[8].display_name	Probabilistic analysis of algorithms
keywords[9].id	https://openalex.org/keywords/artificial-intelligence
keywords[9].score	0.17410629987716675
keywords[9].display_name	Artificial intelligence
keywords[10].id	https://openalex.org/keywords/mathematics
keywords[10].score	0.13329705595970154
keywords[10].display_name	Mathematics
keywords[11].id	https://openalex.org/keywords/statistics
keywords[11].score	0.08136388659477234
keywords[11].display_name	Statistics
keywords[12].id	https://openalex.org/keywords/machine-learning
keywords[12].score	0.07628339529037476
keywords[12].display_name	Machine learning
language	en
locations[0].id	doi:10.1007/978-3-030-99527-0_1
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S106296714
locations[0].source.issn	0302-9743, 1611-3349
locations[0].source.type	book series
locations[0].source.is_oa	False
locations[0].source.issn_l	0302-9743
locations[0].source.is_core	True
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Lecture notes in computer science
locations[0].source.host_organization	https://openalex.org/P4310319900
locations[0].source.host_organization_name	Springer Science+Business Media
locations[0].source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
locations[0].source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
locations[0].license	cc-by
locations[0].pdf_url	https://link.springer.com/content/pdf/10.1007/978-3-030-99527-0_1.pdf
locations[0].version	publishedVersion
locations[0].raw_type	book-chapter
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Lecture Notes in Computer Science
locations[0].landing_page_url	https://doi.org/10.1007/978-3-030-99527-0_1
locations[1].id	pmh:oai:arXiv.org:2004.08059
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url	https://arxiv.org/pdf/2004.08059
locations[1].version	submittedVersion
locations[1].raw_type	text
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published	False
locations[1].raw_source_name
locations[1].landing_page_url	http://arxiv.org/abs/2004.08059
indexed_in	arxiv, crossref
authorships[0].author.id	https://openalex.org/A5081435269
authorships[0].author.orcid	https://orcid.org/0000-0002-3490-0029
authorships[0].author.display_name	Ji Guan
authorships[0].countries	CN
authorships[0].affiliations[0].institution_ids	https://openalex.org/I19820366, https://openalex.org/I4210128818
authorships[0].affiliations[0].raw_affiliation_string	State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
authorships[0].institutions[0].id	https://openalex.org/I19820366
authorships[0].institutions[0].ror	https://ror.org/034t30j35
authorships[0].institutions[0].type	government
authorships[0].institutions[0].lineage	https://openalex.org/I19820366
authorships[0].institutions[0].country_code	CN
authorships[0].institutions[0].display_name	Chinese Academy of Sciences
authorships[0].institutions[1].id	https://openalex.org/I4210128818
authorships[0].institutions[1].ror	https://ror.org/033dfsn42
authorships[0].institutions[1].type	facility
authorships[0].institutions[1].lineage	https://openalex.org/I19820366, https://openalex.org/I4210128818
authorships[0].institutions[1].country_code	CN
authorships[0].institutions[1].display_name	Institute of Software
authorships[0].author_position	first
authorships[0].raw_author_name	Ji Guan
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
authorships[1].author.id	https://openalex.org/A5088217238
authorships[1].author.orcid	https://orcid.org/0000-0003-1188-3032
authorships[1].author.display_name	Nengkun Yu
authorships[1].countries	AU
authorships[1].affiliations[0].institution_ids	https://openalex.org/I114017466, https://openalex.org/I4210096034
authorships[1].affiliations[0].raw_affiliation_string	Centre for Quantum Software and Information, University of Technology Sydney, Sydney, Australia
authorships[1].institutions[0].id	https://openalex.org/I4210096034
authorships[1].institutions[0].ror	https://ror.org/00rnbty21
authorships[1].institutions[0].type	facility
authorships[1].institutions[0].lineage	https://openalex.org/I1337719021, https://openalex.org/I165143802, https://openalex.org/I2801453606, https://openalex.org/I4210096034, https://openalex.org/I4210132349
authorships[1].institutions[0].country_code	AU
authorships[1].institutions[0].display_name	Centre for Quantum Computation and Communication Technology
authorships[1].institutions[1].id	https://openalex.org/I114017466
authorships[1].institutions[1].ror	https://ror.org/03f0f6041
authorships[1].institutions[1].type	education
authorships[1].institutions[1].lineage	https://openalex.org/I114017466
authorships[1].institutions[1].country_code	AU
authorships[1].institutions[1].display_name	University of Technology Sydney
authorships[1].author_position	last
authorships[1].raw_author_name	Nengkun Yu
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Centre for Quantum Software and Information, University of Technology Sydney, Sydney, Australia
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://link.springer.com/content/pdf/10.1007/978-3-030-99527-0_1.pdf
open_access.oa_status	hybrid
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	A Probabilistic Logic for Verifying Continuous-time Markov Chains
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10142
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998000264167786
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Formal Methods in Verification
related_works	https://openalex.org/W1497573972, https://openalex.org/W2289277223, https://openalex.org/W4238495367, https://openalex.org/W2749065928, https://openalex.org/W1499367685, https://openalex.org/W2225666389, https://openalex.org/W2289944023, https://openalex.org/W2371210594, https://openalex.org/W3023702216, https://openalex.org/W2138707849
cited_by_count	3
counts_by_year[0].year	2024
counts_by_year[0].cited_by_count	2
counts_by_year[1].year	2023
counts_by_year[1].cited_by_count	1
locations_count	2
best_oa_location.id	doi:10.1007/978-3-030-99527-0_1
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S106296714
best_oa_location.source.issn	0302-9743, 1611-3349
best_oa_location.source.type	book series
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l	0302-9743
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Lecture notes in computer science
best_oa_location.source.host_organization	https://openalex.org/P4310319900
best_oa_location.source.host_organization_name	Springer Science+Business Media
best_oa_location.source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
best_oa_location.source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
best_oa_location.license	cc-by
best_oa_location.pdf_url	https://link.springer.com/content/pdf/10.1007/978-3-030-99527-0_1.pdf
best_oa_location.version	publishedVersion
best_oa_location.raw_type	book-chapter
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Lecture Notes in Computer Science
best_oa_location.landing_page_url	https://doi.org/10.1007/978-3-030-99527-0_1
primary_location.id	doi:10.1007/978-3-030-99527-0_1
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S106296714
primary_location.source.issn	0302-9743, 1611-3349
primary_location.source.type	book series
primary_location.source.is_oa	False
primary_location.source.issn_l	0302-9743
primary_location.source.is_core	True
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Lecture notes in computer science
primary_location.source.host_organization	https://openalex.org/P4310319900
primary_location.source.host_organization_name	Springer Science+Business Media
primary_location.source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
primary_location.source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
primary_location.license	cc-by
primary_location.pdf_url	https://link.springer.com/content/pdf/10.1007/978-3-030-99527-0_1.pdf
primary_location.version	publishedVersion
primary_location.raw_type	book-chapter
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Lecture Notes in Computer Science
primary_location.landing_page_url	https://doi.org/10.1007/978-3-030-99527-0_1
publication_date	2022-01-01
publication_year	2022
referenced_works	https://openalex.org/W1970473241, https://openalex.org/W2021112905, https://openalex.org/W2114554615, https://openalex.org/W2101508170, https://openalex.org/W2025782239, https://openalex.org/W2022479657, https://openalex.org/W2041226400, https://openalex.org/W2141881497, https://openalex.org/W2103836778, https://openalex.org/W77257248, https://openalex.org/W2158776910, https://openalex.org/W2160106881, https://openalex.org/W9281975, https://openalex.org/W6600632366, https://openalex.org/W2593267253, https://openalex.org/W2884771291, https://openalex.org/W2766658289, https://openalex.org/W6688888991, https://openalex.org/W2005998857, https://openalex.org/W2527393991, https://openalex.org/W2410243683, https://openalex.org/W2005308357, https://openalex.org/W2134991157, https://openalex.org/W2493224436, https://openalex.org/W2052909074, https://openalex.org/W12758337, https://openalex.org/W2063118073, https://openalex.org/W2082326200, https://openalex.org/W2001915506, https://openalex.org/W2007454673, https://openalex.org/W2138914032, https://openalex.org/W2027109253, https://openalex.org/W3095319300, https://openalex.org/W2152523762, https://openalex.org/W3038029671, https://openalex.org/W1498432697, https://openalex.org/W3103183526, https://openalex.org/W2735589526, https://openalex.org/W2167031861, https://openalex.org/W2465148488, https://openalex.org/W1972422534, https://openalex.org/W1014907731, https://openalex.org/W1605256314, https://openalex.org/W1592891131, https://openalex.org/W2963800672, https://openalex.org/W1815267262, https://openalex.org/W2962985445, https://openalex.org/W3034838075
referenced_works_count	48
abstract_inverted_index.A	1
abstract_inverted_index.a	8, 19, 74, 91, 102
abstract_inverted_index.We	38, 72
abstract_inverted_index.in	95
abstract_inverted_index.is	7
abstract_inverted_index.of	11, 36, 42, 47, 52, 62, 83, 105
abstract_inverted_index.on	44, 88
abstract_inverted_index.to	29, 67, 107
abstract_inverted_index.we	100
abstract_inverted_index.CLL	43, 53, 63, 79
abstract_inverted_index.The	50, 81
abstract_inverted_index.and	59
abstract_inverted_index.for	78
abstract_inverted_index.our	109
abstract_inverted_index.the	32, 40, 45, 60, 84
abstract_inverted_index.This	16
abstract_inverted_index.open	93
abstract_inverted_index.over	14
abstract_inverted_index.time	65
abstract_inverted_index.CTMCs	106
abstract_inverted_index.about	31
abstract_inverted_index.chain	4
abstract_inverted_index.class	10
abstract_inverted_index.logic	27
abstract_inverted_index.paper	17
abstract_inverted_index.reset	66
abstract_inverted_index.space	46
abstract_inverted_index.study	68
abstract_inverted_index.timed	56
abstract_inverted_index.until	57
abstract_inverted_index.(CLL),	28
abstract_inverted_index.(CTMC)	5
abstract_inverted_index.CTMCs.	37
abstract_inverted_index.Markov	3
abstract_inverted_index.allows	64
abstract_inverted_index.define	39
abstract_inverted_index.derive	73
abstract_inverted_index.linear	26
abstract_inverted_index.logic,	23
abstract_inverted_index.namely	24
abstract_inverted_index.number	97
abstract_inverted_index.reason	30
abstract_inverted_index.syntax	41, 51
abstract_inverted_index.central	92
abstract_inverted_index.depends	87
abstract_inverted_index.example	104
abstract_inverted_index.method.	110
abstract_inverted_index.problem	94
abstract_inverted_index.provide	101
abstract_inverted_index.running	103
abstract_inverted_index.states.	15
abstract_inverted_index.theory.	98
abstract_inverted_index.Abstract	0
abstract_inverted_index.includes	54
abstract_inverted_index.proposes	18
abstract_inverted_index.temporal	22, 70
abstract_inverted_index.algorithm	77, 86
abstract_inverted_index.execution	6, 35
abstract_inverted_index.formulas,	58
abstract_inverted_index.formulas.	80
abstract_inverted_index.semantics	61
abstract_inverted_index.continuous	9
abstract_inverted_index.illustrate	108
abstract_inverted_index.multiphase	55
abstract_inverted_index.relatively	69
abstract_inverted_index.conjecture,	90
abstract_inverted_index.correctness	82
abstract_inverted_index.linear-time	21
abstract_inverted_index.probability	12, 33, 48
abstract_inverted_index.properties.	71
abstract_inverted_index.Furthermore,	99
abstract_inverted_index.Schanuel’s	89
abstract_inverted_index.distribution	34
abstract_inverted_index.corresponding	75
abstract_inverted_index.distributions	13
abstract_inverted_index.probabilistic	20
abstract_inverted_index.distributions.	49
abstract_inverted_index.model-checking	76, 85
abstract_inverted_index.transcendental	96
abstract_inverted_index.continuous-time	2, 25
cited_by_percentile_year.max	96
cited_by_percentile_year.min	89
countries_distinct_count	2
institutions_distinct_count	2
citation_normalized_percentile.value	0.83905837
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False