Complexity Reduction in Finite State Automata Explosion of Networked System Diagnosis

در اين پژوهش با بكارگيري يك گونه خاص از نمودار دودويي تصميم براي نمايش ماشين حالت محدود نشان داده مي شود كه چگونه مي توان اين ساختار را به طور مفيدي براي عيب يابي سيستم-هاي شبكه اي به كار برد. متد پيشنهادي اين مزيت را در اختيار مي گذارد تا درگير تعداد نمايي از تركيب هاي ممكن نشويم. براي پياده سازي متد پيشنهادي از بسته استاندارد ارايه شده توسط دانشگاه كلورادو بهره برده ايم. يك اثبات رياضي نيز براي اين ادعا كه بكارگيري نمودار دودويي تصميم مورد نظر مي تواند بسيار بهتر عمل كند ارايه شده است.

This research puts forward the rough finite state automata which have been represented by two variants of Binary Decision Diagram (BDD) called ROBDD and ZBDD, for networked system diagnosis. Using the suggested data structures can help us overcome the combinatorial explosion which usually occurs in system diagnosis. In implementations and analysis of our experimental results, we used CUDD-Colorado University Decision Diagram package. A mathematical proof for the claimed complexity is provided which shows that ZBDD representation has superiority in space and time complexity to ROBDD representation.