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.
slide + paper
probabilistic automata; isolated cutpoints
English
International Conference on Automata, Languages and Programming
1977
Salomaa, A; Steinby, M
Proceedings 4th International Conference on Automata, Languages and Programming
978-3-540-08342-9
1977
52
87
94
none
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/16954
Citazioni
  • Scopus 26
  • ???jsp.display-item.citation.isi??? ND
Social impact