Decision Questions for Probabilistic Automata on Small Alphabets

DOI10.46298/LMCS-19(4:36)2023arXiv2105.10293MaRDI QIDQ6137871FDOQ6137871

Pavel Semukhin, Paul C. Bell

Publication date: 16 January 2024

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: We study the emptiness and $lambda$-reachability problems for unary and binary Probabilistic Finite Automata (PFA) and characterise the complexity of these problems in terms of the degree of ambiguity of the automaton and the size of its alphabet. Our main result is that emptiness and $lambda$-reachability are solvable in EXPTIME for polynomially ambiguous unary PFA and if, in addition, the transition matrix is binary, we show they are in NP. In contrast to the Skolem-hardness of the $lambda$-reachability and emptiness problems for exponentially ambiguous unary PFA, we show that these problems are NP-hard even for finitely ambiguous unary PFA. For binary polynomially ambiguous PFA with fixed and commuting transition matrices, we prove NP-hardness of the $lambda$-reachability (dimension 9), nonstrict emptiness (dimension 37) and strict emptiness (dimension 40) problems.

Full work available at URL: https://arxiv.org/abs/2105.10293

zbMATH Keywords

probabilistic finite automataemptiness problemunary alphabetbounded ambiguity

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx) Computer science (68-XX)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilistic automata
• Title not available (Why is that?)
• NP-complete decision problems for binary quadratics
• Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
• Undecidable problems for probabilistic automata of fixed dimension
• Fast parallel matrix and GCD computations
• Positivity Problems for Low-Order Linear Recurrence Sequences
• Occurrence of zero in a linear recursive sequence
• Title not available (Why is that?)
• Reachability problems for Markov chains
• Generalized Automata and Stochastic Languages
• Title not available (Why is that?)
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages
• Decision Problems for Linear Recurrence Sequences
• Probabilistic Automata of Bounded Ambiguity
• A robust class of linear recurrence sequences
• Title not available (Why is that?)
• Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs.
• Near-Optimal Complexity Bounds for Fragments of the Skolem Problem
• Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• Decision Questions for Probabilistic Automata on Small Alphabets

Cited In (1)

• Decision Questions for Probabilistic Automata on Small Alphabets

This page was built for publication: Decision Questions for Probabilistic Automata on Small Alphabets

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