ADFA
- Fig 1. Automat izomorf cu un ADFA antrenat sa recunoasca numere separate prin spatii
. Ce sunt ADFA ?
Automatele finite deterministe adaptive sunt niste sisteme formate din matrice de multimi care se pot:
a) antrena prin prezentarea de atomi lexicali
b) exploata punandu-le sa recunoasca atomi lexicali similari cu cei cu care s-au antrenat, sau mai complexi dar care pastreaza aceleasi succesiuni de clase de caractere (cifre,litere, spatii etc).
Sunt o curioasa contribu]ie intr-un domeniu - teoria automatelor - considerat inchis de circa 30 de ani. Se pot considera de asemenea ca fiind la limita dintre doua domenii: teoria limbajelor formale si a automatelor si inteligenta artificiala.
Un avantaj al lor este viteza de recunoastere a textelor similare cu sablonul. Deoarece dupa antrenare ceea ce rezulta este un automat finit determinist (care s-a configurat in mod adaptabil /adaptiv) el are timpul de procesare a atomilor lexicali pe care ii va recunoaste de ordinul de marime al timpilor de la automate finite deterministe: O(n) - timp liniar raportat la lungimea intrarii. Avantajul contribuie la viteza la sistemele antispam realizate cu aceasta tehnologie.
. Aplicatiile ADFA
Sunt variate. Initial ADFA-urile au fost concepute de Dan Popa de la Univ. din Bacau (actualmente "Univ.Vasile Alecsandri" din Bacau) pentru a inlocui faza de proiectare a analizoarelor lexicale ale compilatoarelor cu o faza de antrenare a unor sisteme adaptabile/adaptive. Experimentul a reusit si au fost publicate o serie de lucrari, vedeti bibliografia. Actualmente am inceput sa folosim aceasta tehnologie pentru producere de software de recunoastere. Referinte gasiti in lucrarea (3) si in bibliografia ei.
. Bibliografie
1.Popa Dan; Adaptable Tokenizer for Programming Languages , Simpozionul International al Tinerilor Cercetatori, ASEM, Chisinau 2004, pg 55-57, ISBN 9975-75-239-x <DOWNLOAD> Draft despre Adaptive Automata Old file, check it, it may include old viruses !?!
2.Popa Dan ; Adaptive DFA based on array of sets, Studii si Cercetari Ştiinţifice, Seria Matematica, Nr 15 (2005) p 113-121, ISSN 1224 - 2519. Download a rebuilt .pdf file.
3.Popa Dan - Adaptive DFA–The development of adaptable methods, Proceedings of The 34th Annual Congress of the American Romanian Academy of Arts and Sciences (ARA), Presses Internationales Polytechnique, Montreal,Quebec ,2010, pp 421-424. Download the draft paper .pdf format.
Un capitol continand Teoria Automatelor Adaptive Finit Deterministe este inclus in teza de doctorat (de la UNIVERSITATEA "ALEXANDRU IOAN CUZA" DIN IASI FACULTATEA DE INFORMATICA):
4. Metode si tehnici de realizare a interpretoarelor adaptabile , indrumata de Prof.Univ.Doctor.Habilitat.Dumitru Todoroi,Doctorand: Dan Popa. Este vorba de capitolul al X-lea care s-a adaugat la inceputul anului 2010 celor IX capitole prezentate la sustinerea in catedra din Oct.2009. http://www.haskell.org/wikiupload/1/12/PR_INT_47_TEZA_.pdf.zip Cereti parola de la ambele adresele de e-mail din lucrarea (3) daca nu puteti desface arhiva. Daca de la o adresa nu vi se raspunde folositi, mai bine, adresa publica, cea de forma numeVprenume@yahoo.com.
. Prezentari
.... Automate adaptive implementate in Haskell: Prezentarea in format .pdf aferenta lucrarii (3) - Download the .pdf format here! ....
. Performante
Deoarece dupa antrenare ADFA-urile devin izomorfe cu niste automate dintr-o submultime de automate finite deterministe, timpul in care ele analizeaza un atom lexical sau o data oarecare este cel mult egal cu lungimea acestei intrari. S-ar putea s-o rejecteze (sa n-o accepte) inainte chiar de a o termina de prelucrat.
. Aplicatii
In domeniul sistemelor anti-spam. In domeniul supravegherii video automate. ... vor urma si altele.
Pagina dedicata automatelor adaptive. In dezvoltare...