Conference item
The Big-O problem for labelled Markov chains and weighted automata
- Abstract:
-
Given two weighted automata, we consider the problem of whether one is big-O of the other, i.e., if the weight of every finite word in the first is not greater than some constant multiple of the weight in the second. We show that the problem is undecidable, even for the instantiation of weighted automata as labelled Markov chains. Moreover, even when it is known that one weighted automaton is big-O of another, the problem of finding or approximating the associated constant is also undecidable...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, 730.0KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.CONCUR.2020.41
Authors
Funding
Bibliographic Details
- Publisher:
- Schloss Dagstuhl
- Journal:
- LIPIcs More from this journal
- Volume:
- 171
- Pages:
- 1-19
- Publication date:
- 2020-08-26
- Acceptance date:
- 2020-06-29
- Event title:
- 31st International Conference on Concurrency Theory (CONCUR 2020)
- Event website:
- https://concur2020.forsyte.at/
- Event start date:
- 2020-09-01
- Event end date:
- 2020-09-04
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959771603
Item Description
- Language:
-
English
- Keywords:
- Pubs id:
-
1119180
- Local pid:
-
pubs:1119180
- Deposit date:
-
2020-07-16
Terms of use
- Copyright holder:
- Chistikov et al.
- Copyright date:
- 2020
- Rights statement:
- © Dmitry Chistikov, Stefan Kiefer, Andrzej S. Murawski, and David Purser; licensed under Creative Commons License CC-BY.
- Notes:
- This paper was presented at the 31st International Conference on Concurrency Theory (CONCUR 2020), September 2020.
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record