Journal article icon

Journal article

When are emptiness and containment decidable for probabilistic automata?

Abstract:

The emptiness and containment problems for probabilistic automata are natural quantitative generalisations of the classical language emptiness and inclusion problems for Boolean automata. It is known that both problems are undecidable. We provide a more refined view of these problems in terms of the degree of ambiguity of probabilistic automata. We show that a gap version of the emptiness problem (known to be undecidable in general) becomes decidable for automata of polynomial ambiguity. We c...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jcss.2021.01.006

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Name:
Engineering and Physical Sciences Research Council
Grant:
EP/N008197/1
Publisher:
Elsevier
Journal:
Journal of Computer and System Sciences More from this journal
Volume:
119
Pages:
78-96
Publication date:
2021-02-10
Acceptance date:
2021-01-29
DOI:
ISSN:
0022-0000
Language:
English
Keywords:
Pubs id:
1160560
Local pid:
pubs:1160560
Deposit date:
2021-02-10

Terms of use


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