Journal article
The big-O problem
- 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, 934.6KB, Terms of use)
-
- Publication website:
- https://lmcs.episciences.org/9217
Authors
Funding
Bibliographic Details
- Publisher:
- Logical Methods in Computer Science
- Journal:
- Logical Methods in Computer Science More from this journal
- Volume:
- 18
- Issue:
- 1
- Article number:
- 40
- Publication date:
- 2022-03-15
- Acceptance date:
- 2022-02-01
- ISSN:
-
1860-5974
Item Description
- Language:
-
English
- Keywords:
- Pubs id:
-
1244062
- Local pid:
-
pubs:1244062
- Deposit date:
-
2022-03-15
Terms of use
- Copyright holder:
- Chistikov et al
- Copyright date:
- 2022
- Rights statement:
- © D. Chistikov, S. Kiefer, A. S. Murawski, and D. Purser. This work is licensed under the Creative Commons Attribution License. To view a copy of this license, visit https://creativecommons.org/licenses/by/4.0/ or send a letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany.
- 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