[{"department":[{"_id":"EdHa"}],"isi":1,"intvolume":"       365","page":"705-710","date_published":"2019-08-16T00:00:00Z","type":"journal_article","year":"2019","issue":"6454","pmid":1,"language":[{"iso":"eng"}],"title":"Active cell migration is critical for steady-state epithelial turnover in the gut","publication":"Science","date_created":"2019-08-25T22:00:51Z","quality_controlled":"1","scopus_import":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"ista":"Krndija D, Marjou FE, Guirao B, Richon S, Leroy O, Bellaiche Y, Hannezo EB, Vignjevic DM. 2019. Active cell migration is critical for steady-state epithelial turnover in the gut. Science. 365(6454), 705–710.","short":"D. Krndija, F.E. Marjou, B. Guirao, S. Richon, O. Leroy, Y. Bellaiche, E.B. Hannezo, D.M. Vignjevic, Science 365 (2019) 705–710.","ama":"Krndija D, Marjou FE, Guirao B, et al. Active cell migration is critical for steady-state epithelial turnover in the gut. <i>Science</i>. 2019;365(6454):705-710. doi:<a href=\"https://doi.org/10.1126/science.aau3429\">10.1126/science.aau3429</a>","mla":"Krndija, Denis, et al. “Active Cell Migration Is Critical for Steady-State Epithelial Turnover in the Gut.” <i>Science</i>, vol. 365, no. 6454, American Association for the Advancement of Science, 2019, pp. 705–10, doi:<a href=\"https://doi.org/10.1126/science.aau3429\">10.1126/science.aau3429</a>.","ieee":"D. Krndija <i>et al.</i>, “Active cell migration is critical for steady-state epithelial turnover in the gut,” <i>Science</i>, vol. 365, no. 6454. American Association for the Advancement of Science, pp. 705–710, 2019.","apa":"Krndija, D., Marjou, F. E., Guirao, B., Richon, S., Leroy, O., Bellaiche, Y., … Vignjevic, D. M. (2019). Active cell migration is critical for steady-state epithelial turnover in the gut. <i>Science</i>. American Association for the Advancement of Science. <a href=\"https://doi.org/10.1126/science.aau3429\">https://doi.org/10.1126/science.aau3429</a>","chicago":"Krndija, Denis, Fatima El Marjou, Boris Guirao, Sophie Richon, Olivier Leroy, Yohanns Bellaiche, Edouard B Hannezo, and Danijela Matic Vignjevic. “Active Cell Migration Is Critical for Steady-State Epithelial Turnover in the Gut.” <i>Science</i>. American Association for the Advancement of Science, 2019. <a href=\"https://doi.org/10.1126/science.aau3429\">https://doi.org/10.1126/science.aau3429</a>."},"volume":365,"status":"public","oa_version":"None","date_updated":"2023-08-29T07:16:40Z","month":"08","publication_status":"published","author":[{"full_name":"Krndija, Denis","first_name":"Denis","last_name":"Krndija"},{"last_name":"Marjou","first_name":"Fatima El","full_name":"Marjou, Fatima El"},{"first_name":"Boris","full_name":"Guirao, Boris","last_name":"Guirao"},{"first_name":"Sophie","full_name":"Richon, Sophie","last_name":"Richon"},{"last_name":"Leroy","first_name":"Olivier","full_name":"Leroy, Olivier"},{"full_name":"Bellaiche, Yohanns","first_name":"Yohanns","last_name":"Bellaiche"},{"last_name":"Hannezo","id":"3A9DB764-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6005-1561","full_name":"Hannezo, Edouard B","first_name":"Edouard B"},{"first_name":"Danijela Matic","full_name":"Vignjevic, Danijela Matic","last_name":"Vignjevic"}],"_id":"6832","external_id":{"pmid":["31416964"],"isi":["000481688700050"]},"publisher":"American Association for the Advancement of Science","day":"16","article_processing_charge":"No","abstract":[{"lang":"eng","text":"Steady-state turnover is a hallmark of epithelial tissues throughout adult life. Intestinal epithelial turnover is marked by continuous cell migration, which is assumed to be driven by mitotic pressure from the crypts. However, the balance of forces in renewal remains ill-defined. Combining biophysical modeling and quantitative three-dimensional tissue imaging with genetic and physical manipulations, we revealed the existence of an actin-related protein 2/3 complex–dependent active migratory force, which explains quantitatively the profiles of cell speed, density, and tissue tension along the villi. Cells migrate collectively with minimal rearrangements while displaying dual—apicobasal and front-back—polarity characterized by actin-rich basal protrusions oriented in the direction of migration. We propose that active migration is a critical component of gut epithelial turnover."}],"doi":"10.1126/science.aau3429"},{"oa_version":"None","date_updated":"2023-08-29T07:42:20Z","month":"08","external_id":{"isi":["000478029000003"],"pmid":["31371826"]},"_id":"6837","publisher":"Springer Nature","author":[{"last_name":"Tavano","id":"2F162F0C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-9970-7804","full_name":"Tavano, Ste","first_name":"Ste"},{"full_name":"Heisenberg, Carl-Philipp J","orcid":"0000-0002-0912-4566","first_name":"Carl-Philipp J","id":"39427864-F248-11E8-B48F-1D18A9856A87","last_name":"Heisenberg"}],"publication_status":"published","day":"01","doi":"10.1038/s41556-019-0369-3","abstract":[{"lang":"eng","text":"Migrasomes are a recently discovered type of extracellular vesicles that are characteristically generated along retraction fibers in migrating cells. Two studies now show how migrasomes are formed and how they function in the physiologically relevant context of the developing zebrafish embryo."}],"article_processing_charge":"No","isi":1,"publication_identifier":{"eissn":["1476-4679"]},"department":[{"_id":"CaHe"}],"intvolume":"        21","page":"918-920","date_published":"2019-08-01T00:00:00Z","type":"journal_article","issue":"8","year":"2019","pmid":1,"language":[{"iso":"eng"}],"publication":"Nature Cell Biology","title":"Migrasomes take center stage","date_created":"2019-09-01T22:00:57Z","quality_controlled":"1","scopus_import":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Tavano, Ste, and Carl-Philipp J Heisenberg. “Migrasomes Take Center Stage.” <i>Nature Cell Biology</i>. Springer Nature, 2019. <a href=\"https://doi.org/10.1038/s41556-019-0369-3\">https://doi.org/10.1038/s41556-019-0369-3</a>.","ieee":"S. Tavano and C.-P. J. Heisenberg, “Migrasomes take center stage,” <i>Nature Cell Biology</i>, vol. 21, no. 8. Springer Nature, pp. 918–920, 2019.","apa":"Tavano, S., &#38; Heisenberg, C.-P. J. (2019). Migrasomes take center stage. <i>Nature Cell Biology</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s41556-019-0369-3\">https://doi.org/10.1038/s41556-019-0369-3</a>","ama":"Tavano S, Heisenberg C-PJ. Migrasomes take center stage. <i>Nature Cell Biology</i>. 2019;21(8):918-920. doi:<a href=\"https://doi.org/10.1038/s41556-019-0369-3\">10.1038/s41556-019-0369-3</a>","mla":"Tavano, Ste, and Carl-Philipp J. Heisenberg. “Migrasomes Take Center Stage.” <i>Nature Cell Biology</i>, vol. 21, no. 8, Springer Nature, 2019, pp. 918–20, doi:<a href=\"https://doi.org/10.1038/s41556-019-0369-3\">10.1038/s41556-019-0369-3</a>.","short":"S. Tavano, C.-P.J. Heisenberg, Nature Cell Biology 21 (2019) 918–920.","ista":"Tavano S, Heisenberg C-PJ. 2019. Migrasomes take center stage. Nature Cell Biology. 21(8), 918–920."},"status":"public","volume":21},{"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","file_id":"6916","creator":"mgiacobbe","relation":"main_file","file_size":4100685,"file_name":"giacobbe_thesis.pdf","checksum":"773beaf4a85dc2acc2c12b578fbe1965","date_created":"2019-09-27T14:15:05Z","date_updated":"2020-07-14T12:47:43Z","content_type":"application/pdf"},{"access_level":"closed","file_id":"6917","creator":"mgiacobbe","file_name":"giacobbe_thesis_src.tar.gz","checksum":"97f1c3da71feefd27e6e625d32b4c75b","relation":"source_file","file_size":7959732,"content_type":"application/gzip","date_created":"2019-09-27T14:22:04Z","date_updated":"2020-07-14T12:47:43Z"}],"title":"Automatic time-unbounded reachability analysis of hybrid systems","corr_author":"1","year":"2019","type":"dissertation","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","citation":{"short":"M. Giacobbe, Automatic Time-Unbounded Reachability Analysis of Hybrid Systems, Institute of Science and Technology Austria, 2019.","ista":"Giacobbe M. 2019. Automatic time-unbounded reachability analysis of hybrid systems. Institute of Science and Technology Austria.","ama":"Giacobbe M. Automatic time-unbounded reachability analysis of hybrid systems. 2019. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:6894\">10.15479/AT:ISTA:6894</a>","mla":"Giacobbe, Mirco. <i>Automatic Time-Unbounded Reachability Analysis of Hybrid Systems</i>. Institute of Science and Technology Austria, 2019, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:6894\">10.15479/AT:ISTA:6894</a>.","ieee":"M. Giacobbe, “Automatic time-unbounded reachability analysis of hybrid systems,” Institute of Science and Technology Austria, 2019.","apa":"Giacobbe, M. (2019). <i>Automatic time-unbounded reachability analysis of hybrid systems</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:6894\">https://doi.org/10.15479/AT:ISTA:6894</a>","chicago":"Giacobbe, Mirco. “Automatic Time-Unbounded Reachability Analysis of Hybrid Systems.” Institute of Science and Technology Austria, 2019. <a href=\"https://doi.org/10.15479/AT:ISTA:6894\">https://doi.org/10.15479/AT:ISTA:6894</a>."},"status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_created":"2019-09-22T14:08:44Z","degree_awarded":"PhD","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"647"},{"relation":"part_of_dissertation","status":"public","id":"631"},{"relation":"part_of_dissertation","status":"public","id":"140"}]},"OA_place":"publisher","license":"https://creativecommons.org/licenses/by/4.0/","publication_identifier":{"eissn":["2663-337X"]},"supervisor":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"}],"department":[{"_id":"ToHe"}],"page":"132","date_published":"2019-09-30T00:00:00Z","alternative_title":["ISTA Thesis"],"ddc":["000"],"abstract":[{"lang":"eng","text":"Hybrid automata combine finite automata and dynamical systems, and model the interaction of digital with physical systems. Formal analysis that can guarantee the safety of all behaviors or rigorously witness failures, while unsolvable in general, has been tackled algorithmically using, e.g., abstraction, bounded model-checking, assisted theorem proving.\r\nNevertheless, very few methods have addressed the time-unbounded reachability analysis of hybrid automata and, for current sound and automatic tools, scalability remains critical. We develop methods for the polyhedral abstraction of hybrid automata, which construct coarse overapproximations and tightens them incrementally, in a CEGAR fashion. We use template polyhedra, i.e., polyhedra whose facets are normal to a given set of directions.\r\nWhile, previously, directions were given by the user, we introduce (1) the first method\r\nfor computing template directions from spurious counterexamples, so as to generalize and\r\neliminate them. The method applies naturally to convex hybrid automata, i.e., hybrid\r\nautomata with (possibly non-linear) convex constraints on derivatives only, while for linear\r\nODE requires further abstraction. Specifically, we introduce (2) the conic abstractions,\r\nwhich, partitioning the state space into appropriate (possibly non-uniform) cones, divide\r\ncurvy trajectories into relatively straight sections, suitable for polyhedral abstractions.\r\nFinally, we introduce (3) space-time interpolation, which, combining interval arithmetic\r\nand template refinement, computes appropriate (possibly non-uniform) time partitioning\r\nand template directions along spurious trajectories, so as to eliminate them.\r\nWe obtain sound and automatic methods for the reachability analysis over dense\r\nand unbounded time of convex hybrid automata and hybrid automata with linear ODE.\r\nWe build prototype tools and compare—favorably—our methods against the respective\r\nstate-of-the-art tools, on several benchmarks."}],"article_processing_charge":"No","doi":"10.15479/AT:ISTA:6894","_id":"6894","author":[{"first_name":"Mirco","orcid":"0000-0001-8180-0904","full_name":"Giacobbe, Mirco","last_name":"Giacobbe","id":"3444EA5E-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","publisher":"Institute of Science and Technology Austria","day":"30","oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:43Z","oa":1,"date_updated":"2026-04-16T09:55:03Z","has_accepted_license":"1","month":"09"},{"file":[{"content_type":"application/pdf","date_created":"2019-10-08T12:47:19Z","date_updated":"2020-07-14T12:47:44Z","file_name":"LIPIcs-DISC-2019-29.pdf","checksum":"2d2202f90c6ac991e50876451627c4b5","file_size":639378,"relation":"main_file","creator":"jrybicki","access_level":"open_access","file_id":"6934"}],"language":[{"iso":"eng"}],"publication":"33rd International Symposium on Distributed Computing","title":"Byzantine approximate agreement on graphs","year":"2019","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.” <i>33rd International Symposium on Distributed Computing</i>, vol. 146, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17, doi:<a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">10.4230/LIPICS.DISC.2019.29</a>.","ama":"Nowak T, Rybicki J. Byzantine approximate agreement on graphs. In: <i>33rd International Symposium on Distributed Computing</i>. Vol 146. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:29:1--29:17. doi:<a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">10.4230/LIPICS.DISC.2019.29</a>","ista":"Nowak T, Rybicki J. 2019. Byzantine approximate agreement on graphs. 33rd International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 146, 29:1--29:17.","short":"T. Nowak, J. Rybicki, in:, 33rd International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17.","chicago":"Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.” In <i>33rd International Symposium on Distributed Computing</i>, 146:29:1--29:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">https://doi.org/10.4230/LIPICS.DISC.2019.29</a>.","apa":"Nowak, T., &#38; Rybicki, J. (2019). Byzantine approximate agreement on graphs. In <i>33rd International Symposium on Distributed Computing</i> (Vol. 146, p. 29:1--29:17). Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">https://doi.org/10.4230/LIPICS.DISC.2019.29</a>","ieee":"T. Nowak and J. Rybicki, “Byzantine approximate agreement on graphs,” in <i>33rd International Symposium on Distributed Computing</i>, Budapest, Hungary, 2019, vol. 146, p. 29:1--29:17."},"status":"public","volume":146,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_created":"2019-10-08T12:41:38Z","quality_controlled":"1","scopus_import":"1","department":[{"_id":"DaAl"}],"publication_identifier":{"eisbn":["978-3-95977-126-9"]},"arxiv":1,"page":"29:1--29:17","alternative_title":["LIPIcs"],"date_published":"2019-11-01T00:00:00Z","intvolume":"       146","ec_funded":1,"ddc":["004"],"doi":"10.4230/LIPICS.DISC.2019.29","article_processing_charge":"No","abstract":[{"lang":"eng","text":"Consider a distributed system with n processors out of which f can be Byzantine faulty. In the\r\napproximate agreement task, each processor i receives an input value xi and has to decide on an\r\noutput value yi such that\r\n1. the output values are in the convex hull of the non-faulty processors’ input values,\r\n2. the output values are within distance d of each other.\r\n\r\n\r\nClassically, the values are assumed to be from an m-dimensional Euclidean space, where m ≥ 1.\r\nIn this work, we study the task in a discrete setting, where input values with some structure\r\nexpressible as a graph. Namely, the input values are vertices of a finite graph G and the goal is to\r\noutput vertices that are within distance d of each other in G, but still remain in the graph-induced\r\nconvex hull of the input values. For d = 0, the task reduces to consensus and cannot be solved with\r\na deterministic algorithm in an asynchronous system even with a single crash fault. For any d ≥ 1,\r\nwe show that the task is solvable in asynchronous systems when G is chordal and n > (ω + 1)f,\r\nwhere ω is the clique number of G. In addition, we give the first Byzantine-tolerant algorithm for a\r\nvariant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact\r\nvariants of these and related tasks over a large class of combinatorial structures."}],"_id":"6931","author":[{"last_name":"Nowak","first_name":"Thomas","full_name":"Nowak, Thomas"},{"first_name":"Joel","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki"}],"publication_status":"published","external_id":{"arxiv":["1908.02743"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"conference":{"end_date":"2019-10-18","name":"DISC: Symposium on Distributed Computing","location":"Budapest, Hungary","start_date":"2019-10-14"},"day":"01","file_date_updated":"2020-07-14T12:47:44Z","oa_version":"Published Version","keyword":["consensus","approximate agreement","Byzantine faults","chordal graphs","lattice agreement"],"oa":1,"has_accepted_license":"1","date_updated":"2025-07-10T11:54:03Z","month":"11"},{"article_processing_charge":"No","abstract":[{"text":"Graph games and Markov decision processes (MDPs) are standard models in reactive synthesis and verification of probabilistic systems with nondeterminism. The class of   𝜔 -regular winning conditions; e.g., safety, reachability, liveness, parity conditions; provides a robust and expressive specification formalism for properties that arise in analysis of reactive systems. The resolutions of nondeterminism in games and MDPs are represented as strategies, and we consider succinct representation of such strategies. The decision-tree data structure from machine learning retains the flavor of decisions of strategies and allows entropy-based minimization to obtain succinct trees. However, in contrast to traditional machine-learning problems where small errors are allowed, for winning strategies in graph games and MDPs no error is allowed, and the decision tree must represent the entire strategy. In this work we propose decision trees with linear classifiers for representation of strategies in graph games and MDPs. We have implemented strategy representation using this data structure and we present experimental results for problems on graph games and MDPs, which show that this new data structure presents a much more efficient strategy representation as compared to standard decision trees.","lang":"eng"}],"doi":"10.1007/978-3-030-30281-8_7","day":"04","conference":{"end_date":"2019-09-12","name":"QEST: Quantitative Evaluation of Systems","start_date":"2019-09-10","location":"Glasgow, United Kingdom"},"project":[{"name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407"},{"name":"Rigorous Systems Engineering","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23","call_identifier":"FWF"},{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003"}],"_id":"6942","author":[{"last_name":"Ashok","full_name":"Ashok, Pranav","first_name":"Pranav"},{"last_name":"Brázdil","full_name":"Brázdil, Tomáš","first_name":"Tomáš"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"last_name":"Křetínský","first_name":"Jan","full_name":"Křetínský, Jan"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","first_name":"Christoph"},{"id":"3AF3DA7C-F248-11E8-B48F-1D18A9856A87","last_name":"Toman","full_name":"Toman, Viktor","orcid":"0000-0001-9036-063X","first_name":"Viktor"}],"external_id":{"arxiv":["1906.08178"],"isi":["000679281300007"]},"publisher":"Springer Nature","publication_status":"published","main_file_link":[{"url":"https://arxiv.org/abs/1906.08178","open_access":"1"}],"month":"09","date_updated":"2025-04-14T13:51:05Z","oa_version":"Preprint","oa":1,"volume":11785,"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"ieee":"P. Ashok, T. Brázdil, K. Chatterjee, J. Křetínský, C. Lampert, and V. Toman, “Strategy representation by decision trees with linear classifiers,” in <i>16th International Conference on Quantitative Evaluation of Systems</i>, Glasgow, United Kingdom, 2019, vol. 11785, pp. 109–128.","apa":"Ashok, P., Brázdil, T., Chatterjee, K., Křetínský, J., Lampert, C., &#38; Toman, V. (2019). Strategy representation by decision trees with linear classifiers. In <i>16th International Conference on Quantitative Evaluation of Systems</i> (Vol. 11785, pp. 109–128). Glasgow, United Kingdom: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-30281-8_7\">https://doi.org/10.1007/978-3-030-30281-8_7</a>","chicago":"Ashok, Pranav, Tomáš Brázdil, Krishnendu Chatterjee, Jan Křetínský, Christoph Lampert, and Viktor Toman. “Strategy Representation by Decision Trees with Linear Classifiers.” In <i>16th International Conference on Quantitative Evaluation of Systems</i>, 11785:109–28. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-30281-8_7\">https://doi.org/10.1007/978-3-030-30281-8_7</a>.","ista":"Ashok P, Brázdil T, Chatterjee K, Křetínský J, Lampert C, Toman V. 2019. Strategy representation by decision trees with linear classifiers. 16th International Conference on Quantitative Evaluation of Systems. QEST: Quantitative Evaluation of Systems, LNCS, vol. 11785, 109–128.","short":"P. Ashok, T. Brázdil, K. Chatterjee, J. Křetínský, C. Lampert, V. Toman, in:, 16th International Conference on Quantitative Evaluation of Systems, Springer Nature, 2019, pp. 109–128.","ama":"Ashok P, Brázdil T, Chatterjee K, Křetínský J, Lampert C, Toman V. Strategy representation by decision trees with linear classifiers. In: <i>16th International Conference on Quantitative Evaluation of Systems</i>. Vol 11785. Springer Nature; 2019:109-128. doi:<a href=\"https://doi.org/10.1007/978-3-030-30281-8_7\">10.1007/978-3-030-30281-8_7</a>","mla":"Ashok, Pranav, et al. “Strategy Representation by Decision Trees with Linear Classifiers.” <i>16th International Conference on Quantitative Evaluation of Systems</i>, vol. 11785, Springer Nature, 2019, pp. 109–28, doi:<a href=\"https://doi.org/10.1007/978-3-030-30281-8_7\">10.1007/978-3-030-30281-8_7</a>."},"quality_controlled":"1","scopus_import":"1","date_created":"2019-10-14T06:57:49Z","title":"Strategy representation by decision trees with linear classifiers","publication":"16th International Conference on Quantitative Evaluation of Systems","language":[{"iso":"eng"}],"year":"2019","type":"conference","date_published":"2019-09-04T00:00:00Z","alternative_title":["LNCS"],"arxiv":1,"page":"109-128","intvolume":"     11785","publication_identifier":{"eisbn":["9783030302818"],"issn":["0302-9743"],"isbn":["9783030302801"]},"department":[{"_id":"KrCh"},{"_id":"ChLa"}],"isi":1},{"isi":1,"department":[{"_id":"DaAl"}],"publication_identifier":{"issn":["0004-5411"]},"intvolume":"        66","article_number":"32","date_published":"2019-09-01T00:00:00Z","arxiv":1,"type":"journal_article","issue":"5","year":"2019","publication":"Journal of the ACM","corr_author":"1","title":"Self-stabilising Byzantine clock synchronisation is almost as easy as consensus","file":[{"date_updated":"2020-07-14T12:47:46Z","date_created":"2019-10-25T12:58:38Z","content_type":"application/pdf","relation":"main_file","file_size":2183085,"checksum":"7e5d95c478e0e393f4927fcf7e48194e","file_name":"2019_JACM_Lenzen.pdf","creator":"dernst","file_id":"6975","access_level":"open_access"}],"language":[{"iso":"eng"}],"scopus_import":"1","quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_created":"2019-10-24T17:12:48Z","status":"public","volume":66,"citation":{"apa":"Lenzen, C., &#38; Rybicki, J. (2019). Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3339471\">https://doi.org/10.1145/3339471</a>","ieee":"C. Lenzen and J. Rybicki, “Self-stabilising Byzantine clock synchronisation is almost as easy as consensus,” <i>Journal of the ACM</i>, vol. 66, no. 5. ACM, 2019.","chicago":"Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus.” <i>Journal of the ACM</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3339471\">https://doi.org/10.1145/3339471</a>.","short":"C. Lenzen, J. Rybicki, Journal of the ACM 66 (2019).","ista":"Lenzen C, Rybicki J. 2019. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. Journal of the ACM. 66(5), 32.","mla":"Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus.” <i>Journal of the ACM</i>, vol. 66, no. 5, 32, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3339471\">10.1145/3339471</a>.","ama":"Lenzen C, Rybicki J. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. <i>Journal of the ACM</i>. 2019;66(5). doi:<a href=\"https://doi.org/10.1145/3339471\">10.1145/3339471</a>"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa":1,"article_type":"original","file_date_updated":"2020-07-14T12:47:46Z","oa_version":"Published Version","month":"09","has_accepted_license":"1","date_updated":"2025-04-14T07:44:06Z","ddc":["000"],"ec_funded":1,"project":[{"grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"day":"01","publication_status":"published","_id":"6972","external_id":{"isi":["000496514100001"],"arxiv":["1705.06173"]},"publisher":"ACM","author":[{"last_name":"Lenzen","full_name":"Lenzen, Christoph","first_name":"Christoph"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki","first_name":"Joel","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646"}],"doi":"10.1145/3339471","article_processing_charge":"Yes","abstract":[{"lang":"eng","text":"We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of thennodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e.,the initial state of the system may be arbitrary, and there can be up to f<n/3 ongoing Byzantine faults, i.e.,nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks ofthe nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model,we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodesgenerate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner.Compared to prior work, we achieveexponentialimprovements in stabilisation time and the number ofcommunicated bits, and give the first sublinear-time algorithm for the problem:•In the deterministic setting, the state-of-the-art solutions stabilise in timeΘ(f)and have each nodebroadcastΘ(flogf)bits per time unit. We exponentially reduce the number of bits broadcasted pertime unit toΘ(logf)while retaining the same stabilisation time.•In the randomised setting, the state-of-the-art solutions stabilise in timeΘ(f)and have each nodebroadcastO(1)bits per time unit. We exponentially reduce the stabilisation time to polylogfwhileeach node broadcasts polylogfbits per time unit.These results are obtained by means of a recursive approach reducing the above task ofself-stabilisingpulse synchronisation in thebounded-delaymodel tonon-self-stabilisingbinary consensus in thesynchro-nousmodel. In general, our approach introduces at most logarithmic overheads in terms of stabilisation timeand broadcasted bits over the underlying consensus routine."}]},{"doi":"10.1007/978-3-030-23459-1_6","article_processing_charge":"No","abstract":[{"lang":"eng","text":"Cells are arranged into species-specific patterns during early embryogenesis. Such cell division patterns are important since they often reflect the distribution of localized cortical factors from eggs/fertilized eggs to specific cells as well as the emergence of organismal form. However, it has proven difficult to reveal the mechanisms that underlie the emergence of cell positioning patterns that underlie embryonic shape, likely because a systems-level approach is required that integrates cell biological, genetic, developmental, and mechanical parameters. The choice of organism to address such questions is also important. Because ascidians display the most extreme form of invariant cleavage pattern among the metazoans, we have been analyzing the cell biological mechanisms that underpin three aspects of cell division (unequal cell division (UCD), oriented cell division (OCD), and asynchronous cell cycles) which affect the overall shape of the blastula-stage ascidian embryo composed of 64 cells. In ascidians, UCD creates two small cells at the 16-cell stage that in turn undergo two further successive rounds of UCD. Starting at the 16-cell stage, the cell cycle becomes asynchronous, whereby the vegetal half divides before the animal half, thus creating 24-, 32-, 44-, and then 64-cell stages. Perturbing either UCD or the alternate cell division rhythm perturbs cell position. We propose that dynamic cell shape changes propagate throughout the embryo via cell-cell contacts to create the ascidian-specific invariant cleavage pattern."}],"publication_status":"published","_id":"6987","external_id":{"pmid":["31598855"]},"publisher":"Springer Nature","author":[{"last_name":"McDougall","first_name":"Alex","full_name":"McDougall, Alex"},{"last_name":"Chenevert","full_name":"Chenevert, Janet","first_name":"Janet"},{"last_name":"Godard","id":"33280250-F248-11E8-B48F-1D18A9856A87","full_name":"Godard, Benoit G","first_name":"Benoit G"},{"last_name":"Dumollard","first_name":"Remi","full_name":"Dumollard, Remi"}],"day":"10","ddc":["570"],"has_accepted_license":"1","date_updated":"2026-04-16T10:26:18Z","month":"10","oa_version":"Submitted Version","file_date_updated":"2020-07-14T12:47:46Z","editor":[{"full_name":"Tworzydlo, Waclaw","first_name":"Waclaw","last_name":"Tworzydlo"},{"last_name":"Bilinski","first_name":"Szczepan M.","full_name":"Bilinski, Szczepan M."}],"oa":1,"citation":{"mla":"McDougall, Alex, et al. “Emergence of Embryo Shape during Cleavage Divisions.” <i>Evo-Devo: Non-Model Species in Cell and Developmental Biology</i>, edited by Waclaw Tworzydlo and Szczepan M. Bilinski, vol. 68, Springer Nature, 2019, pp. 127–54, doi:<a href=\"https://doi.org/10.1007/978-3-030-23459-1_6\">10.1007/978-3-030-23459-1_6</a>.","ama":"McDougall A, Chenevert J, Godard BG, Dumollard R. Emergence of embryo shape during cleavage divisions. In: Tworzydlo W, Bilinski SM, eds. <i>Evo-Devo: Non-Model Species in Cell and Developmental Biology</i>. Vol 68. Springer Nature; 2019:127-154. doi:<a href=\"https://doi.org/10.1007/978-3-030-23459-1_6\">10.1007/978-3-030-23459-1_6</a>","ista":"McDougall A, Chenevert J, Godard BG, Dumollard R. 2019.Emergence of embryo shape during cleavage divisions. In: Evo-Devo: Non-model species in cell and developmental biology. RESULTS, vol. 68, 127–154.","short":"A. McDougall, J. Chenevert, B.G. Godard, R. Dumollard, in:, W. Tworzydlo, S.M. Bilinski (Eds.), Evo-Devo: Non-Model Species in Cell and Developmental Biology, Springer Nature, 2019, pp. 127–154.","chicago":"McDougall, Alex, Janet Chenevert, Benoit G Godard, and Remi Dumollard. “Emergence of Embryo Shape during Cleavage Divisions.” In <i>Evo-Devo: Non-Model Species in Cell and Developmental Biology</i>, edited by Waclaw Tworzydlo and Szczepan M. Bilinski, 68:127–54. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-23459-1_6\">https://doi.org/10.1007/978-3-030-23459-1_6</a>.","apa":"McDougall, A., Chenevert, J., Godard, B. G., &#38; Dumollard, R. (2019). Emergence of embryo shape during cleavage divisions. In W. Tworzydlo &#38; S. M. Bilinski (Eds.), <i>Evo-Devo: Non-model species in cell and developmental biology</i> (Vol. 68, pp. 127–154). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-23459-1_6\">https://doi.org/10.1007/978-3-030-23459-1_6</a>","ieee":"A. McDougall, J. Chenevert, B. G. Godard, and R. Dumollard, “Emergence of embryo shape during cleavage divisions,” in <i>Evo-Devo: Non-model species in cell and developmental biology</i>, vol. 68, W. Tworzydlo and S. M. Bilinski, Eds. Springer Nature, 2019, pp. 127–154."},"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","status":"public","volume":68,"date_created":"2019-11-04T16:20:19Z","scopus_import":"1","quality_controlled":"1","file":[{"content_type":"application/pdf","date_created":"2020-05-14T10:09:30Z","date_updated":"2020-07-14T12:47:46Z","file_name":"2019_RESULTS_McDougall.pdf","checksum":"7f43e1e3706d15061475c5c57efc2786","relation":"main_file","file_size":19317348,"creator":"dernst","file_id":"7829","access_level":"open_access"}],"language":[{"iso":"eng"}],"publication":"Evo-Devo: Non-model species in cell and developmental biology","title":"Emergence of embryo shape during cleavage divisions","year":"2019","type":"book_chapter","pmid":1,"page":"127-154","alternative_title":["RESULTS"],"date_published":"2019-10-10T00:00:00Z","intvolume":"        68","department":[{"_id":"CaHe"}],"publication_identifier":{"eisbn":["9783030234591"],"eissn":["1861-0412"],"issn":["0080-1844"],"isbn":["9783030234584"]}},{"ddc":["580"],"_id":"6999","external_id":{"isi":["000490183000068"],"pmid":["31575745"]},"publication_status":"published","author":[{"last_name":"Huang","first_name":"D","full_name":"Huang, D"},{"last_name":"Sun","full_name":"Sun, Y","first_name":"Y"},{"last_name":"Ma","first_name":"Z","full_name":"Ma, Z"},{"last_name":"Ke","first_name":"M","full_name":"Ke, M"},{"first_name":"Y","full_name":"Cui, Y","last_name":"Cui"},{"last_name":"Chen","first_name":"Z","full_name":"Chen, Z"},{"full_name":"Chen, C","first_name":"C","last_name":"Chen"},{"full_name":"Ji, C","first_name":"C","last_name":"Ji"},{"last_name":"Tran","first_name":"TM","full_name":"Tran, TM"},{"first_name":"L","full_name":"Yang, L","last_name":"Yang"},{"full_name":"Lam, SM","first_name":"SM","last_name":"Lam"},{"first_name":"Y","full_name":"Han, Y","last_name":"Han"},{"last_name":"Shu","first_name":"G","full_name":"Shu, G"},{"id":"4159519E-F248-11E8-B48F-1D18A9856A87","last_name":"Friml","full_name":"Friml, Jiří","orcid":"0000-0002-8302-7596","first_name":"Jiří"},{"full_name":"Miao, Y","first_name":"Y","last_name":"Miao"},{"last_name":"Jiang","full_name":"Jiang, L","first_name":"L"},{"full_name":"Chen, X","first_name":"X","last_name":"Chen"}],"publisher":"National Academy of Sciences","day":"15","doi":"10.1073/pnas.1911892116","article_processing_charge":"No","abstract":[{"text":"Plasmodesmata (PD) are plant-specific membrane-lined channels that create cytoplasmic and membrane continuities between adjacent cells, thereby facilitating cell–cell communication and virus movement. Plant cells have evolved diverse mechanisms to regulate PD plasticity in response to numerous environmental stimuli. In particular, during defense against plant pathogens, the defense hormone, salicylic acid (SA), plays a crucial role in the regulation of PD permeability in a callose-dependent manner. Here, we uncover a mechanism by which plants restrict the spreading of virus and PD cargoes using SA signaling by increasing lipid order and closure of PD. We showed that exogenous SA application triggered the compartmentalization of lipid raft nanodomains through a modulation of the lipid raft-regulatory protein, Remorin (REM). Genetic studies, superresolution imaging, and transmission electron microscopy observation together demonstrated that Arabidopsis REM1.2 and REM1.3 are crucial for plasma membrane nanodomain assembly to control PD aperture and functionality. In addition, we also found that a 14-3-3 epsilon protein modulates REM clustering and membrane nanodomain compartmentalization through its direct interaction with REM proteins. This study unveils a molecular mechanism by which the key plant defense hormone, SA, triggers membrane lipid nanodomain reorganization, thereby regulating PD closure to impede virus spreading.","lang":"eng"}],"article_type":"original","oa":1,"file_date_updated":"2020-07-14T12:47:46Z","oa_version":"Published Version","has_accepted_license":"1","date_updated":"2025-05-14T10:56:34Z","month":"10","year":"2019","issue":"42","type":"journal_article","pmid":1,"file":[{"content_type":"application/pdf","date_created":"2019-11-13T08:22:28Z","date_updated":"2020-07-14T12:47:46Z","file_name":"2019_PNAS_Huang.pdf","checksum":"258c666bc6253eab81961f61169eefae","relation":"main_file","file_size":3287466,"creator":"dernst","file_id":"7012","access_level":"open_access"}],"language":[{"iso":"eng"}],"publication":"Proceedings of the National Academy of Sciences of the United States of America","title":"Salicylic acid-mediated plasmodesmal closure via Remorin-dependent lipid organization","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)"},"date_created":"2019-11-12T11:42:05Z","scopus_import":"1","quality_controlled":"1","related_material":{"link":[{"url":"https://doi.org/10.1073/pnas.2004738117","relation":"erratum"}]},"citation":{"chicago":"Huang, D, Y Sun, Z Ma, M Ke, Y Cui, Z Chen, C Chen, et al. “Salicylic Acid-Mediated Plasmodesmal Closure via Remorin-Dependent Lipid Organization.” <i>Proceedings of the National Academy of Sciences of the United States of America</i>. National Academy of Sciences, 2019. <a href=\"https://doi.org/10.1073/pnas.1911892116\">https://doi.org/10.1073/pnas.1911892116</a>.","apa":"Huang, D., Sun, Y., Ma, Z., Ke, M., Cui, Y., Chen, Z., … Chen, X. (2019). Salicylic acid-mediated plasmodesmal closure via Remorin-dependent lipid organization. <i>Proceedings of the National Academy of Sciences of the United States of America</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.1911892116\">https://doi.org/10.1073/pnas.1911892116</a>","ieee":"D. Huang <i>et al.</i>, “Salicylic acid-mediated plasmodesmal closure via Remorin-dependent lipid organization,” <i>Proceedings of the National Academy of Sciences of the United States of America</i>, vol. 116, no. 42. National Academy of Sciences, pp. 21274–21284, 2019.","mla":"Huang, D., et al. “Salicylic Acid-Mediated Plasmodesmal Closure via Remorin-Dependent Lipid Organization.” <i>Proceedings of the National Academy of Sciences of the United States of America</i>, vol. 116, no. 42, National Academy of Sciences, 2019, pp. 21274–84, doi:<a href=\"https://doi.org/10.1073/pnas.1911892116\">10.1073/pnas.1911892116</a>.","ama":"Huang D, Sun Y, Ma Z, et al. Salicylic acid-mediated plasmodesmal closure via Remorin-dependent lipid organization. <i>Proceedings of the National Academy of Sciences of the United States of America</i>. 2019;116(42):21274-21284. doi:<a href=\"https://doi.org/10.1073/pnas.1911892116\">10.1073/pnas.1911892116</a>","short":"D. Huang, Y. Sun, Z. Ma, M. Ke, Y. Cui, Z. Chen, C. Chen, C. Ji, T. Tran, L. Yang, S. Lam, Y. Han, G. Shu, J. Friml, Y. Miao, L. Jiang, X. Chen, Proceedings of the National Academy of Sciences of the United States of America 116 (2019) 21274–21284.","ista":"Huang D, Sun Y, Ma Z, Ke M, Cui Y, Chen Z, Chen C, Ji C, Tran T, Yang L, Lam S, Han Y, Shu G, Friml J, Miao Y, Jiang L, Chen X. 2019. Salicylic acid-mediated plasmodesmal closure via Remorin-dependent lipid organization. Proceedings of the National Academy of Sciences of the United States of America. 116(42), 21274–21284."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","volume":116,"license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","isi":1,"publication_identifier":{"eissn":["1091-6490"],"issn":["0027-8424"]},"department":[{"_id":"JiFr"}],"intvolume":"       116","page":"21274-21284","date_published":"2019-10-15T00:00:00Z"},{"citation":{"chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds.” <i>Journal of Computational Geometry</i>. Computational Geometry Laborartoy, 2019. <a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">https://doi.org/10.20382/JOGC.V10I2A5</a>.","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” <i>Journal of Computational Geometry</i>, vol. 10, no. 2. Computational Geometry Laborartoy, pp. 70–98, 2019.","apa":"Huszár, K., Spreer, J., &#38; Wagner, U. (2019). On the treewidth of triangulated 3-manifolds. <i>Journal of Computational Geometry</i>. Computational Geometry Laborartoy. <a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">https://doi.org/10.20382/JOGC.V10I2A5</a>","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. <i>Journal of Computational Geometry</i>. 2019;10(2):70–98. doi:<a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">10.20382/JOGC.V10I2A5</a>","mla":"Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” <i>Journal of Computational Geometry</i>, vol. 10, no. 2, Computational Geometry Laborartoy, 2019, pp. 70–98, doi:<a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">10.20382/JOGC.V10I2A5</a>.","short":"K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019) 70–98.","ista":"Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","volume":10,"status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_created":"2019-11-23T12:14:09Z","related_material":{"record":[{"relation":"earlier_version","id":"285","status":"public"},{"id":"8032","status":"public","relation":"part_of_dissertation"}]},"quality_controlled":"1","scopus_import":"1","language":[{"iso":"eng"}],"file":[{"access_level":"open_access","file_id":"7094","creator":"khuszar","checksum":"c872d590d38d538404782bca20c4c3f5","file_name":"479-1917-1-PB.pdf","relation":"main_file","file_size":857590,"content_type":"application/pdf","date_updated":"2020-07-14T12:47:49Z","date_created":"2019-11-23T12:35:16Z"}],"title":"On the treewidth of triangulated 3-manifolds","publication":"Journal of Computational Geometry","type":"journal_article","year":"2019","issue":"2","arxiv":1,"page":"70–98","date_published":"2019-11-01T00:00:00Z","intvolume":"        10","department":[{"_id":"UlWa"}],"publication_identifier":{"issn":["1920-180X"]},"article_processing_charge":"No","abstract":[{"lang":"eng","text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how \"simple\" or \"thin\" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth.\r\nIn view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs).\r\nWe derive these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 18(k+1) (resp. 4(3k+1))."}],"doi":"10.20382/JOGC.V10I2A5","publisher":"Computational Geometry Laborartoy","_id":"7093","external_id":{"arxiv":["1712.00434"]},"publication_status":"published","author":[{"id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár","full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","first_name":"Kristóf"},{"first_name":"Jonathan","full_name":"Spreer, Jonathan","last_name":"Spreer"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"day":"01","ddc":["514"],"date_updated":"2026-04-08T07:21:27Z","has_accepted_license":"1","month":"11","oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:49Z","oa":1,"article_type":"original"},{"main_file_link":[{"url":"https://arxiv.org/abs/1711.08436","open_access":"1"}],"month":"06","date_updated":"2025-06-04T07:49:03Z","oa_version":"Preprint","oa":1,"article_type":"original","doi":"10.1145/3314024","article_processing_charge":"No","abstract":[{"lang":"eng","text":"We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable."}],"day":"01","external_id":{"isi":["000495406300007"],"arxiv":["1711.08436"]},"_id":"7108","publisher":"ACM","author":[{"full_name":"Goaoc, Xavier","first_name":"Xavier","last_name":"Goaoc"},{"id":"B593B804-1035-11EA-B4F1-947645A5BB83","last_name":"Patak","first_name":"Pavel","full_name":"Patak, Pavel"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","last_name":"Patakova","full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","first_name":"Zuzana"},{"full_name":"Tancer, Martin","first_name":"Martin","last_name":"Tancer"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"publication_status":"published","date_published":"2019-06-01T00:00:00Z","article_number":"21","arxiv":1,"intvolume":"        66","isi":1,"department":[{"_id":"UlWa"}],"publication_identifier":{"issn":["0004-5411"]},"status":"public","volume":66,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” <i>Journal of the ACM</i>, vol. 66, no. 3. ACM, 2019.","apa":"Goaoc, X., Patak, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2019). Shellability is NP-complete. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3314024\">https://doi.org/10.1145/3314024</a>","chicago":"Goaoc, Xavier, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete.” <i>Journal of the ACM</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3314024\">https://doi.org/10.1145/3314024</a>.","short":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner, Journal of the ACM 66 (2019).","ista":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. 2019. Shellability is NP-complete. Journal of the ACM. 66(3), 21.","ama":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. <i>Journal of the ACM</i>. 2019;66(3). doi:<a href=\"https://doi.org/10.1145/3314024\">10.1145/3314024</a>","mla":"Goaoc, Xavier, et al. “Shellability Is NP-Complete.” <i>Journal of the ACM</i>, vol. 66, no. 3, 21, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3314024\">10.1145/3314024</a>."},"quality_controlled":"1","scopus_import":"1","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"184"}]},"date_created":"2019-11-26T10:13:59Z","publication":"Journal of the ACM","title":"Shellability is NP-complete","language":[{"iso":"eng"}],"year":"2019","type":"journal_article","issue":"3"},{"isi":1,"department":[{"_id":"CaGu"},{"_id":"ToHe"}],"publication_identifier":{"eissn":["1611-3349"],"eisbn":["9783030313043"],"isbn":["9783030313036"],"issn":["0302-9743"]},"page":"155-187","alternative_title":["LNCS"],"date_published":"2019-09-17T00:00:00Z","intvolume":"     11773","language":[{"iso":"eng"}],"publication":"17th International Conference on Computational Methods in Systems Biology","title":"Transient memory in gene regulation","type":"conference","year":"2019","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","citation":{"ieee":"C. C. Guet, T. A. Henzinger, C. Igler, T. Petrov, and A. Sezgin, “Transient memory in gene regulation,” in <i>17th International Conference on Computational Methods in Systems Biology</i>, Trieste, Italy, 2019, vol. 11773, pp. 155–187.","apa":"Guet, C. C., Henzinger, T. A., Igler, C., Petrov, T., &#38; Sezgin, A. (2019). Transient memory in gene regulation. In <i>17th International Conference on Computational Methods in Systems Biology</i> (Vol. 11773, pp. 155–187). Trieste, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-31304-3_9\">https://doi.org/10.1007/978-3-030-31304-3_9</a>","chicago":"Guet, Calin C, Thomas A Henzinger, Claudia Igler, Tatjana Petrov, and Ali Sezgin. “Transient Memory in Gene Regulation.” In <i>17th International Conference on Computational Methods in Systems Biology</i>, 11773:155–87. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-31304-3_9\">https://doi.org/10.1007/978-3-030-31304-3_9</a>.","ista":"Guet CC, Henzinger TA, Igler C, Petrov T, Sezgin A. 2019. Transient memory in gene regulation. 17th International Conference on Computational Methods in Systems Biology. CMSB: Computational Methods in Systems Biology, LNCS, vol. 11773, 155–187.","short":"C.C. Guet, T.A. Henzinger, C. Igler, T. Petrov, A. Sezgin, in:, 17th International Conference on Computational Methods in Systems Biology, Springer Nature, 2019, pp. 155–187.","ama":"Guet CC, Henzinger TA, Igler C, Petrov T, Sezgin A. Transient memory in gene regulation. In: <i>17th International Conference on Computational Methods in Systems Biology</i>. Vol 11773. Springer Nature; 2019:155-187. doi:<a href=\"https://doi.org/10.1007/978-3-030-31304-3_9\">10.1007/978-3-030-31304-3_9</a>","mla":"Guet, Calin C., et al. “Transient Memory in Gene Regulation.” <i>17th International Conference on Computational Methods in Systems Biology</i>, vol. 11773, Springer Nature, 2019, pp. 155–87, doi:<a href=\"https://doi.org/10.1007/978-3-030-31304-3_9\">10.1007/978-3-030-31304-3_9</a>."},"status":"public","volume":11773,"date_created":"2019-12-04T16:07:50Z","scopus_import":"1","quality_controlled":"1","oa_version":"None","date_updated":"2026-04-16T10:26:49Z","month":"09","doi":"10.1007/978-3-030-31304-3_9","abstract":[{"text":"The expression of a gene is characterised by its transcription factors and the function processing them. If the transcription factors are not affected by gene products, the regulating function is often represented as a combinational logic circuit, where the outputs (product) are determined by current input values (transcription factors) only, and are hence independent on their relative arrival times. However, the simultaneous arrival of transcription factors (TFs) in genetic circuits is a strong assumption, given that the processes of transcription and translation of a gene into a protein introduce intrinsic time delays and that there is no global synchronisation among the arrival times of different molecular species at molecular targets.\r\n\r\nIn this paper, we construct an experimentally implementable genetic circuit with two inputs and a single output, such that, in presence of small delays in input arrival, the circuit exhibits qualitatively distinct observable phenotypes. In particular, these phenotypes are long lived transients: they all converge to a single value, but so slowly, that they seem stable for an extended time period, longer than typical experiment duration. We used rule-based language to prototype our circuit, and we implemented a search for finding the parameter combinations raising the phenotypes of interest.\r\n\r\nThe behaviour of our prototype circuit has wide implications. First, it suggests that GRNs can exploit event timing to create phenotypes. Second, it opens the possibility that GRNs are using event timing to react to stimuli and memorise events, without explicit feedback in regulation. From the modelling perspective, our prototype circuit demonstrates the critical importance of analysing the transient dynamics at the promoter binding sites of the DNA, before applying rapid equilibrium assumptions.","lang":"eng"}],"article_processing_charge":"No","external_id":{"isi":["000557875100009"]},"_id":"7147","publication_status":"published","author":[{"last_name":"Guet","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6220-2052","full_name":"Guet, Calin C","first_name":"Calin C"},{"last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"full_name":"Igler, Claudia","orcid":"0000-0001-7777-546X","first_name":"Claudia","id":"46613666-F248-11E8-B48F-1D18A9856A87","last_name":"Igler"},{"first_name":"Tatjana","orcid":"0000-0002-9041-0905","full_name":"Petrov, Tatjana","last_name":"Petrov","id":"3D5811FC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Ali","full_name":"Sezgin, Ali","id":"4C7638DA-F248-11E8-B48F-1D18A9856A87","last_name":"Sezgin"}],"publisher":"Springer Nature","project":[{"call_identifier":"FWF","grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425"},{"_id":"251EE76E-B435-11E9-9278-68D0E5697425","name":"Design principles underlying genetic switch architecture","grant_number":"24573"}],"conference":{"start_date":"2019-09-18","location":"Trieste, Italy","name":"CMSB: Computational Methods in Systems Biology","end_date":"2019-09-20"},"day":"17"},{"status":"public","volume":32,"citation":{"chicago":"Censor-Hillel, Keren, Petteri Kaski, Janne Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. “Algebraic Methods in the Congested Clique.” <i>Distributed Computing</i>. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/s00446-016-0270-2\">https://doi.org/10.1007/s00446-016-0270-2</a>.","apa":"Censor-Hillel, K., Kaski, P., Korhonen, J., Lenzen, C., Paz, A., &#38; Suomela, J. (2019). Algebraic methods in the congested clique. <i>Distributed Computing</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00446-016-0270-2\">https://doi.org/10.1007/s00446-016-0270-2</a>","ieee":"K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, and J. Suomela, “Algebraic methods in the congested clique,” <i>Distributed Computing</i>, vol. 32, no. 6. Springer Nature, pp. 461–478, 2019.","mla":"Censor-Hillel, Keren, et al. “Algebraic Methods in the Congested Clique.” <i>Distributed Computing</i>, vol. 32, no. 6, Springer Nature, 2019, pp. 461–78, doi:<a href=\"https://doi.org/10.1007/s00446-016-0270-2\">10.1007/s00446-016-0270-2</a>.","ama":"Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. Algebraic methods in the congested clique. <i>Distributed Computing</i>. 2019;32(6):461-478. doi:<a href=\"https://doi.org/10.1007/s00446-016-0270-2\">10.1007/s00446-016-0270-2</a>","short":"K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, J. Suomela, Distributed Computing 32 (2019) 461–478.","ista":"Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. 2019. Algebraic methods in the congested clique. Distributed Computing. 32(6), 461–478."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","date_created":"2019-12-05T09:49:49Z","publication":"Distributed Computing","title":"Algebraic methods in the congested clique","language":[{"iso":"eng"}],"year":"2019","type":"journal_article","issue":"6","date_published":"2019-12-01T00:00:00Z","arxiv":1,"page":"461-478","intvolume":"        32","publication_identifier":{"issn":["0178-2770","1432-0452"]},"doi":"10.1007/s00446-016-0270-2","article_processing_charge":"No","abstract":[{"text":"In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an O(n1−2/ω) round matrix multiplication algorithm, where ω<2.3728639 is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include:\r\n\r\n1.    triangle and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) algorithm of Dolev et al. [DISC 2012],\r\n2. a (1+o(1))-approximation of all-pairs shortest paths in O(n0.158) rounds, improving upon the O~(n1/2)-round (2+o(1))-approximation algorithm given by Nanongkai [STOC 2014], and\r\n 3. computing the girth in O(n0.158) rounds, which is the first non-trivial solution in this model.\r\n   \r\nIn addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles.","lang":"eng"}],"day":"01","author":[{"first_name":"Keren","full_name":"Censor-Hillel, Keren","last_name":"Censor-Hillel"},{"first_name":"Petteri","full_name":"Kaski, Petteri","last_name":"Kaski"},{"last_name":"Korhonen","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne","full_name":"Korhonen, Janne"},{"full_name":"Lenzen, Christoph","first_name":"Christoph","last_name":"Lenzen"},{"last_name":"Paz","full_name":"Paz, Ami","first_name":"Ami"},{"last_name":"Suomela","first_name":"Jukka","full_name":"Suomela, Jukka"}],"_id":"7150","publisher":"Springer Nature","publication_status":"published","external_id":{"arxiv":["1503.04963"]},"extern":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1503.04963"}],"month":"12","date_updated":"2021-01-12T08:12:05Z","oa_version":"Preprint","oa":1,"article_type":"original"},{"publication_identifier":{"eisbn":["9783030320799"],"isbn":["9783030320782"],"issn":["0302-9743"]},"department":[{"_id":"ToHe"}],"isi":1,"page":"292-309","date_published":"2019-10-01T00:00:00Z","alternative_title":["LNCS"],"intvolume":"     11757","language":[{"iso":"eng"}],"title":"Shape expressions for specifying and extracting signal features","publication":"19th International Conference on Runtime Verification","year":"2019","type":"conference","citation":{"chicago":"Ničković, Dejan, Xin Qin, Thomas Ferrere, Cristinel Mateis, and Jyotirmoy Deshmukh. “Shape Expressions for Specifying and Extracting Signal Features.” In <i>19th International Conference on Runtime Verification</i>, 11757:292–309. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-32079-9_17\">https://doi.org/10.1007/978-3-030-32079-9_17</a>.","ieee":"D. Ničković, X. Qin, T. Ferrere, C. Mateis, and J. Deshmukh, “Shape expressions for specifying and extracting signal features,” in <i>19th International Conference on Runtime Verification</i>, Porto, Portugal, 2019, vol. 11757, pp. 292–309.","apa":"Ničković, D., Qin, X., Ferrere, T., Mateis, C., &#38; Deshmukh, J. (2019). Shape expressions for specifying and extracting signal features. In <i>19th International Conference on Runtime Verification</i> (Vol. 11757, pp. 292–309). Porto, Portugal: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-32079-9_17\">https://doi.org/10.1007/978-3-030-32079-9_17</a>","ama":"Ničković D, Qin X, Ferrere T, Mateis C, Deshmukh J. Shape expressions for specifying and extracting signal features. In: <i>19th International Conference on Runtime Verification</i>. Vol 11757. Springer Nature; 2019:292-309. doi:<a href=\"https://doi.org/10.1007/978-3-030-32079-9_17\">10.1007/978-3-030-32079-9_17</a>","mla":"Ničković, Dejan, et al. “Shape Expressions for Specifying and Extracting Signal Features.” <i>19th International Conference on Runtime Verification</i>, vol. 11757, Springer Nature, 2019, pp. 292–309, doi:<a href=\"https://doi.org/10.1007/978-3-030-32079-9_17\">10.1007/978-3-030-32079-9_17</a>.","ista":"Ničković D, Qin X, Ferrere T, Mateis C, Deshmukh J. 2019. Shape expressions for specifying and extracting signal features. 19th International Conference on Runtime Verification. RV: Runtime Verification, LNCS, vol. 11757, 292–309.","short":"D. Ničković, X. Qin, T. Ferrere, C. Mateis, J. Deshmukh, in:, 19th International Conference on Runtime Verification, Springer Nature, 2019, pp. 292–309."},"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","volume":11757,"status":"public","date_created":"2019-12-09T08:47:55Z","quality_controlled":"1","scopus_import":"1","oa_version":"None","date_updated":"2026-04-16T10:27:14Z","month":"10","article_processing_charge":"No","abstract":[{"lang":"eng","text":"Cyber-physical systems (CPS) and the Internet-of-Things (IoT) result in a tremendous amount of generated, measured and recorded time-series data. Extracting temporal segments that encode patterns with useful information out of these huge amounts of data is an extremely difficult problem. We propose shape expressions as a declarative formalism for specifying, querying and extracting sophisticated temporal patterns from possibly noisy data. Shape expressions are regular expressions with arbitrary (linear, exponential, sinusoidal, etc.) shapes with parameters as atomic predicates and additional constraints on these parameters. We equip shape expressions with a novel noisy semantics that combines regular expression matching semantics with statistical regression. We characterize essential properties of the formalism and propose an efficient approximate shape expression matching procedure. We demonstrate the wide applicability of this technique on two case studies. "}],"doi":"10.1007/978-3-030-32079-9_17","author":[{"full_name":"Ničković, Dejan","first_name":"Dejan","last_name":"Ničković"},{"first_name":"Xin","full_name":"Qin, Xin","last_name":"Qin"},{"last_name":"Ferrere","id":"40960E6E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5199-3143","full_name":"Ferrere, Thomas","first_name":"Thomas"},{"full_name":"Mateis, Cristinel","first_name":"Cristinel","last_name":"Mateis"},{"full_name":"Deshmukh, Jyotirmoy","first_name":"Jyotirmoy","last_name":"Deshmukh"}],"_id":"7159","external_id":{"isi":["000570006300017"]},"publication_status":"published","publisher":"Springer Nature","day":"01","conference":{"end_date":"2019-10-11","name":"RV: Runtime Verification","start_date":"2019-10-08","location":"Porto, Portugal"},"project":[{"call_identifier":"FWF","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"Formal methods for the design and analysis of complex systems"},{"call_identifier":"FWF","grant_number":"S11402-N23","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering"}]},{"editor":[{"full_name":"Kersting, Kristian","first_name":"Kristian","last_name":"Kersting"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","first_name":"Christoph","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887"},{"last_name":"Rothkopf","full_name":"Rothkopf, Constantin","first_name":"Constantin"}],"oa_version":"None","department":[{"_id":"ChLa"}],"publication_identifier":{"eisbn":["978-3-658-26763-6"],"isbn":["978-3-658-26762-9"]},"date_published":"2019-10-30T00:00:00Z","page":"XIV, 245","month":"10","date_updated":"2021-12-22T14:40:58Z","edition":"1","title":"Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt","language":[{"iso":"ger"}],"year":"2019","type":"book_editor","doi":"10.1007/978-3-658-26763-6","status":"public","article_processing_charge":"No","abstract":[{"lang":"ger","text":"Wissen Sie, was sich hinter künstlicher Intelligenz und maschinellem Lernen verbirgt? \r\nDieses Sachbuch erklärt Ihnen leicht verständlich und ohne komplizierte Formeln die grundlegenden Methoden und Vorgehensweisen des maschinellen Lernens. Mathematisches Vorwissen ist dafür nicht nötig. Kurzweilig und informativ illustriert Lisa, die Protagonistin des Buches, diese anhand von Alltagssituationen. \r\nEin Buch für alle, die in Diskussionen über Chancen und Risiken der aktuellen Entwicklung der künstlichen Intelligenz und des maschinellen Lernens mit Faktenwissen punkten möchten. Auch für Schülerinnen und Schüler geeignet!"}],"place":"Wiesbaden","citation":{"apa":"Kersting, K., Lampert, C., &#38; Rothkopf, C. (Eds.). (2019). <i>Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt</i> (1st ed.). Wiesbaden: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-658-26763-6\">https://doi.org/10.1007/978-3-658-26763-6</a>","ieee":"K. Kersting, C. Lampert, and C. Rothkopf, Eds., <i>Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt</i>, 1st ed. Wiesbaden: Springer Nature, 2019.","chicago":"Kersting, Kristian, Christoph Lampert, and Constantin Rothkopf, eds. <i>Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt</i>. 1st ed. Wiesbaden: Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-658-26763-6\">https://doi.org/10.1007/978-3-658-26763-6</a>.","short":"K. Kersting, C. Lampert, C. Rothkopf, eds., Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt, 1st ed., Springer Nature, Wiesbaden, 2019.","ista":"Kersting K, Lampert C, Rothkopf C eds. 2019. Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt 1st ed., Wiesbaden: Springer Nature, XIV, 245p.","mla":"Kersting, Kristian, et al., editors. <i>Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt</i>. 1st ed., Springer Nature, 2019, doi:<a href=\"https://doi.org/10.1007/978-3-658-26763-6\">10.1007/978-3-658-26763-6</a>.","ama":"Kersting K, Lampert C, Rothkopf C, eds. <i>Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt</i>. 1st ed. Wiesbaden: Springer Nature; 2019. doi:<a href=\"https://doi.org/10.1007/978-3-658-26763-6\">10.1007/978-3-658-26763-6</a>"},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","quality_controlled":"1","day":"30","related_material":{"link":[{"url":"https://ist.ac.at/en/news/book-release-how-machines-learn/","relation":"press_release","description":"News on IST Website"}]},"_id":"7171","publication_status":"published","publisher":"Springer Nature","date_created":"2019-12-11T14:15:56Z"},{"oa":1,"article_type":"original","oa_version":"Submitted Version","file_date_updated":"2020-12-06T17:30:09Z","month":"12","has_accepted_license":"1","date_updated":"2026-04-03T09:44:03Z","ddc":["571","599"],"day":"01","_id":"7179","publication_status":"published","author":[{"full_name":"Klotz, Lisa","first_name":"Lisa","last_name":"Klotz"},{"last_name":"Wendler","first_name":"Olaf","full_name":"Wendler, Olaf"},{"last_name":"Frischknecht","full_name":"Frischknecht, Renato","first_name":"Renato"},{"first_name":"Ryuichi","orcid":"0000-0001-8761-9444","full_name":"Shigemoto, Ryuichi","last_name":"Shigemoto","id":"499F3ABC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Schulze, Holger","first_name":"Holger","last_name":"Schulze"},{"last_name":"Enz","full_name":"Enz, Ralf","first_name":"Ralf"}],"external_id":{"isi":["000507466100054"],"pmid":["31585509"]},"publisher":"FASEB","doi":"10.1096/fj.201901543R","abstract":[{"text":"Glutamate is the major excitatory neurotransmitter in the CNS binding to a variety of glutamate receptors. Metabotropic glutamate receptors (mGluR1 to mGluR8) can act excitatory or inhibitory, depending on associated signal cascades. Expression and localization of inhibitory acting mGluRs at inner hair cells (IHCs) in the cochlea are largely unknown. Here, we analyzed expression of mGluR2, mGluR3, mGluR4, mGluR6, mGluR7, and mGluR8 and investigated their localization with respect to the presynaptic ribbon of IHC synapses. We detected transcripts for mGluR2, mGluR3, and mGluR4 as well as for mGluR7a, mGluR7b, mGluR8a, and mGluR8b splice variants. Using receptor-specific antibodies in cochlear wholemounts, we found expression of mGluR2, mGluR4, and mGluR8b close to presynaptic ribbons. Super resolution and confocal microscopy in combination with 3-dimensional reconstructions indicated a postsynaptic localization of mGluR2 that overlaps with postsynaptic density protein 95 on dendrites of afferent type I spiral ganglion neurons. In contrast, mGluR4 and mGluR8b were expressed at the presynapse close to IHC ribbons. In summary, we localized in detail 3 mGluR types at IHC ribbon synapses, providing a fundament for new therapeutical strategies that could protect the cochlea against noxious stimuli and excitotoxicity.","lang":"eng"}],"article_processing_charge":"No","isi":1,"department":[{"_id":"RySh"}],"publication_identifier":{"eissn":["1530-6860"]},"intvolume":"        33","date_published":"2019-12-01T00:00:00Z","page":"13734-13746","pmid":1,"year":"2019","issue":"12","type":"journal_article","publication":"FASEB Journal","title":"Localization of group II and III metabotropic glutamate receptors at pre- and postsynaptic sites of inner hair cell ribbon synapses","file":[{"success":1,"file_id":"8922","access_level":"open_access","creator":"shigemot","checksum":"79e3b72481dc32489911121cf3b7d8d0","file_name":"Klotz et al 2019 EMBO Reports.pdf","file_size":4766789,"relation":"main_file","content_type":"application/pdf","date_updated":"2020-12-06T17:30:09Z","date_created":"2020-12-06T17:30:09Z"}],"language":[{"iso":"eng"}],"scopus_import":"1","quality_controlled":"1","date_created":"2019-12-15T23:00:42Z","status":"public","volume":33,"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","citation":{"chicago":"Klotz, Lisa, Olaf Wendler, Renato Frischknecht, Ryuichi Shigemoto, Holger Schulze, and Ralf Enz. “Localization of Group II and III Metabotropic Glutamate Receptors at Pre- and Postsynaptic Sites of Inner Hair Cell Ribbon Synapses.” <i>FASEB Journal</i>. FASEB, 2019. <a href=\"https://doi.org/10.1096/fj.201901543R\">https://doi.org/10.1096/fj.201901543R</a>.","apa":"Klotz, L., Wendler, O., Frischknecht, R., Shigemoto, R., Schulze, H., &#38; Enz, R. (2019). Localization of group II and III metabotropic glutamate receptors at pre- and postsynaptic sites of inner hair cell ribbon synapses. <i>FASEB Journal</i>. FASEB. <a href=\"https://doi.org/10.1096/fj.201901543R\">https://doi.org/10.1096/fj.201901543R</a>","ieee":"L. Klotz, O. Wendler, R. Frischknecht, R. Shigemoto, H. Schulze, and R. Enz, “Localization of group II and III metabotropic glutamate receptors at pre- and postsynaptic sites of inner hair cell ribbon synapses,” <i>FASEB Journal</i>, vol. 33, no. 12. FASEB, pp. 13734–13746, 2019.","mla":"Klotz, Lisa, et al. “Localization of Group II and III Metabotropic Glutamate Receptors at Pre- and Postsynaptic Sites of Inner Hair Cell Ribbon Synapses.” <i>FASEB Journal</i>, vol. 33, no. 12, FASEB, 2019, pp. 13734–46, doi:<a href=\"https://doi.org/10.1096/fj.201901543R\">10.1096/fj.201901543R</a>.","ama":"Klotz L, Wendler O, Frischknecht R, Shigemoto R, Schulze H, Enz R. Localization of group II and III metabotropic glutamate receptors at pre- and postsynaptic sites of inner hair cell ribbon synapses. <i>FASEB Journal</i>. 2019;33(12):13734-13746. doi:<a href=\"https://doi.org/10.1096/fj.201901543R\">10.1096/fj.201901543R</a>","ista":"Klotz L, Wendler O, Frischknecht R, Shigemoto R, Schulze H, Enz R. 2019. Localization of group II and III metabotropic glutamate receptors at pre- and postsynaptic sites of inner hair cell ribbon synapses. FASEB Journal. 33(12), 13734–13746.","short":"L. Klotz, O. Wendler, R. Frischknecht, R. Shigemoto, H. Schulze, R. Enz, FASEB Journal 33 (2019) 13734–13746."}},{"doi":"10.1007/978-3-030-31784-3_27","article_processing_charge":"No","abstract":[{"text":"A probabilistic vector addition system with states (pVASS) is a finite state Markov process augmented with non-negative integer counters that can be incremented or decremented during each state transition, blocking any behaviour that would cause a counter to decrease below zero. The pVASS can be used as abstractions of probabilistic programs with many decidable properties. The use of pVASS as abstractions requires the presence of nondeterminism in the model. In this paper, we develop techniques for checking fast termination of pVASS with nondeterminism. That is, for every initial configuration of size n, we consider the worst expected number of transitions needed to reach a configuration with some counter negative (the expected termination time). We show that the problem whether the asymptotic expected termination time is linear is decidable in polynomial time for a certain natural class of pVASS with nondeterminism. Furthermore, we show the following dichotomy: if the asymptotic expected termination time is not linear, then it is at least quadratic, i.e., in Ω(n2).","lang":"eng"}],"project":[{"call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"day":"21","conference":{"location":"Taipei, Taiwan","start_date":"2019-10-28","name":"ATVA: Automated TEchnology for Verification and Analysis","end_date":"2019-10-31"},"_id":"7183","external_id":{"arxiv":["1907.11010"],"isi":["000723515700027"]},"publisher":"Springer Nature","author":[{"full_name":"Brázdil, Tomás","first_name":"Tomás","last_name":"Brázdil"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"last_name":"Kucera","first_name":"Antonín","full_name":"Kucera, Antonín"},{"full_name":"Novotný, Petr","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","last_name":"Novotný"},{"first_name":"Dominik","full_name":"Velan, Dominik","last_name":"Velan"}],"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1907.11010"}],"month":"10","date_updated":"2026-04-16T09:51:24Z","oa_version":"Preprint","oa":1,"status":"public","volume":11781,"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","citation":{"ista":"Brázdil T, Chatterjee K, Kucera A, Novotný P, Velan D. 2019. Deciding fast termination for probabilistic VASS with nondeterminism. International Symposium on Automated Technology for Verification and Analysis. ATVA: Automated TEchnology for Verification and Analysis, LNCS, vol. 11781, 462–478.","short":"T. Brázdil, K. Chatterjee, A. Kucera, P. Novotný, D. Velan, in:, International Symposium on Automated Technology for Verification and Analysis, Springer Nature, 2019, pp. 462–478.","mla":"Brázdil, Tomás, et al. “Deciding Fast Termination for Probabilistic VASS with Nondeterminism.” <i>International Symposium on Automated Technology for Verification and Analysis</i>, vol. 11781, Springer Nature, 2019, pp. 462–78, doi:<a href=\"https://doi.org/10.1007/978-3-030-31784-3_27\">10.1007/978-3-030-31784-3_27</a>.","ama":"Brázdil T, Chatterjee K, Kucera A, Novotný P, Velan D. Deciding fast termination for probabilistic VASS with nondeterminism. In: <i>International Symposium on Automated Technology for Verification and Analysis</i>. Vol 11781. Springer Nature; 2019:462-478. doi:<a href=\"https://doi.org/10.1007/978-3-030-31784-3_27\">10.1007/978-3-030-31784-3_27</a>","apa":"Brázdil, T., Chatterjee, K., Kucera, A., Novotný, P., &#38; Velan, D. (2019). Deciding fast termination for probabilistic VASS with nondeterminism. In <i>International Symposium on Automated Technology for Verification and Analysis</i> (Vol. 11781, pp. 462–478). Taipei, Taiwan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-31784-3_27\">https://doi.org/10.1007/978-3-030-31784-3_27</a>","ieee":"T. Brázdil, K. Chatterjee, A. Kucera, P. Novotný, and D. Velan, “Deciding fast termination for probabilistic VASS with nondeterminism,” in <i>International Symposium on Automated Technology for Verification and Analysis</i>, Taipei, Taiwan, 2019, vol. 11781, pp. 462–478.","chicago":"Brázdil, Tomás, Krishnendu Chatterjee, Antonín Kucera, Petr Novotný, and Dominik Velan. “Deciding Fast Termination for Probabilistic VASS with Nondeterminism.” In <i>International Symposium on Automated Technology for Verification and Analysis</i>, 11781:462–78. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-31784-3_27\">https://doi.org/10.1007/978-3-030-31784-3_27</a>."},"scopus_import":"1","quality_controlled":"1","date_created":"2019-12-15T23:00:44Z","publication":"International Symposium on Automated Technology for Verification and Analysis","title":"Deciding fast termination for probabilistic VASS with nondeterminism","language":[{"iso":"eng"}],"type":"conference","year":"2019","alternative_title":["LNCS"],"date_published":"2019-10-21T00:00:00Z","page":"462-478","arxiv":1,"intvolume":"     11781","isi":1,"department":[{"_id":"KrCh"}],"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783030317836"],"issn":["0302-9743"]}},{"isi":1,"department":[{"_id":"LaEr"},{"_id":"JaMa"}],"publication_identifier":{"issn":["0246-0203"]},"intvolume":"        55","date_published":"2019-09-25T00:00:00Z","arxiv":1,"page":"1203-1225","year":"2019","type":"journal_article","issue":"3","publication":"Annales de l'institut Henri Poincare (B) Probability and Statistics","title":"Limit law of a second class particle in TASEP with non-random initial condition","language":[{"iso":"eng"}],"quality_controlled":"1","scopus_import":"1","date_created":"2018-12-11T11:44:29Z","status":"public","volume":55,"citation":{"ista":"Ferrari P, Ghosal P, Nejjar P. 2019. Limit law of a second class particle in TASEP with non-random initial condition. Annales de l’institut Henri Poincare (B) Probability and Statistics. 55(3), 1203–1225.","short":"P. Ferrari, P. Ghosal, P. Nejjar, Annales de l’institut Henri Poincare (B) Probability and Statistics 55 (2019) 1203–1225.","mla":"Ferrari, Patrick, et al. “Limit Law of a Second Class Particle in TASEP with Non-Random Initial Condition.” <i>Annales de l’institut Henri Poincare (B) Probability and Statistics</i>, vol. 55, no. 3, Institute of Mathematical Statistics, 2019, pp. 1203–25, doi:<a href=\"https://doi.org/10.1214/18-AIHP916\">10.1214/18-AIHP916</a>.","ama":"Ferrari P, Ghosal P, Nejjar P. Limit law of a second class particle in TASEP with non-random initial condition. <i>Annales de l’institut Henri Poincare (B) Probability and Statistics</i>. 2019;55(3):1203-1225. doi:<a href=\"https://doi.org/10.1214/18-AIHP916\">10.1214/18-AIHP916</a>","apa":"Ferrari, P., Ghosal, P., &#38; Nejjar, P. (2019). Limit law of a second class particle in TASEP with non-random initial condition. <i>Annales de l’institut Henri Poincare (B) Probability and Statistics</i>. Institute of Mathematical Statistics. <a href=\"https://doi.org/10.1214/18-AIHP916\">https://doi.org/10.1214/18-AIHP916</a>","ieee":"P. Ferrari, P. Ghosal, and P. Nejjar, “Limit law of a second class particle in TASEP with non-random initial condition,” <i>Annales de l’institut Henri Poincare (B) Probability and Statistics</i>, vol. 55, no. 3. Institute of Mathematical Statistics, pp. 1203–1225, 2019.","chicago":"Ferrari, Patrick, Promit Ghosal, and Peter Nejjar. “Limit Law of a Second Class Particle in TASEP with Non-Random Initial Condition.” <i>Annales de l’institut Henri Poincare (B) Probability and Statistics</i>. Institute of Mathematical Statistics, 2019. <a href=\"https://doi.org/10.1214/18-AIHP916\">https://doi.org/10.1214/18-AIHP916</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","oa":1,"oa_version":"Preprint","month":"09","date_updated":"2025-04-14T07:27:49Z","main_file_link":[{"url":"https://arxiv.org/abs/1710.02323","open_access":"1"}],"ec_funded":1,"project":[{"call_identifier":"FP7","grant_number":"338804","name":"Random matrices, universality and disordered quantum systems","_id":"258DCDE6-B435-11E9-9278-68D0E5697425"},{"_id":"256E75B8-B435-11E9-9278-68D0E5697425","name":"Optimal Transport and Stochastic Dynamics","call_identifier":"H2020","grant_number":"716117"}],"day":"25","publication_status":"published","_id":"72","external_id":{"isi":["000487763200001"],"arxiv":["1710.02323"]},"author":[{"last_name":"Ferrari","full_name":"Ferrari, Patrick","first_name":"Patrick"},{"last_name":"Ghosal","full_name":"Ghosal, Promit","first_name":"Promit"},{"last_name":"Nejjar","id":"4BF426E2-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","full_name":"Nejjar, Peter"}],"publisher":"Institute of Mathematical Statistics","doi":"10.1214/18-AIHP916","article_processing_charge":"No","abstract":[{"text":"We consider the totally asymmetric simple exclusion process (TASEP) with non-random initial condition having density ρ on ℤ− and λ on ℤ+, and a second class particle initially at the origin. For ρ&lt;λ, there is a shock and the second class particle moves with speed 1−λ−ρ. For large time t, we show that the position of the second class particle fluctuates on a t1/3 scale and determine its limiting law. We also obtain the limiting distribution of the number of steps made by the second class particle until time t.","lang":"eng"}]},{"_id":"7228","publication_status":"published","external_id":{"isi":["000851061400023"]},"author":[{"full_name":"Koval, Nikita","first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","last_name":"Koval"},{"last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Roman","full_name":"Elizarov, Roman","last_name":"Elizarov"}],"publisher":"Springer Nature","day":"13","conference":{"end_date":"2019-08-30","name":"Euro-Par: European Conference on Parallel Processing","location":"Göttingen, Germany","start_date":"2019-08-26"},"doi":"10.1007/978-3-030-29400-7_23","abstract":[{"text":"Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) and actor models, which share data via explicit communication. These models have been known for almost half a century, and have recently had started to gain significant traction among modern programming languages. The common abstraction for communication between several processes is the channel. Although channels are similar to producer-consumer data structures, they have different semantics and support additional operations, such as the select expression. Despite their growing popularity, most known implementations of channels use lock-based data structures and can be rather inefficient.\r\n\r\nIn this paper, we present the first efficient lock-free algorithm for implementing a communication channel for CSP programming. We provide implementations and experimental results in the Kotlin and Go programming languages. Our new algorithm outperforms existing implementations on many workloads, while providing non-blocking progress guarantee. Our design can serve as an example of how to construct general communication data structures for CSP and actor models. ","lang":"eng"}],"article_processing_charge":"No","date_updated":"2023-09-06T14:53:59Z","month":"08","oa_version":"None","date_created":"2020-01-05T23:00:46Z","scopus_import":"1","quality_controlled":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"short":"N. Koval, D.-A. Alistarh, R. Elizarov, in:, 25th Anniversary of Euro-Par, Springer Nature, 2019, pp. 317–333.","ista":"Koval N, Alistarh D-A, Elizarov R. 2019. Scalable FIFO channels for programming via communicating sequential processes. 25th Anniversary of Euro-Par. Euro-Par: European Conference on Parallel Processing, LNCS, vol. 11725, 317–333.","mla":"Koval, Nikita, et al. “Scalable FIFO Channels for Programming via Communicating Sequential Processes.” <i>25th Anniversary of Euro-Par</i>, vol. 11725, Springer Nature, 2019, pp. 317–33, doi:<a href=\"https://doi.org/10.1007/978-3-030-29400-7_23\">10.1007/978-3-030-29400-7_23</a>.","ama":"Koval N, Alistarh D-A, Elizarov R. Scalable FIFO channels for programming via communicating sequential processes. In: <i>25th Anniversary of Euro-Par</i>. Vol 11725. Springer Nature; 2019:317-333. doi:<a href=\"https://doi.org/10.1007/978-3-030-29400-7_23\">10.1007/978-3-030-29400-7_23</a>","apa":"Koval, N., Alistarh, D.-A., &#38; Elizarov, R. (2019). Scalable FIFO channels for programming via communicating sequential processes. In <i>25th Anniversary of Euro-Par</i> (Vol. 11725, pp. 317–333). Göttingen, Germany: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-29400-7_23\">https://doi.org/10.1007/978-3-030-29400-7_23</a>","ieee":"N. Koval, D.-A. Alistarh, and R. Elizarov, “Scalable FIFO channels for programming via communicating sequential processes,” in <i>25th Anniversary of Euro-Par</i>, Göttingen, Germany, 2019, vol. 11725, pp. 317–333.","chicago":"Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. “Scalable FIFO Channels for Programming via Communicating Sequential Processes.” In <i>25th Anniversary of Euro-Par</i>, 11725:317–33. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-29400-7_23\">https://doi.org/10.1007/978-3-030-29400-7_23</a>."},"status":"public","volume":11725,"type":"conference","year":"2019","language":[{"iso":"eng"}],"publication":"25th Anniversary of Euro-Par","title":"Scalable FIFO channels for programming via communicating sequential processes","intvolume":"     11725","page":"317-333","alternative_title":["LNCS"],"date_published":"2019-08-13T00:00:00Z","isi":1,"department":[{"_id":"DaAl"}],"publication_identifier":{"isbn":["978-3-0302-9399-4"],"issn":["0302-9743"],"eissn":["1611-3349"]}},{"page":"230-243","arxiv":1,"alternative_title":["LNCS"],"date_published":"2019-11-28T00:00:00Z","intvolume":"     11904","isi":1,"department":[{"_id":"UlWa"}],"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["978-3-0303-5801-3"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Arroyo Guevara, Alan M, Martin Derka, and Irene Parada. “Extending Simple Drawings.” In <i>27th International Symposium on Graph Drawing and Network Visualization</i>, 11904:230–43. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">https://doi.org/10.1007/978-3-030-35802-0_18</a>.","ieee":"A. M. Arroyo Guevara, M. Derka, and I. Parada, “Extending simple drawings,” in <i>27th International Symposium on Graph Drawing and Network Visualization</i>, Prague, Czech Republic, 2019, vol. 11904, pp. 230–243.","apa":"Arroyo Guevara, A. M., Derka, M., &#38; Parada, I. (2019). Extending simple drawings. In <i>27th International Symposium on Graph Drawing and Network Visualization</i> (Vol. 11904, pp. 230–243). Prague, Czech Republic: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">https://doi.org/10.1007/978-3-030-35802-0_18</a>","ama":"Arroyo Guevara AM, Derka M, Parada I. Extending simple drawings. In: <i>27th International Symposium on Graph Drawing and Network Visualization</i>. Vol 11904. Springer Nature; 2019:230-243. doi:<a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">10.1007/978-3-030-35802-0_18</a>","mla":"Arroyo Guevara, Alan M., et al. “Extending Simple Drawings.” <i>27th International Symposium on Graph Drawing and Network Visualization</i>, vol. 11904, Springer Nature, 2019, pp. 230–43, doi:<a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">10.1007/978-3-030-35802-0_18</a>.","short":"A.M. Arroyo Guevara, M. Derka, I. Parada, in:, 27th International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2019, pp. 230–243.","ista":"Arroyo Guevara AM, Derka M, Parada I. 2019. Extending simple drawings. 27th International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 11904, 230–243."},"status":"public","volume":11904,"date_created":"2020-01-05T23:00:47Z","quality_controlled":"1","scopus_import":"1","language":[{"iso":"eng"}],"publication":"27th International Symposium on Graph Drawing and Network Visualization","title":"Extending simple drawings","type":"conference","year":"2019","main_file_link":[{"url":"https://arxiv.org/abs/1908.08129","open_access":"1"}],"date_updated":"2025-04-14T07:44:07Z","month":"11","oa_version":"Preprint","oa":1,"doi":"10.1007/978-3-030-35802-0_18","article_processing_charge":"No","abstract":[{"text":"Simple drawings of graphs are those in which each pair of edges share at most one point, either a common endpoint or a proper crossing. In this paper we study the problem of extending a simple drawing D(G) of a graph G by inserting a set of edges from the complement of G into D(G) such that the result is a simple drawing. In the context of rectilinear drawings, the problem is trivial. For pseudolinear drawings, the existence of such an extension follows from Levi’s enlargement lemma. In contrast, we prove that deciding if a given set of edges can be inserted into a simple drawing is NP-complete. Moreover, we show that the maximization version of the problem is APX-hard. We also present a polynomial-time algorithm for deciding whether one edge uv can be inserted into D(G) when {u,v} is a dominating set for the graph G.","lang":"eng"}],"external_id":{"isi":["000612918800018"],"arxiv":["1908.08129"]},"_id":"7230","author":[{"first_name":"Alan M","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara"},{"last_name":"Derka","full_name":"Derka, Martin","first_name":"Martin"},{"full_name":"Parada, Irene","first_name":"Irene","last_name":"Parada"}],"publication_status":"published","publisher":"Springer Nature","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411"}],"day":"28","conference":{"name":"GD: Graph Drawing and Network Visualization","start_date":"2019-09-17","location":"Prague, Czech Republic","end_date":"2019-09-20"},"ec_funded":1},{"day":"13","conference":{"end_date":"2019-08-29","location":"Amsterdam, The Netherlands","start_date":"2019-08-27","name":"FORMATS: Formal Modeling and Analysis of Timed Systems"},"project":[{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407","call_identifier":"FWF"},{"name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","call_identifier":"FWF"}],"publication_status":"published","_id":"7231","author":[{"full_name":"Kong, Hui","orcid":"0000-0002-3066-6941","first_name":"Hui","id":"3BDE25AA-F248-11E8-B48F-1D18A9856A87","last_name":"Kong"},{"first_name":"Ezio","full_name":"Bartocci, Ezio","last_name":"Bartocci"},{"last_name":"Jiang","full_name":"Jiang, Yu","first_name":"Yu"},{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"isi":["000611677700008"],"arxiv":["1907.11514"]},"publisher":"Springer Nature","article_processing_charge":"No","abstract":[{"lang":"eng","text":"Piecewise Barrier Tubes (PBT) is a new technique for flowpipe overapproximation for nonlinear systems with polynomial dynamics, which leverages a combination of barrier certificates. PBT has advantages over traditional time-step based methods in dealing with those nonlinear dynamical systems in which there is a large difference in speed between trajectories, producing an overapproximation that is time independent. However, the existing approach for PBT is not efficient due to the application of interval methods for enclosure-box computation, and it can only deal with continuous dynamical systems without uncertainty. In this paper, we extend the approach with the ability to handle both continuous and hybrid dynamical systems with uncertainty that can reside in parameters and/or noise. We also improve the efficiency of the method significantly, by avoiding the use of interval-based methods for the enclosure-box computation without loosing soundness. We have developed a C++ prototype implementing the proposed approach and we evaluate it on several benchmarks. The experiments show that our approach is more efficient and precise than other methods in the literature."}],"doi":"10.1007/978-3-030-29662-9_8","month":"08","date_updated":"2025-04-15T06:26:06Z","main_file_link":[{"url":"https://arxiv.org/abs/1907.11514","open_access":"1"}],"oa":1,"oa_version":"Preprint","scopus_import":"1","quality_controlled":"1","date_created":"2020-01-05T23:00:47Z","volume":11750,"status":"public","citation":{"apa":"Kong, H., Bartocci, E., Jiang, Y., &#38; Henzinger, T. A. (2019). Piecewise robust barrier tubes for nonlinear hybrid systems with uncertainty. In <i>17th International Conference on Formal Modeling and Analysis of Timed Systems</i> (Vol. 11750, pp. 123–141). Amsterdam, The Netherlands: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-29662-9_8\">https://doi.org/10.1007/978-3-030-29662-9_8</a>","ieee":"H. Kong, E. Bartocci, Y. Jiang, and T. A. Henzinger, “Piecewise robust barrier tubes for nonlinear hybrid systems with uncertainty,” in <i>17th International Conference on Formal Modeling and Analysis of Timed Systems</i>, Amsterdam, The Netherlands, 2019, vol. 11750, pp. 123–141.","chicago":"Kong, Hui, Ezio Bartocci, Yu Jiang, and Thomas A Henzinger. “Piecewise Robust Barrier Tubes for Nonlinear Hybrid Systems with Uncertainty.” In <i>17th International Conference on Formal Modeling and Analysis of Timed Systems</i>, 11750:123–41. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-29662-9_8\">https://doi.org/10.1007/978-3-030-29662-9_8</a>.","short":"H. Kong, E. Bartocci, Y. Jiang, T.A. Henzinger, in:, 17th International Conference on Formal Modeling and Analysis of Timed Systems, Springer Nature, 2019, pp. 123–141.","ista":"Kong H, Bartocci E, Jiang Y, Henzinger TA. 2019. Piecewise robust barrier tubes for nonlinear hybrid systems with uncertainty. 17th International Conference on Formal Modeling and Analysis of Timed Systems. FORMATS: Formal Modeling and Analysis of Timed Systems, LNCS, vol. 11750, 123–141.","mla":"Kong, Hui, et al. “Piecewise Robust Barrier Tubes for Nonlinear Hybrid Systems with Uncertainty.” <i>17th International Conference on Formal Modeling and Analysis of Timed Systems</i>, vol. 11750, Springer Nature, 2019, pp. 123–41, doi:<a href=\"https://doi.org/10.1007/978-3-030-29662-9_8\">10.1007/978-3-030-29662-9_8</a>.","ama":"Kong H, Bartocci E, Jiang Y, Henzinger TA. Piecewise robust barrier tubes for nonlinear hybrid systems with uncertainty. In: <i>17th International Conference on Formal Modeling and Analysis of Timed Systems</i>. Vol 11750. Springer Nature; 2019:123-141. doi:<a href=\"https://doi.org/10.1007/978-3-030-29662-9_8\">10.1007/978-3-030-29662-9_8</a>"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","type":"conference","year":"2019","title":"Piecewise robust barrier tubes for nonlinear hybrid systems with uncertainty","publication":"17th International Conference on Formal Modeling and Analysis of Timed Systems","language":[{"iso":"eng"}],"intvolume":"     11750","date_published":"2019-08-13T00:00:00Z","alternative_title":["LNCS"],"arxiv":1,"page":"123-141","department":[{"_id":"ToHe"}],"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["978-3-0302-9661-2"]},"isi":1}]