Abstract




 
   

IJE TRANSACTIONS A: Basics Vol. 27, No. 1 (January 2014) 29-32   

downloaded Downloaded: 109   viewed Viewed: 1628

  REDUCTION OF COMPUTATIONAL COMPLEXITY IN FINITE STATE AUTOMATA EXPLOSION OF NETWORKED SYSTEM DIAGNOSIS (RESEARCH NOTE)
 
M. Ghasemzadeh
 
( Received: April 06, 2013 – Accepted: June 20, 2013 )
 
 

Abstract    This research puts forward rough finite state automata which have been represented by two variants of BDD called ROBDD and ZBDD. The proposed structures have been used in networked system diagnosis and can overcome cominatorial explosion. In implementation the CUDD - Colorado University Decision Diagrams package is used. A mathematical proof for claimed complexity are provided which shows ZBDD representing has superiority in space and time complexity to ROBDD representing.

 

Keywords    Complexity, Finite State Automata, Networked System Diagnosis, ROBDD

 

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

References   

 

1.     Lin, F., "Diagnosability of discrete event systems and its applications", Discrete Event Dynamic Systems,  Vol. 4, No. 2, (1994), 197-212.

2.     Minato, S.-i., "Zero-suppressed bdds and their applications", International Journal on Software Tools for Technology Transfer,  Vol. 3, No. 2, (2001), 156-170.

3.     Mishchenko, A. Extra library for zdd. Available from: http://www.ee.pdx.edu/ alanmi/research/extra.htm.

4.             Somenzi, F. Cudd package, realease 2.3.1. Available from: http://vlsi.colorado.edu/ fabio/cudd/cuddIntro.html.   





International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir