Decision Questions for Probabilistic Automata on Small Alphabets

DOI10.46298/lmcs-19(4:36)2023arXiv2105.10293MaRDI QIDQ6137871

Pavel Semukhin, Paul C. Bell

Publication date: 16 January 2024

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

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)

Related Items

Decision Questions for Probabilistic Automata on Small Alphabets

Cites Work

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