When are emptiness and containment decidable for probabilistic automata?
From MaRDI portal
Publication:2662671
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 well known that both problems are undecidable. In this paper 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 (that is known be undecidable in general) becomes decidable for automata of polynomial ambiguity. We complement this positive result by showing that the emptiness problem remains undecidable even when restricted to automata of linear ambiguity. We then turn to finitely ambiguous automata. Here we show decidability of containment in case one of the automata is assumed to be unambiguous while the other one is allowed to be finitely ambiguous. Our proof of this last result relies on the decidability of the theory of real exponentiation, which has been shown, subject to Schanuel's Conjecture, by Macintyre and Wilkie.
Recommendations
- When is containment decidable for probabilistic automata?
- Probabilistic automata on finite words: decidable and undecidable problems
- Decidable and expressive classes of probabilistic automata
- Decidable and expressive classes of probabilistic automata
- Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata
- Decision problems for probabilistic finite automata on bounded languages
- On Decision Problems for Probabilistic Büchi Automata
- Decidable problems for probabilistic automata on infinite words
- Probabilistic automata on infinite words: decidability and undecidability results
- STACS 2005
Cites work
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
- Assume-guarantee verification for probabilistic systems
- Decidable and expressive classes of probabilistic automata
- Deciding the value 1 problem for probabilistic leaktight automata
- Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata
- scientific article; zbMATH DE number 435565 (Why is no real title available?)
- scientific article; zbMATH DE number 1169378 (Why is no real title available?)
- scientific article; zbMATH DE number 5685899 (Why is no real title available?)
- scientific article; zbMATH DE number 3310089 (Why is no real title available?)
- scientific article; zbMATH DE number 3371972 (Why is no real title available?)
- Learning-based compositional verification for synchronous probabilistic systems
- On the definition of a family of automata
- On the degree of ambiguity of finite automata
- Probabilistic automata
- Probabilistic automata of bounded ambiguity
- Quantum automata and algebraic groups
- Reachability problems for Markov chains
- Statistical Inference for Probabilistic Functions of Finite State Markov Chains
- The containment problem for unambiguous register automata
- The covering and boundedness problems for vector addition systems
- Unbounded-error quantum computation with small space bounds
- Undecidable problems for probabilistic automata of fixed dimension
- What's decidable about weighted automata?
Cited in
(12)- The containment problem for unambiguous register automata and unambiguous timed automata
- Probabilistic automata of bounded ambiguity
- When is containment decidable for probabilistic automata?
- Emptiness of zero automata is decidable
- Probabilistic automata of bounded ambiguity
- Finitely ambiguous and finitely sequential weighted automata over fields
- The boundedness and zero isolation problems for weighted automata over nonnegative rationals
- The big-O problem for max-plus automata is decidable (PSPACE-complete)
- Determinisation and unambiguisation of polynomially-ambiguous rational weighted automata
- On the existential theory of the reals enriched with integer powers of a computable number
- Resolving nondeterminism by chance
- Containment and equivalence of weighted automata: probabilistic and max-plus cases
This page was built for publication: When are emptiness and containment decidable for probabilistic automata?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2662671)
