ﻻ يوجد ملخص باللغة العربية
This short note aims at proving that the isolation problem is undecidable for probabilistic automata with only one probabilistic transition. This problem is known to be undecidable for general probabilistic automata, without restriction on the number of probabilistic transitions. In this note, we develop a simulation technique that allows to simulate any probabilistic automaton with one having only one probabilistic transition.
A weight normalization procedure, commonly called pushing, is introduced for weighted tree automata (wta) over commutative semifields. The normalization preserves the recognized weighted tree language even for nondeterministic wta, but it is most use
The probabilistic bisimilarity distance of Deng et al. has been proposed as a robust quantitative generalization of Segala and Lynchs probabilistic bisimilarity for probabilistic automata. In this paper, we present a characterization of the bisimilar
In [1], we introduced the weakly synchronizing languages for probabilistic automata. In this report, we show that the emptiness problem of weakly synchronizing languages for probabilistic automata is undecidable. This implies that the decidability re
We characterize the class of nondeterministic ${omega}$-automata that can be used for the analysis of finite Markov decision processes (MDPs). We call these automata `good-for-MDPs (GFM). We show that GFM automata are closed under classic simulation
Subzero automata is a class of tree automata whose acceptance condition can express probabilistic constraints. Our main result is that the problem of determining if a subzero automaton accepts some regular tree is decidable.