Active Learning of Nondeterministic Finite State Machines
المؤلفون المشاركون
Pacharoen, Warawoot
Aoki, Toshiaki
Bhattarakosol, Pattarasinee
Surarerks, Athasit
المصدر
Mathematical Problems in Engineering
العدد
المجلد 2013، العدد 2013 (31 ديسمبر/كانون الأول 2013)، ص ص. 1-11، 11ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2013-12-04
دولة النشر
مصر
عدد الصفحات
11
التخصصات الرئيسية
الملخص EN
We consider the problem of learning nondeterministic finite state machines (NFSMs) from systems where their internal structures are implicit and nondeterministic.
Recently, an algorithm for inferring observable NFSMs (ONFSMs), which are the potentially learnable subclass of NFSMs, has been proposed based on the hypothesis that the complete testing assumption is satisfied.
According to this assumption, with an input sequence (query), the complete set of all possible output sequences is given by the so-called Teacher, so the number of times for asking the same query is not taken into account in the algorithm.
In this paper, we propose LNM*, a refined ONFSM learning algorithm that considers the amount for repeating the same query as one parameter.
Unlike the previous work, our approach does not require all possible output sequences in one answer.
Instead, it tries to observe the possible output sequences by asking the same query many times to the Teacher.
We have proved that LNM* can infer the corresponding ONFSMs of the unknown systems when the number of tries for the same query is adequate to guarantee the complete testing assumption.
Moreover, the proof shows that our algorithm will eventually terminate no matter whether the assumption is fulfilled or not.
We also present the theoretical time complexity analysis of LNM*.
In addition, experimental results demonstrate the practical efficiency of our approach.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Pacharoen, Warawoot& Aoki, Toshiaki& Bhattarakosol, Pattarasinee& Surarerks, Athasit. 2013. Active Learning of Nondeterministic Finite State Machines. Mathematical Problems in Engineering،Vol. 2013, no. 2013, pp.1-11.
https://search.emarefa.net/detail/BIM-1009150
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Pacharoen, Warawoot…[et al.]. Active Learning of Nondeterministic Finite State Machines. Mathematical Problems in Engineering No. 2013 (2013), pp.1-11.
https://search.emarefa.net/detail/BIM-1009150
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Pacharoen, Warawoot& Aoki, Toshiaki& Bhattarakosol, Pattarasinee& Surarerks, Athasit. Active Learning of Nondeterministic Finite State Machines. Mathematical Problems in Engineering. 2013. Vol. 2013, no. 2013, pp.1-11.
https://search.emarefa.net/detail/BIM-1009150
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1009150
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر