Rough set flow graph inference

Pawlak recently introduced rough set flow graphs (RSFGs) as a graphical framework for reasoning from data. No study, however, has yet investigated the complexity of the accompanying inference algorithm, nor the complexity of inference in RSFGs. In this thesis, we establish the computational complexity for RSFG inference by studying the relation between Bayesian networks and RSFGs and show that the traditional RSFG inference algorithm has exponential time complexity. Then a new RSFG inference algorithm that exploits the factorization in a RSFG is proposed. We prove its correctness and establish its polynomial time complexity. In addition, we show that our inference algorithm never does more work than the traditional algorithm. Our discussion also reveals that, unlike traditional rough set research, RSFGs make implicit independency assumptions regarding the problem domain.