Modeliranje dinamičkih sustava s pomoću stohastičkih konačnih automata

scientific master's theses

• Author: Robert Logožar
• Mentor: Leo Budin (mentor)
• Committee member: Siniša Srbljić (predsjednik povjerenstva)
• Committee member: Leo Budin (član povjerenstva)
• Committee member: Nikola Bogunović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Electronics, Microelectronics, Computer and Intelligent Systems); Zagreb
• Defense date and country: 1999-07-14, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

Predstavljen je novi pristup u izučavanju dinamičkih sustava, temeljen na teoriji є-strojeva J. P. Crutchfielda. Zadatak je iznaći model procesa zaključivanjem isključivo na temelju vremenskog niza. Zaokružena je formalna veza između simboličke dinamike i raščlambe vremenskog niza, te razrađena geneza stohastičkih konačnih automata (SFA) iz razreda konačnih automata (FA). Opisan je općeniti algoritam konstrukcije є-strojeva i izvršena njegova specijalizacija za rekonstrukciju SFA. Uveden je pojam statističke složenosti kao kvalitativno nove mjere za strukturnu složenost realnih sustava. Prema načelima objektnog programiranja razvijena je programska podrška koja implementira algoritam gradbe SFA. Prilikom analize vremenskog niza, kao prva razina modela javlja se raščlambeno stablo definirano kao posebna vrsta binarnog stabla. Konstruirani su izvorni algoritmi za prijeredni, poslijeredni i međuredni nerekurzivni prolaz kroz stablo. Algoritam za usporedbu (pod)stabala provjerava njihovu morfološku i vjerojatnosnu strukturu, te predstavlja okosnicu algoritma za pronalaženje jedinstvenih morfova. Jedinstveni morfovi predstavljaju stanja SFA, a uvjetne vjerojatnosti prijelaza definiraju njegova stohastička svojstva. Program je testiran i prezentiran na nizu primjera sustava zadanih pravilnim izrazima. Prikazani su dobiveni modeli SFA i izračunati statistički parametri. Izvršeno je preliminarno istraživanje nelinearnog sustava opisanog logističkom jednadžbom za više parametara te posebno za Misiurewiczev, i kritični parametar početka puta prema kaosu udvostručenjem perioda. Dobiveni rezultati su konzistentni s onima dobivenim od autora teorije. Zbog ostvarene preglednosti prikaza binarnog stabla i dodatnih informacija koje podastire algoritam nalaženja morfova, olakšano je minimiziranje modela, tj. optimiziranje njegove veličine s obzirom na vrijednost vjerojatnosnog parametra.

Abstract (english)

A new approach to the study of dynamical systems, based on J. P. Crutchfields’s theory of є-machines, is presented. The goal is to find a model by inferring solely from a time series. A formal connection between symbolic dynamic and the parsing of the time series is made, and stochastic finite automata (SFA) are derived from the class of finite automata (FA). The general algorithm for construction of є-machines is explained, with emphasize on its specialization to reconstruction of SFA. A notion of statistical complexity is introduced as a qualitatively new measure for structural complexity or realistic systems. Guided by the principles of object-oriented programming, a software platform for the reconstruction of SFA is implemented. A parse tree, defined as a special kind of binary tree, arises as the first level of reconstruction process. Original algorithms implementing preorder, postorder and inorder traverse through the tree structure are devised. An algorithm for comparison of (sub)trees checks their morphological and probabilistic structure, and makes a key role in the process of finding of unique morphs. The latter presents the states of SFA, and the conditional transitional probabilities provide their stochastic properties. The program was tested and presented on a number of example systems. Resulting SFA-based models and corresponding statistical parameters are given. A preliminary investigation of nonlinear system governed by Logistic map is made for several values of its parameter, especially for Misiurewicz and the critical parameter at the first period-doubling onset of chaos. The results obtained are consistent with those of the author of the theory. The clarity of the binary tree interface helps to control the results of the modeling. Additional in-formation obtained from the morph-finding algorithm enables the minimization of the model, i.e. the optimization of its size regarding the probability difference parameter.

• Keywords: Dinamički sustavi; simbolička dinamika; konačni automati; stohastički konačni automati (SFA); teorija є-strojeva; deterministička složenost; statistička složenost; rekonstrukcija SFA; objektno orijentirana programska podrška; klase stabala; klasa morfova; algoritmi; sustav logističke jednadžbe; izranjanje strukture; kaos
• Keywords (english): Dynamical systems; symbolic dynamics; finite automata; stochastic finite automata (SFA); theory of є-machines; deterministic complexity; statistical complexity; reconstruction of SFA; object-oriented program application; tree classes; morph class; algorithms; logistic equation system; emergence of structure; chaos
• Language: croatian
• URN:NBN: urn:nbn:hr:168:491463
• Study programme: Title: Postgraduate master programe in computing; Study programme type: university; Study level: postgraduate; Academic / professional title: magistar inženjer računarstva (magistar inženjer računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-29 14:22:37