Journal article

Markov chains and unambiguous automata

Abstract:: Unambiguous automata are nondeterministic automata in which every word has at most one accepting run. In this paper we give a polynomial-time algorithm for model checking discrete-time Markov chains against ω-regular specifications represented as unambiguous automata. We furthermore show that the complexity of this model checking problem lies in NC: the subclass of P comprising those problems solvable in poly-logarithmic parallel time. These complexity bounds match the known bounds for model checking Markov chains against specifications given as deterministic automata, notwithstanding the fact that unambiguous automata can be exponentially more succinct than deterministic automata. We report on an implementation of our procedure, including an experiment in which the implementation is used to model check LTL formulas on Markov chains.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Baier, C., Kiefer, S., Klein, J., Müller, D., & Worrell, J. (2023). Markov chains and unambiguous automata. Journal of Computer and System Sciences, 136, 113–134.

MLA Style

Baier, C, et al. “Markov Chains and Unambiguous Automata.” Journal of Computer and System Sciences, vol. 136, 2023, pp. 113–34.

Chicago Style

Baier, C, S Kiefer, J Klein, D Müller, and J Worrell. 2023. “Markov Chains and Unambiguous Automata.” Journal of Computer and System Sciences 136: 113–34.
Print

Access Document

Files:: Baier_et_al_2023_Markov_chains_and.pdf

(Preview, Version of record, pdf, 610.5KB, Terms of use)

Publisher copy:: 10.1016/j.jcss.2023.03.005

Authors

+ Baier, C More by this author

Role:: Author

+ Kiefer, S More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Oxford college:: St John's College
Role:: Author
ORCID:: 0000-0003-4173-6877

+ Klein, J More by this author

Role:: Author

+ Müller, D More by this author

Role:: Author

+ Worrell, J More by this author

Role:: Author

+ Royal Society More from this funder

Grant:: URF/R/180025

Publisher:: Elsevier
Journal:: Journal of Computer and System Sciences More from this journal
Volume:: 136
Pages:: 113-134
Publication date:: 2023-04-13
Acceptance date:: 2023-03-23
DOI:: 10.1016/j.jcss.2023.03.005
EISSN:: 1090-2724
ISSN:: 0022-0000

Language:: English
Keywords:: FFR
Pubs id:: 1336272
Local pid:: pubs:1336272
Deposit date:: 2023-04-07
ARK identifier:: ark:/29072/ora_e2bfa3de66884b1d8f87ce04ed611c5d

Terms of use

Copyright holder:: Baier et al.
Copyright date:: 2023
Rights statement:: © 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/).

Licence:: CC Attribution (CC BY)

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP