Computationally based modeling of dynamical systems

U ovom multidisciplinarnom radu opisano je, implementirano i primijenjeno modelira-nje jednodimenzionalnih dinamičkih sustava u kojem se isključivo na temelju primlje-nog binarnog vremenskog niza gradi računski model s pridodanim stohastičkim svoj-stvima. U teorijskom uvodu pokazana je korektnost takvog pristupa. Simbolička dina-mika povezana je s kodiranjem u mjerno-modelirajućem kanalu i aproksimirana podni-zovima konačne duljine. Između nekoliko računarskih metodologija Crutchfieldova teorija ε-strojeva odabrana je kao najprikladnija za modeliranje iz vremenskog niza. U njoj je temeljni ε-stroj predstavljen stohastičkim konačnim automatom (SFA), koji je ovdje izveden iz konačnih automata (FA). Ilustrirana je podudarnost stohastičkih nede-terminističkih konačnih automata (SNFA) sa skrivenim Markovljevim modelima teme-ljenim na granama grafa (EOHMM). Dan je i pregled složenijih automata koji su kandi-dati za ε-strojeve viših razina. Uvedene su operativne inačice osnovnih pojmova teorije ε-strojeva: (L, δ)-ekvivalentna uzročna stanja i njihova praktična zamjena ─ (L, δ)-morfovi (nadalje, mor-fovi), te pripadni razredi ekvivalencije. Poznata stanja i njihove vjerojatnosti prijelaza određuju prijelazni tenzor te ε-stroj i SFA. Uvedeni su broj morfovima koreliranih sim-bola i duljina tako istražene korelacije, te duljina korelacije SFA-modela i njegova reku-rentnog ciklusa. Opisan je hijerarhijski proces gradbe ε-strojeva. Iz vremenskog niza kreira se raščlambeno stablo visine D, u kojem se morfovi nalaze kao (L,δ)-jedinstvena podstabla. Ta (pod)stabla ─ s listovima na konstantnoj razini (L) D ─ teorijski su razrađe-na i nazvana ε-(pod)stabla. Njihova se statistika temelji na prosječnom broju bl djece iz čvora na l-toj razini. Glavni računarski doprinos ovog rada izvorni su FM i TFM algoritmi. Oni nalaze morfove (stanja) i njihove međusobne prijelaze i vjerojatnosti, te time definiraju SFA-model sustava. Uz parametre modela L i δ FM algoritam nalazi najdublji morf na razini lDM i općenito staje prije provjere svih podstabla. Stoga kažemo da je on potencijalno površan. Uvjet regularnosti dobivenog SFA jest lDM + L + 1 ≤ D. Uveden je koncept sveo-buhvatnog modeliranja u kojem se varijacijom parametara L i δ ─ uz odabranu minimal-nu rezoluciju potonjeg ─ na zadanom glavnom stablu istražuje cijeli prostor rješenja FM algoritma. Temeljiti (punoprolazni), TFM algoritam provjerava sva podstabla raščlambe-nog stabla, a potom uklanja ona koja su (L, δ)-ekvivalentna nekom ranijem podstablu (morfu). On načelno potvrđuje korektnost rezultata FM algoritma. Oba algoritma garanti-raju minimalnost i determinističnost svojih regularnih SFA-modela, što im je glavna pre-dnost pred drugim algoritmima iste namjene. Iznijeta je cjelovita informacijsko-teorijska analiza primljenog vremenskog niza i SFA-modela. Definirane su njihove stope entropi-ja i različite složenosti, uključujući i statističku složenost. Na izvoran je način ekspliciran rastav ukupne entropije SFA-modela na sumu statističke složenosti i stope entropije mo-dela. Dokazano je da se stopa entropije modela dalje rastavlja na sumu stope entropije niza odaslanog iz modela i nedeterminiranosti prijelaza, ili na sumu stope entropije Mar-kovljevog izvora i novouvedene stope entropije simbola po prijelazu. Definirani teorij-sko-informacijski pokazatelji izračunani su za raznovrsne sustave, a za periodične su i dokazani. Modeliranje do razine SFA ostvareno je u našem programskom alatu DSA. Opisana je implementacija podatkovnih struktura i algoritama korištenih u njegova tri glavna pro-gramska modula: za simulaciju dinamičkih sustava, za hranidbu binarnog raščlambenog (glavnog) stabla i za nalaženje SFA. Pregledavanje vremenskog niza, glavnog stabla, morfova i dobivenih modela omogućeno je u grafičkim sučeljima. Za ostvarenje statisti-čki relevantnog glavnog stabla, vremensko-prostorna složenost procesa hranidbe ekspo-nencijalna je u njegovoj visini D. Dokazana je korektnost izvornih algoritama za nere-kurzivni prolazak kroz stabla te napravljena njihova usporedba s rekurzivnim algori-tmima. FM algoritam unaprijeđen je u odnosu na prvobitnu inačicu. Za njega je imple-mentacija pomno obrazložena, a za vrlo opsežan TFM algoritam u bitnim crtama. Na-pravljena je iscrpna analiza vremenske složenosti FM algoritma za slučajeve različitih glavnih stabala i različitih načina njegova rada. Općenito je ta složenost eksponencijalna u raznim linearnim kombinacijama parametara L i D, a u najgorem slučaju u njihovoj razlici 2D − L. DSA program primijenjen je za modeliranje brojnih sustava. Za njihova su raščlam-bena ε-stabla utvrđene krajnje razine statističke konzistentnosti, odnosno maksimalne visine korektnih glavnih stabala u kojima će se nalaziti morfovi. Te su razine teorijski povezane s točnosti numeričkog izračuna i s Lyapunovljevim eksponentom sustava. Za periodične i sustave zadane pravilom te za potpuno kvazistohastičke sustave dobivaju se točni SFA-modeli i uz uporabu FM i TFM algoritama. To vrijedi i za logističko preslika-vanje u nastupu kaosa na kraju puta udvostručavanjem perioda, za koje porastom dulji-ne L morfa broj stanja SFA divergira. Tu su dobiveni SFA-modeli plauzibilniji od pret-hodno poznatih, a na višoj je razini potvrđen konačan registarski stroj. Logistička presli-kavanja u kaosu na mahove, za Misiurewiczev parametar i nadomak potpunog kaosa pokazuju strukturu izmiješanu s kvazistohastičnosti. Sveobuhvatno modeliranje ovih sustava za zadani L i sve manji δ daje niz sve preciznijih SFA-modela, sa sve većim bro-jem stanja. Na temelju njihovih grafova i izračunanih informacijsko-teorijskih pokazate-lja odabrani su oni najreprezentativniji. Neki su od njih potvrđeni i TFM algoritmom. Takav složen postupak modeliranja učinkovito obavlja humani modelar s pomoću DSA programa. Time je ustanovljena funkcionalna modelirajuća platforma, pogodna za dalj-nju nadogradnju i poopćenja.In this multidisciplinary work we describe, implement, and apply the modeling of one-dimensional dynamical systems in which the computational model with added stochastic properties is built solely from the received binary time series. The introductory theoreti-cal chapters show the correctness of such an approach. Symbolic dynamics is connected to the encoding in the measuring-modeling channel and approximated by the finite-length substrings. Among a few presented methodologies, the Crutchfield theory of ε-machines is selected as the best for the modeling from a time series. The basic ε-machine is presented by a stochastic finite automaton (SFA), which is here derived from the class of finite automata (FA). The equality of the stochastic nondeterministic finite automata (SNFFA) to the edge-output hidden Markov models (EOHMM) is illustrated. The more complex automata suitable for the higher-level ε-machines are also presented. The basic concepts of the theory of ε-machines are given their operational versions: (L, δ)-equivalent causal states and their practical substitutions ─ (L, δ)-morphs (further, morphs), which define the classes of equivalence. Known states and their transitions' probabilities define the transition tensor, and thus an ε-machine and its SFA. The num-ber of the morph-correlated symbols and the morph-investigated correlation length are introduced, as well as the correlation length of the SFA-model and the length of its re-current cycle. The reconstruction of ε-machines is a hierarchical process. From the time series, the parse tree of height D is created, wherefrom morphs are found as (L, δ)-unique subtrees. These ε-(sub)trees ─ with leaves at the constant level (L) D ─ are theo-retically described. Their statistics is based on the average number bl of children from an l-level node. The main computational contributions of this work are original FM and TFM algo-rithms. They find morphs (states), their mutual transitions and probabilities, and thus define the SFA-model of a system. For given L and δ, FM algorithm finds the deepest morph on level lDM and generally stops before having checked all the subtrees. This is called (potential) superficiality. The condition for a regular SFA is lDM + L + 1 ≤ D. The concept of comprehensive modeling is introduced. By the variation of L and δ ─ with a chosen resolution for the latter ─ the whole space of the FM algorithm solutions for a parse tree of height D is being explored. The thorough, TFM algorithm first investigates all the subtrees in the parse tree and then removes those which are (L, δ)-equivalent to earlier subtrees. It confirms the correctness of the FM algorithm results. Both algorithms guarantee the minimality and determinism of their regular SFA-models, which is their main advantage over other algorithms of the same purpose. A complete information-theoretical analysis of the time series and the SFA-model is given. The corresponding entropy rates and various complexities are defined. An original expansion of the SFA total entropy to the sum of statistical complexity and the model entropy rate is present-ed. It is proved that the latter can be resolved as the sum of the entropy rate of the time series emitted from the model and the transition indeterminacy, or the sum of the entro-py rate of the Markov source and the newly introduced symbol-per-transition entropy rate. All defined quantities are calculated for various dynamical systems and proven for the periodic ones. The modeling up to the SFA level is realized by our original DSA programming tool. The implementation of data structures and algorithms used in its three main program-ming modules is presented. Inspection of the time series, main (parse) tree, morphs and the created models is possible via graphical user interfaces. The time-space complexity of the tree-feed process for a statistically relevant main tree is generally exponential in the tree height D. Correctness of the original nonrecursive tree-traversal algorithms was proven, and they were compared to the recursive versions. FM algorithm is upgraded from its first version. Its implementation is described in detail, and the implementation of the extensive TFM algorithm in its essential parts. The exhaustive analysis of FM al-gorithm time complexity is made for the cases of different parse trees and different ways of its operation. For general systems, this complexity is exponential in different linear combinations of parameters L and D and in the worst case in their difference 2D − L. DSA program was applied for the modeling of numerous systems. For their parse ε-trees, the utmost levels of statistical consistency had been determined, so that their morphs were being found from the consistent main trees. Those levels were theoretically connected to the accuracy of numerical calculation and Lyapunov exponent of the sys-tem. For periodical, rule-defined, and fully quasi-stochastic systems, both, FM and TFM algorithms give the exact SFA-models. The same is true for the logistic map at the onset of chaos by the end of the period-doubling route, for which the number of SFA states diverge with increasing morph height L. Here, more plausible SFA-models were obtained than previously known. Also, on a higher level, a finite register machine is confirmed. Logistic maps at the intermittency chaos, Misiurewicz parameter, and near the climax of chaos show structure mixed with quasi-stochasticity. The comprehensive modeling of these systems for a given range of L and decreasing δ gives more and more precise SFA-models, with increasing number of states. Based on their graphs and the calculated in-formation-theoretic indicators, the best representative models are chosen among them. Some of them were confirmed by the TFM algorithm. Such a complex modeling task can be effectively accomplished by a human modeler with the aid of the DSA program. By this, we have provided a functional modeling platform that is suitable for further upgrades and generalizations