In the present work we examine the decidability of some questions concerning the existence of cutpoints isolated with respect to a given probabilistic automaton (PA). As is well known, the question of the existence of an isolated cutpoint, besides an intrinsic interest, has a considerable importance in connection with Rabin's theorem, which ensures that a cutpoint event T(A, Lambda) is regular if Lambda is an isolated cutpoint for the PA A.
Bertoni, A., Mauri, G., Torelli, M. (1977). Some recursively unsolvable problems relating to isolated cutpoints in probabilistic automata. In Proceedings 4th International Conference on Automata, Languages and Programming (pp.87-94). Berlin : Springer [10.1007/3-540-08342-1_7].
Some recursively unsolvable problems relating to isolated cutpoints in probabilistic automata
Mauri, G;
1977
Abstract
In the present work we examine the decidability of some questions concerning the existence of cutpoints isolated with respect to a given probabilistic automaton (PA). As is well known, the question of the existence of an isolated cutpoint, besides an intrinsic interest, has a considerable importance in connection with Rabin's theorem, which ensures that a cutpoint event T(A, Lambda) is regular if Lambda is an isolated cutpoint for the PA A.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
