Word occurrence counts in stochastic string rewriting systems
02.11.2018 von 14:00 bis 15:00
The “population” of a multi-type branching process is a multiset over types. Imposing a linear order on this population yields a stochastic process with strings over types as states. The talk focuses on a particularly well-behaved instance of such “ordered” branching processes, namely stochastic string rewriting systems whose rules are context-free in the Chomskian sense, i.e., letters are replaced by words. The main topic of the talk is computability of the continuous-time evolution of the expected number of occurrences of a fixed “word motif” in stochastic string rewriting systems. The main theoretical result is (TTE) computability of the mean occurrence count independent of the initial distribution. This is an instance of a much more general computability result about continuous-time Markov chains, which in turn relies on a result of Weihrauch and Zhong.
One issue of the theoretical result is inefficiency of numerical methods, which run into a state-space explosion problem that is aggravated by the fact that for each “reachable” word, we also have to take into account a suitable approximation of a real number. The talk will conclude with a short sketch of a research direction towards “solving” stochastic string and graph rewriting