Probabilistic automata of bounded ambiguity

DOI10.4230/LIPICS.CONCUR.2017.19zbMATH Open1442.68092OpenAlexW4285020225MaRDI QIDQ5111632FDOQ5111632

Authors 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

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

Recommendations

• Probabilistic automata of bounded ambiguity
• Probabilistic automata on finite words: decidable and undecidable problems
• When are emptiness and containment decidable for probabilistic automata?
• Polynomially ambiguous probabilistic automata on restricted languages
• When is containment decidable for probabilistic automata?

Cites work

• scientific article; zbMATH DE number 5764846 (Why is no real title available?)
• scientific article; zbMATH DE number 3976343 (Why is no real title available?)
• scientific article; zbMATH DE number 3513703 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Decidable problems for probabilistic automata on infinite words
• Deciding the value 1 problem for probabilistic leaktight automata
• Deciding the value 1 problem for probabilistic leaktight automata
• Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On the Complexity of Numerical Analysis
• On the degree of ambiguity of finite automata
• Probabilistic automata
• Probabilistic automata on finite words: decidable and undecidable problems
• The consensus string problem and the complexity of comparing hidden Markov models.
• The ideal view on Rackoff's coverability technique

Cited in

(20)

• Decidable and expressive classes of probabilistic automata
• Probabilistic ω-automata
• An automata-based view on configurability and uncertainty
• Probabilistic automata of bounded ambiguity
• Probabilistic asynchronous automata
• The big-O problem
• A robust class of linear recurrence sequences
• Probabilistic automata on finite words: decidable and undecidable problems
• Space-bounded probabilistic game automata
• Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs.
• The containment problem for unambiguous register automata
• The containment problem for unambiguous register automata and unambiguous timed automata
• The boundedness and zero isolation problems for weighted automata over nonnegative rationals
• When is containment decidable for probabilistic automata?
• When are emptiness and containment decidable for probabilistic automata?
• Ambiguity, weakness, and regularity in probabilistic Büchi automata
• Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• General Algorithms for Testing the Ambiguity of Finite Automata
• Title not available (Why is no real title available?)
• Polynomially ambiguous probabilistic automata on restricted languages

This page was built for publication: Probabilistic automata of bounded ambiguity

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