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

摘要

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' 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.