Kolloquiumsvortrag: Dr. Tobias Heindel (University of Hawaii)

02.11.2018 von 14:15 bis 16:00

Seminarraum Ü2/K, Ludewig-Meyn-Str. 2

Titel: Word occurrence counts in stochastic string rewriting systems

Abstract:  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 systems.


Prof. Dr. Dirk Nowokta, 0431/880-4199

Diesen Termin meinem iCal-Kalender hinzufügen