Recurrence and transience for finite probabilistic tables

DOI10.1016/j.tcs.2010.12.038zbMath1207.68226MaRDI QIDQ631776

Mathieu Tracol

Publication date: 14 March 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.12.038

zbMATH Keywords

Markov chains; recurrence; probabilistic automata; non-homogeneous Markov chains; finite probabilistic tables

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Products of stochastic matrices and applications
• Non-negative matrices and Markov chains.
• Relationships between nondeterministic and deterministic tape complexities
• Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
• Finite Continuous Time Markov Chains
• The complexity of probabilistic verification
• Tail events of simulated annealing Markov chains
• On Decision Problems for Probabilistic Büchi Automata
• Probabilistic automata
• Ergodic Theorems for Infinite Probabilistic Tables
• On the Tail $\Sigma$-Algebra of the Finite Inhomogeneous Markov Chains
• Power of Randomization in Automata on Infinite Strings
• Tools and Algorithms for the Construction and Analysis of Systems