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

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?

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)

Cites Work

• Probabilistic automata
• Title not available (Why is that?)
• The consensus string problem and the complexity of comparing hidden Markov models.
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Probabilistic automata on finite words: decidable and undecidable problems
• On the Complexity of Numerical Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• On the degree of ambiguity of finite automata
• Title not available (Why is that?)
• The ideal view on Rackoff's coverability technique
• Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata

Cited In (22)

• Title not available (Why is that?)
• Decision Questions for Probabilistic Automata on Small Alphabets
• Decidable and expressive classes of probabilistic automata
• The Containment Problem for Unambiguous Register Automata
• Probabilistic ω-automata
• An automata-based view on configurability and uncertainty
• Probabilistic automata of bounded ambiguity
• Title not available (Why is that?)
• Probabilistic asynchronous automata
• 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 and unambiguous timed automata
• The boundedness and zero isolation problems for weighted automata over nonnegative rationals
• 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
• Quantitative Automata under Probabilistic Semantics
• General Algorithms for Testing the Ambiguity of Finite Automata
• Title not available (Why is that?)
• 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)