For a bounded Petri Net model the diagnosability property is usually checked via its regular language represented by the reachability graph RG. However, this is problematic because the computational complexity of the diagnosability test is polynomial in the cardinality of the state space of the model which is typically very large. This limitation can be overcome by using for the diagnosability test an ROF-automaton, with a state space significantly smaller than RG, that generates the same language as RG after projecting out all non-faulty unobservable transitions. ROF is efficiently constructed based on the calculation of the minimal explanations of the fault and of the observable transitions.