TY - CONF AB - We study turn-based stochastic zero-sum games with lexicographic preferences over reachability and safety objectives. Stochastic games are standard models in control, verification, and synthesis of stochastic reactive systems that exhibit both randomness as well as angelic and demonic non-determinism. Lexicographic order allows to consider multiple objectives with a strict preference order over the satisfaction of the objectives. To the best of our knowledge, stochastic games with lexicographic objectives have not been studied before. We establish determinacy of such games and present strategy and computational complexity results. For strategy complexity, we show that lexicographically optimal strategies exist that are deterministic and memory is only required to remember the already satisfied and violated objectives. For a constant number of objectives, we show that the relevant decision problem is in NP∩coNP , matching the current known bound for single objectives; and in general the decision problem is PSPACE -hard and can be solved in NEXPTIME∩coNEXPTIME . We present an algorithm that computes the lexicographically optimal strategies via a reduction to computation of optimal strategies in a sequence of single-objectives games. We have implemented our algorithm and report experimental results on various case studies. AU - Chatterjee, Krishnendu AU - Katoen, Joost P AU - Weininger, Maximilian AU - Winkler, Tobias ID - 8272 SN - 03029743 T2 - International Conference on Computer Aided Verification TI - Stochastic games with lexicographic reachability-safety objectives VL - 12225 ER - TY - CHAP AB - The polymerization–depolymerization dynamics of cytoskeletal proteins play essential roles in the self-organization of cytoskeletal structures, in eukaryotic as well as prokaryotic cells. While advances in fluorescence microscopy and in vitro reconstitution experiments have helped to study the dynamic properties of these complex systems, methods that allow to collect and analyze large quantitative datasets of the underlying polymer dynamics are still missing. Here, we present a novel image analysis workflow to study polymerization dynamics of active filaments in a nonbiased, highly automated manner. Using treadmilling filaments of the bacterial tubulin FtsZ as an example, we demonstrate that our method is able to specifically detect, track and analyze growth and shrinkage of polymers, even in dense networks of filaments. We believe that this automated method can facilitate the analysis of a large variety of dynamic cytoskeletal systems, using standard time-lapse movies obtained from experiments in vitro as well as in the living cell. Moreover, we provide scripts implementing this method as supplementary material. AU - Dos Santos Caldas, Paulo R AU - Radler, Philipp AU - Sommer, Christoph M AU - Loose, Martin ED - Tran, Phong ID - 7572 SN - 0091679X T2 - Methods in Cell Biology TI - Computational analysis of filament polymerization dynamics in cytoskeletal networks VL - 158 ER - TY - JOUR AB - Most bacteria accomplish cell division with the help of a dynamic protein complex called the divisome, which spans the cell envelope in the plane of division. Assembly and activation of this machinery are coordinated by the tubulin-related GTPase FtsZ, which was found to form treadmilling filaments on supported bilayers in vitro1, as well as in live cells, in which filaments circle around the cell division site2,3. Treadmilling of FtsZ is thought to actively move proteins around the division septum, thereby distributing peptidoglycan synthesis and coordinating the inward growth of the septum to form the new poles of the daughter cells4. However, the molecular mechanisms underlying this function are largely unknown. Here, to study how FtsZ polymerization dynamics are coupled to downstream proteins, we reconstituted part of the bacterial cell division machinery using its purified components FtsZ, FtsA and truncated transmembrane proteins essential for cell division. We found that the membrane-bound cytosolic peptides of FtsN and FtsQ co-migrated with treadmilling FtsZ–FtsA filaments, but despite their directed collective behaviour, individual peptides showed random motion and transient confinement. Our work suggests that divisome proteins follow treadmilling FtsZ filaments by a diffusion-and-capture mechanism, which can give rise to a moving zone of signalling activity at the division site. AU - Baranova, Natalia S. AU - Radler, Philipp AU - Hernández-Rocamora, Víctor M. AU - Alfonso, Carlos AU - Lopez Pelegrin, Maria D AU - Rivas, Germán AU - Vollmer, Waldemar AU - Loose, Martin ID - 7387 JF - Nature Microbiology SN - 2058-5276 TI - Diffusion and capture permits dynamic coupling between treadmilling FtsZ filaments and cell division proteins VL - 5 ER - TY - JOUR AB - Fejes Tóth [3] studied approximations of smooth surfaces in three-space by piecewise flat triangular meshes with a given number of vertices on the surface that are optimal with respect to Hausdorff distance. He proves that this Hausdorff distance decreases inversely proportional with the number of vertices of the approximating mesh if the surface is convex. He also claims that this Hausdorff distance is inversely proportional to the square of the number of vertices for a specific non-convex surface, namely a one-sheeted hyperboloid of revolution bounded by two congruent circles. We refute this claim, and show that the asymptotic behavior of the Hausdorff distance is linear, that is the same as for convex surfaces. AU - Vegter, Gert AU - Wintraecken, Mathijs ID - 8163 IS - 2 JF - Studia Scientiarum Mathematicarum Hungarica SN - 0081-6906 TI - Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes VL - 57 ER - TY - JOUR AB - We study relations between evidence theory and S-approximation spaces. Both theories have their roots in the analysis of Dempsterchr('39')s multivalued mappings and lower and upper probabilities, and have close relations to rough sets. We show that an S-approximation space, satisfying a monotonicity condition, can induce a natural belief structure which is a fundamental block in evidence theory. We also demonstrate that one can induce a natural belief structure on one set, given a belief structure on another set, if the two sets are related by a partial monotone S-approximation space. AU - Shakiba, A. AU - Goharshady, Amir Kafshdar AU - Hooshmandasl, M.R. AU - Alambardar Meybodi, M. ID - 8671 IS - 2 JF - Iranian Journal of Mathematical Sciences and Informatics SN - 1735-4463 TI - A note on belief structures and s-approximation spaces VL - 15 ER -