Decision Questions for Probabilistic Automata on Small Alphabets
From MaRDI portal
Publication:6137871
DOI10.46298/lmcs-19(4:36)2023arXiv2105.10293MaRDI QIDQ6137871
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
Related Items
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