Probabilistic automata on finite words: decidable and undecidable problems

DOI10.1007/978-3-642-14162-1_44zbMATH Open1288.68156OpenAlexW1574229394MaRDI QIDQ3587465FDOQ3587465

Authors: Hugo Gimbert, Youssouf Oualhadj 

Publication date: 7 September 2010

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14162-1_44

Recommendations

• Probabilistic automata on infinite words: decidability and undecidability results
• Decidable problems for probabilistic automata on infinite words
• Probabilistic automata of bounded ambiguity
• Deciding the value 1 problem for probabilistic leaktight automata
• Probabilistic automata of bounded ambiguity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cited In (56)

• The boundedness and zero isolation problems for weighted automata over nonnegative rationals
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decision Questions for Probabilistic Automata on Small Alphabets
• On eventual non-negativity and positivity for the weighted sum of powers of matrices
• Title not available (Why is that?)
• Undecidable Problems for Probabilistic Network Programming
• Diagnosis and degradation control for probabilistic systems
• What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives
• Decision problems for probabilistic finite automata on bounded languages
• Decidable and expressive classes of probabilistic automata
• The complexity of synchronizing Markov decision processes
• Probabilistic automata with isolated cut-points
• On Decision Problems for Probabilistic Büchi Automata
• Controlling a population
• Artin’s Conjecture and Size of Finite Probabilistic Automata
• Profinite techniques for probabilistic automata
• Probabilistic opacity for Markov decision processes
• Reachability analysis of quantum Markov decision processes
• Decidable problems for probabilistic automata on infinite words
• Characterisation of an algebraic algorithm for probabilistic automata
• On the termination problem for probabilistic higher-order recursive programs
• Probabilistic disclosure: maximisation vs. minimisation
• Probabilistic automata of bounded ambiguity
• Probabilistic automata of bounded ambiguity
• Deciding maxmin reachability in half-blind stochastic games
• Distributed synthesis in continuous time
• Undecidable problems for probabilistic automata of fixed dimension
• Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata
• Probabilistic automata on infinite words: decidability and undecidability results
• Infinite Synchronizing Words for Probabilistic Automata
• Stochastization of weighted automata
• Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs.
• Deciding the value 1 problem for probabilistic leaktight automata
• Deciding the value 1 problem for probabilistic leaktight automata
• On regularity of unary probabilistic automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• POMDPs under probabilistic semantics
• Recurrence and transience for finite probabilistic tables
• Irregular behaviours for probabilistic automata
• Measure quantifier in monadic second order logic
• When is containment decidable for probabilistic automata?
• Emptiness of zero automata is decidable
• Bisimulation metrics and norms for real-weighted automata
• When are emptiness and containment decidable for probabilistic automata?
• Ambiguity, weakness, and regularity in probabilistic Büchi automata
• Emptiness problems for distributed automata
• Partial-observation stochastic games, how to win when belief fails
• The complexity of probabilistic versus deterministic finite automata
• Two recursively inseparable problems for probabilistic automata
• Title not available (Why is that?)
• A survey of partial-observation stochastic parity games
• Polynomially ambiguous probabilistic automata on restricted languages
• Profinite techniques for probabilistic automata and the Markov monoid algorithm
• Controlling a random population

This page was built for publication: Probabilistic automata on finite words: decidable and undecidable problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587465)