Algorithms and data structures for the modelling of dynamical systems by means of stochastic finite automata

Razmatramo dizajn i vremensko-prostornu kompleksnost podatkovnih struktura i originalnih algoritama proisteklih iz DSA programa – alata za modeliranje dinamičkih sustava s pomoću stohastičkih konačnih automata prema teoriji ϵ-strojeva. Učinkovita grupna iteracija generira točke sustava i njihove binarne simbole, te ih pohranjuje u kružne spremnike realizirane s pomoću klasnih članskih poredaka. Riječima ekstrahiranim iz vremenskog niza hranimo dinamički kreirano stablo odabrane visine. U stablu potom nalazimo morfološki i stohastički jedinstvena podstabla ili morfove, uz pomoć algoritma koji uspoređuje (pod)stabla prema njihovim topološkim odrednicama i uvjetnim vjerojatnostima čvorova nasljednika. Teorijska analiza algoritama potkrijepljena je mjerenjem vremena njihovog izvođenja. Članak ilustrira kako implementacija znanstveno-programskog alata za modeliranje kao što je DSA, generira paletu specifičnih algoritamskih rješenja za koje možebitno postoji i šira uporaba.We elaborate on the design and time-space complexity of data structures and several original algorithms that resulted from the DSA program – a tool that simulates dynamical systems and produces their stochastic finite automata models according to the theory of ϵ-machines. An efficient batch iteration algorithm generates the system points and their binary symbols, and stores them in circular buffers realized as class member arrays. The words extracted from the time series are fed into a dynamically created binary tree of selected height. The tree is then searched for morphologically and stochastically unique subtrees or morphs, by aid of an algorithm that compares (sub)trees by their topology and the descendant nodes\u27 conditional probabilities. The theoretical analysis of algorithms is corroborated by their execution time measurements. The paper exemplifies how an implementation of a scientific modelling tool like the DSA, generates a range of specific algorithmic solutions that can possibly find their broader use