Probabilistic Automata of Bounded Ambiguity

DOI10.4230/LIPIcs.CONCUR.2017.19zbMath1442.68092OpenAlexW4285020225MaRDI QIDQ5111632

Nathanaël Fijalkow, Cristian Riveros, James Worrell

Publication date: 27 May 2020

Full work available at URL: https://hal.science/hal-03410680

zbMATH Keywords

probabilistic automataemptiness problemmulti-objective optimisation problemsstochastic path problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Multi-objective and goal programming (90C29) Stochastic programming (90C15) Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (14)

Polynomially ambiguous probabilistic automata on restricted languages ⋮ When are emptiness and containment decidable for probabilistic automata? ⋮ Decision Questions for Probabilistic Automata on Small Alphabets ⋮ Unnamed Item ⋮ Ambiguity, weakness, and regularity in probabilistic Büchi automata ⋮ Decidable and expressive classes of probabilistic automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The containment problem for unambiguous register automata and unambiguous timed automata ⋮ Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs. ⋮ The Containment Problem for Unambiguous Register Automata ⋮ Polynomially Ambiguous Probabilistic Automata on Restricted Languages ⋮ Probabilistic automata of bounded ambiguity ⋮ A robust class of linear recurrence sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the degree of ambiguity of finite automata
• The consensus string problem and the complexity of comparing hidden Markov models.
• Deciding the value 1 problem for probabilistic leaktight automata
• Decidable Problems for Probabilistic Automata on Infinite Words
• Deciding the Value 1 Problem for Probabilistic Leaktight Automata
• Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata
• Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
• On the Complexity of Numerical Analysis
• Probabilistic automata
• The ideal view on Rackoff's coverability technique

This page was built for publication: Probabilistic Automata of Bounded Ambiguity