Personal tools

ADFA

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(. Ce sunt ADFA ?)
 
(11 intermediate revisions by one user not shown)
Line 1: Line 1:
 
[[Category:Ro]]
 
[[Category:Ro]]
   
  +
<center>
  +
http://www.haskell.org/wikiupload/5/56/ADFA.png
  +
*'''Fig 1. Automat izomorf cu un ADFA antrenat sa recunoasca numere separate prin spatii'''
  +
</center>
 
==. Ce sunt ADFA ? ==
 
==. Ce sunt ADFA ? ==
   
 
Automatele finite deterministe adaptive sunt niste sisteme formate din matrice de multimi care se pot:
 
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 interesanta contribu]ie intr-un domeniu - teoria automatelor - considerat inchis de circa 30 de ani.
 
   
  +
a) ''antrena'' prin prezentarea de atomi lexicali
   
==. Aplicatiile ADFA ==
+
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 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.
+
Sunt o curioasa contributie 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. Acest avantaj: viteza sistemele antispam realizate cu aceasta tehnologie merita luat in consideratie.
  +
  +
==. 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 [http://www.haskell.org/wikiupload/c/ce/AdaptiveDFA-Bc_%28copy%29-pg113.pdf (3) si in bibliografia ei.]
   
 
==. Bibliografie ==
 
==. 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
 
1.Popa Dan; [[Adaptable Tokenizer for Programming Languages]] , Simpozionul International al Tinerilor Cercetatori, ASEM, Chisinau 2004, pg 55-57, ISBN 9975-75-239-x
[http://www.haskell.org/sitewiki/images/9/9e/SITC2004.PRN.pdf <DOWNLOAD> Draft despre Adaptive Automata ] Old file, check it, it may include old viruses !?!
+
[http://www.haskell.org/wikiupload/9/9e/SITC2004.PRN.pdf <DOWNLOAD> Draft despre Adaptive Automata ] Old file, check it, it may include old viruses !?!
   
   
2.Popa Dan ; [http://www.haskell.org/sitewiki/images/c/ce/AdaptiveDFA-Bc_%28copy%29-pg113.pdf Adaptive DFA based on array of sets], Studii si Cercetari Ştiinţifice, Seria Matematica, Nr 15 (2005) p 113-121, ISSN 1224 - 2519. [http://www.haskell.org/sitewiki/images/c/ce/AdaptiveDFA-Bc_%28copy%29-pg113.pdf Download a rebuilt .pdf file.]
+
2.Popa Dan ; [http://www.haskell.org/wikiupload/c/ce/AdaptiveDFA-Bc_%28copy%29-pg113.pdf Adaptive DFA based on array of sets], Studii si Cercetari Ştiinţifice, Seria Matematica, Nr 15 (2005) p 113-121, ISSN 1224 - 2519. [http://www.haskell.org/wikiupload/c/ce/AdaptiveDFA-Bc_%28copy%29-pg113.pdf 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
+
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. [http://www.haskell.org/wikiupload/e/e4/ARA1-paper.pdf Download the draft paper .pdf format.]
   
Un capitol dedicat lor este inclus in teza de doctorat (de la UNIVERSITATEA "ALEXANDRU IOAN CUZA" DIN IASI FACULTATEA DE INFORMATICA) ''Metode si tehnici de realizare a interpretoarelor adaptabile'' , indrumata de Prof.Univ.Doctor.Habilitat.Dumitru Todoroi, Doctorand: Dan Popa.
+
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.
 
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 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 ==
 
==. Prezentari ==
 
....
 
....
Automate adaptive reimplementate in Haskell:
+
Automate adaptive implementate in Haskell: [http://www.haskell.org/wikiupload/8/83/ARA1.pdf Prezentarea in format .pdf] aferenta [http://www.haskell.org/wikiupload/e/e4/ARA1-paper.pdf 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.
+
  +
  +
Pagina dedicata automatelor adaptive. In dezvoltare...

Latest revision as of 12:55, 7 May 2011


ADFA.png

  • Fig 1. Automat izomorf cu un ADFA antrenat sa recunoasca numere separate prin spatii

Contents

[edit] 1 . 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 contributie 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. Acest avantaj: viteza sistemele antispam realizate cu aceasta tehnologie merita luat in consideratie.

[edit] 2 . 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.

[edit] 3 . 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.

[edit] 4 . Prezentari

.... Automate adaptive implementate in Haskell: Prezentarea in format .pdf aferenta lucrarii (3) - Download the .pdf format here! ....

[edit] 5 . 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.

[edit] 6 . Aplicatii

In domeniul sistemelor anti-spam. In domeniul supravegherii video automate. ... vor urma si altele.



Pagina dedicata automatelor adaptive. In dezvoltare...