Randomization in automata on infinite trees

DOI10.1145/2629336MaRDI QIDQ2946733zbMATH OpenOpenAlexFDO

Authors Arnaud Carayol, Axel Haddad, Olivier Serre

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01260669/file/CHS13_ACM_ToCL.pdf

zbMATH Keywords

(partial observation) Markov decision processesfinite automata on infinite treesmeasure theoryprobabilistic automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Decidable problems for probabilistic automata on infinite words
• Probabilistic automata on infinite words: decidability and undecidability results
• Counting branches in trees using games
• Probabilistic Acceptors for Languages over Infinite Words
• Probabilistic ω-automata

Cites work

• Automata on infinite trees with counting constraints
• Decidability of Second-Order Theories and Automata on Infinite Trees
• scientific article; zbMATH DE number 5872401 (Why is no real title available?)
• scientific article; zbMATH DE number 177825 (Why is no real title available?)
• scientific article; zbMATH DE number 1439861 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• scientific article; zbMATH DE number 3189696 (Why is no real title available?)
• Mathematical metaphysics of randomness
• Measure and integration theory. Transl. from the German by Robert B. Burckel
• On Decision Problems for Probabilistic Büchi Automata
• On equivalence of infinite product measures
• Power of Randomization in Automata on Infinite Strings
• Probabilistic automata
• Probabilistic Weighted Automata
• Probabilistic ω-automata
• Probability theory. Translated from the German by Robert B. Burckel
• Quantitative stochastic parity games

Cited in

(10)

• Stochastically costed tree automata: Turakainen's theorem
• Decidable problems for probabilistic automata on infinite words
• Baire category quantifier in monadic second order logic
• Monadic Second Order Logic with Measure and Category Quantifiers
• Alternating nonzero automata
• On the problem of computing the probability of regular sets of trees
• Erratum for “Randomization in Automata on Infinite Trees”
• Measure quantifier in monadic second order logic
• Power of Randomization in Automata on Infinite Strings
• Counting branches in trees using games

This page was built for publication: Randomization in automata on infinite trees

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