[{"title":"CEGAR for qualitative analysis of probabilistic systems","department":[{"_id":"KrCh"}],"_id":"5413","has_accepted_license":"1","related_material":{"record":[{"id":"2063","relation":"later_version","status":"public"},{"id":"5412","status":"public","relation":"earlier_version"},{"relation":"later_version","status":"public","id":"5414"}]},"oa":1,"ddc":["000"],"doi":"10.15479/AT:IST-2014-153-v2-2","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}],"publication_status":"published","citation":{"apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>.","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>.","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014."},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw","last_name":"Daca","first_name":"Przemyslaw"},{"first_name":"Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","type":"technical_report","date_updated":"2023-02-23T12:25:18Z","year":"2014","day":"06","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"month":"02","date_created":"2018-12-12T11:39:11Z","status":"public","file":[{"relation":"main_file","date_created":"2018-12-12T11:54:17Z","file_size":606049,"content_type":"application/pdf","creator":"system","file_id":"5539","date_updated":"2020-07-14T12:46:47Z","checksum":"ce4967a184d84863eec76c66cbac1614","file_name":"IST-2014-153-v2+2_main.pdf","access_level":"open_access"}],"date_published":"2014-02-06T00:00:00Z","pubrep_id":"164","page":"33","file_date_updated":"2020-07-14T12:46:47Z","publisher":"IST Austria"},{"publication_status":"published","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. \r\nWe have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}],"ddc":["000"],"oa":1,"doi":"10.15479/AT:IST-2014-153-v3-1","related_material":{"record":[{"id":"2063","status":"public","relation":"later_version"},{"id":"5412","status":"public","relation":"earlier_version"},{"id":"5413","status":"public","relation":"earlier_version"}]},"language":[{"iso":"eng"}],"_id":"5414","has_accepted_license":"1","department":[{"_id":"KrCh"}],"title":"CEGAR for qualitative analysis of probabilistic systems","day":"07","year":"2014","date_updated":"2023-02-23T12:25:15Z","type":"technical_report","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw","first_name":"Przemyslaw","last_name":"Daca"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik"}],"citation":{"ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>.","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>"},"status":"public","date_created":"2018-12-12T11:39:12Z","month":"02","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:48Z","page":"33","pubrep_id":"165","date_published":"2014-02-07T00:00:00Z","file":[{"access_level":"open_access","checksum":"87b93fe9af71fc5c94b0eb6151537e11","file_name":"IST-2014-153-v3+1_main.pdf","file_id":"5464","date_updated":"2020-07-14T12:46:48Z","content_type":"application/pdf","creator":"system","file_size":606227,"date_created":"2018-12-12T11:53:03Z","relation":"main_file"}]},{"abstract":[{"lang":"eng","text":"Recently there has been a significant effort to add quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, several basic system properties such as average response time cannot be expressed with weighted automata. In this work, we introduce nested weighted automata as a new formalism for expressing important quantitative properties such as average response time. We establish an almost complete decidability picture for the basic decision problems for nested weighted automata, and illustrate its applicability in several domains.  "}],"publication_status":"published","has_accepted_license":"1","_id":"5415","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"1656"},{"status":"public","relation":"later_version","id":"467"},{"id":"5436","relation":"later_version","status":"public"}]},"doi":"10.15479/AT:IST-2014-170-v1-1","oa":1,"language":[{"iso":"eng"}],"ddc":["004"],"title":"Nested weighted automata","year":"2014","day":"19","oa_version":"Published Version","date_updated":"2023-02-23T12:26:19Z","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"}],"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Nested Weighted Automata</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2014). <i>Nested weighted automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">https://doi.org/10.15479/AT:IST-2014-170-v1-1</a>","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. <i>Nested Weighted Automata</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">https://doi.org/10.15479/AT:IST-2014-170-v1-1</a>.","ista":"Chatterjee K, Henzinger TA, Otop J. 2014. Nested weighted automata, IST Austria, 27p.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2014.","ama":"Chatterjee K, Henzinger TA, Otop J. <i>Nested Weighted Automata</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>"},"status":"public","month":"02","date_created":"2018-12-12T11:39:12Z","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:48Z","pubrep_id":"170","page":"27","file":[{"file_size":573457,"content_type":"application/pdf","creator":"system","relation":"main_file","date_created":"2018-12-12T11:53:36Z","checksum":"31f90dcf2cf899c3f8c6427cfcc2b3c7","file_name":"IST-2014-170-v1+1_main.pdf","access_level":"open_access","file_id":"5497","date_updated":"2020-07-14T12:46:48Z"}],"date_published":"2014-02-19T00:00:00Z"},{"author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","first_name":"Jan","last_name":"Otop"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Henzinger, T. A., &#38; Otop, J. (2014). <i>Model measuring for hybrid systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">https://doi.org/10.15479/AT:IST-2014-171-v1-1</a>","mla":"Henzinger, Thomas A., and Jan Otop. <i>Model Measuring for Hybrid Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">10.15479/AT:IST-2014-171-v1-1</a>.","ieee":"T. A. Henzinger and J. Otop, <i>Model measuring for hybrid systems</i>. IST Austria, 2014.","ama":"Henzinger TA, Otop J. <i>Model Measuring for Hybrid Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">10.15479/AT:IST-2014-171-v1-1</a>","ista":"Henzinger TA, Otop J. 2014. Model measuring for hybrid systems, IST Austria, 22p.","short":"T.A. Henzinger, J. Otop, Model Measuring for Hybrid Systems, IST Austria, 2014.","chicago":"Henzinger, Thomas A, and Jan Otop. <i>Model Measuring for Hybrid Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">https://doi.org/10.15479/AT:IST-2014-171-v1-1</a>."},"year":"2014","day":"19","oa_version":"Published Version","type":"technical_report","date_updated":"2023-02-23T10:33:21Z","_id":"5416","has_accepted_license":"1","department":[{"_id":"ToHe"}],"ddc":["005"],"language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"2217"}]},"oa":1,"doi":"10.15479/AT:IST-2014-171-v1-1","title":"Model measuring for hybrid systems","abstract":[{"text":"As hybrid systems involve continuous behaviors, they should be evaluated by quantitative methods, rather than qualitative methods. In this paper we adapt a quantitative framework, called model measuring, to the hybrid systems domain. The model-measuring problem asks, given a model M and a specification, what is the maximal distance such that all models within that distance from M satisfy (or violate) the specification. A distance function on models is given as part of the input of the problem. Distances, especially related to continuous behaviors are more natural in the hybrid case than the discrete case. We are interested in distances represented by monotonic hybrid automata, a hybrid counterpart of (discrete) weighted automata, whose recognized timed languages are monotone (w.r.t. inclusion) in the values of parameters.The contributions of this paper are twofold. First, we give sufficient conditions under which the model-measuring problem can be solved. Second, we discuss the modeling of distances and applications of the model-measuring problem.","lang":"eng"}],"publication_status":"published","pubrep_id":"171","page":"22","file":[{"access_level":"open_access","checksum":"445456d22371e4e49aad2b9a0c13bf80","file_name":"IST-2014-171-v1+1_report.pdf","date_updated":"2020-07-14T12:46:49Z","file_id":"5492","file_size":712077,"content_type":"application/pdf","creator":"system","date_created":"2018-12-12T11:53:32Z","relation":"main_file"}],"date_published":"2014-02-19T00:00:00Z","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:49Z","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"status":"public","month":"02","date_created":"2018-12-12T11:39:12Z"},{"date_updated":"2023-02-23T10:38:10Z","type":"technical_report","oa_version":"Published Version","day":"19","year":"2014","citation":{"ama":"Henzinger TA, Otop J. <i>From Model Checking to Model Measuring</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">10.15479/AT:IST-2014-172-v1-1</a>","ieee":"T. A. Henzinger and J. Otop, <i>From model checking to model measuring</i>. IST Austria, 2014.","ista":"Henzinger TA, Otop J. 2014. From model checking to model measuring, IST Austria, 14p.","short":"T.A. Henzinger, J. Otop, From Model Checking to Model Measuring, IST Austria, 2014.","chicago":"Henzinger, Thomas A, and Jan Otop. <i>From Model Checking to Model Measuring</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">https://doi.org/10.15479/AT:IST-2014-172-v1-1</a>.","apa":"Henzinger, T. A., &#38; Otop, J. (2014). <i>From model checking to model measuring</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">https://doi.org/10.15479/AT:IST-2014-172-v1-1</a>","mla":"Henzinger, Thomas A., and Jan Otop. <i>From Model Checking to Model Measuring</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">10.15479/AT:IST-2014-172-v1-1</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","first_name":"Jan","last_name":"Otop"}],"publication_status":"published","abstract":[{"lang":"eng","text":"We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M'within distance ρ from M satisfy (or violate)φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata.\r\nThe model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification.\r\nWe show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved.\r\nWe use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. \r\nWe give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications."}],"title":"From model checking to model measuring","language":[{"iso":"eng"}],"ddc":["000"],"doi":"10.15479/AT:IST-2014-172-v1-1","related_material":{"record":[{"id":"2327","status":"public","relation":"later_version"}]},"oa":1,"department":[{"_id":"ToHe"}],"_id":"5417","has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:49Z","publisher":"IST Austria","date_published":"2014-02-19T00:00:00Z","file":[{"file_id":"5481","date_updated":"2020-07-14T12:46:49Z","access_level":"open_access","checksum":"fcc3eab903cfcd3778b338d2d0d44d18","file_name":"IST-2014-172-v1+1_report.pdf","date_created":"2018-12-12T11:53:20Z","relation":"main_file","creator":"system","content_type":"application/pdf","file_size":383052}],"page":"14","pubrep_id":"175","date_created":"2018-12-12T11:39:13Z","month":"02","status":"public","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]}},{"language":[{"iso":"eng"}],"oa":1,"ddc":["000","005"],"doi":"10.15479/AT:IST-2014-176-v1-1","related_material":{"record":[{"id":"2163","status":"public","relation":"later_version"}]},"has_accepted_license":"1","_id":"5418","department":[{"_id":"KrCh"}],"title":"Games with a weak adversary","publication_status":"published","abstract":[{"text":"We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results.","lang":"eng"}],"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>.","apa":"Chatterjee, K., &#38; Doyen, L. (2014). <i>Games with a weak adversary</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>","ama":"Chatterjee K, Doyen L. <i>Games with a Weak Adversary</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>","ieee":"K. Chatterjee and L. Doyen, <i>Games with a weak adversary</i>. IST Austria, 2014.","short":"K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>.","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p."},"day":"22","year":"2014","date_updated":"2023-02-23T10:30:58Z","type":"technical_report","oa_version":"Published Version","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"status":"public","date_created":"2018-12-12T11:39:13Z","month":"03","page":"18","pubrep_id":"176","date_published":"2014-03-22T00:00:00Z","file":[{"checksum":"1d6958aa60050e1c3e932c6e5f34c39f","file_name":"IST-2014-176-v1+1_icalp_14.pdf","access_level":"open_access","file_id":"5468","date_updated":"2020-07-14T12:46:49Z","file_size":328253,"creator":"system","content_type":"application/pdf","relation":"main_file","date_created":"2018-12-12T11:53:07Z"}],"publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:49Z"},{"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2014). <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria, 2014.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p."},"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pavlogiannis","first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","date_updated":"2021-01-12T08:02:03Z","type":"technical_report","year":"2014","day":"14","title":"Improved algorithms for reachability and shortest path on low tree-width graphs","_id":"5419","department":[{"_id":"KrCh"}],"has_accepted_license":"1","doi":"10.15479/AT:IST-2014-187-v1-1","ddc":["000"],"oa":1,"language":[{"iso":"eng"}],"abstract":[{"text":"We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold:\r\n1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing).\r\n2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries.\r\n3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries.\r\nOur algorithms improve all existing results, and use very simple data structures.","lang":"eng"}],"publication_status":"published","file":[{"relation":"main_file","date_created":"2018-12-12T11:54:25Z","file_size":670031,"content_type":"application/pdf","creator":"system","file_id":"5548","date_updated":"2020-07-14T12:46:50Z","checksum":"c608e66030a4bf51d2d99b451f539b99","file_name":"IST-2014-187-v1+1_main_full_tech.pdf","access_level":"open_access"}],"date_published":"2014-04-14T00:00:00Z","pubrep_id":"187","page":"34","file_date_updated":"2020-07-14T12:46:50Z","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"month":"04","date_created":"2018-12-12T11:39:13Z","status":"public"},{"title":"The value 1 problem for concurrent mean-payoff games","has_accepted_license":"1","_id":"5420","department":[{"_id":"KrCh"}],"ddc":["000","005"],"oa":1,"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2014-191-v1-1","abstract":[{"lang":"eng","text":"We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy)."}],"publication_status":"published","citation":{"ama":"Chatterjee K, Ibsen-Jensen R. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>","ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff Games, IST Austria, 2014.","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2014). <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>."},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","first_name":"Rasmus"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","date_updated":"2021-01-12T08:02:05Z","type":"technical_report","year":"2014","day":"14","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"month":"04","date_created":"2018-12-12T11:39:14Z","status":"public","file":[{"creator":"system","content_type":"application/pdf","file_size":584368,"relation":"main_file","date_created":"2018-12-12T11:53:58Z","checksum":"49e0fd3e62650346daf7dc04604f7a0a","file_name":"IST-2014-191-v1+1_main_full.pdf","access_level":"open_access","date_updated":"2020-07-14T12:46:50Z","file_id":"5520"}],"date_published":"2014-04-14T00:00:00Z","pubrep_id":"191","page":"49","file_date_updated":"2020-07-14T12:46:50Z","publisher":"IST Austria"},{"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen"},{"full_name":"Nowak, Martin","first_name":"Martin","last_name":"Nowak"}],"citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolution on Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolution on graphs</i>. IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolution on Graphs, IST Austria, 2014.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2014. The complexity of evolution on graphs, IST Austria, 27p.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2014). <i>The complexity of evolution on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>."},"year":"2014","day":"18","oa_version":"Published Version","date_updated":"2023-02-23T12:26:33Z","type":"technical_report","department":[{"_id":"KrCh"}],"_id":"5421","has_accepted_license":"1","ddc":["000","005"],"doi":"10.15479/AT:IST-2014-190-v2-2","language":[{"iso":"eng"}],"oa":1,"related_material":{"record":[{"id":"5432","relation":"later_version","status":"public"},{"id":"5440","status":"public","relation":"later_version"}]},"title":"The complexity of evolution on graphs","abstract":[{"text":"Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time.","lang":"eng"}],"publication_status":"published","pubrep_id":"190","page":"27","file":[{"file_id":"5538","date_updated":"2020-07-14T12:46:50Z","file_name":"IST-2014-190-v2+2_main_full.pdf","checksum":"42f3d8b563286eb0d903832bd9a848d3","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:54:16Z","creator":"system","content_type":"application/pdf","file_size":443529},{"file_id":"6852","date_updated":"2020-07-14T12:46:50Z","access_level":"open_access","file_name":"IST-2014-190-v1+1_main_full.pdf","checksum":"0c9a2fd822309719634495a35957e34d","date_created":"2019-09-06T07:30:20Z","relation":"main_file","creator":"kschuh","content_type":"application/pdf","file_size":440911}],"date_published":"2014-04-18T00:00:00Z","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:50Z","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"status":"public","month":"04","date_created":"2018-12-12T11:39:14Z"},{"language":[{"iso":"eng"}],"ddc":["020"],"oa":1,"has_accepted_license":"1","_id":"5422","department":[{"_id":"E-Lib"}],"title":"Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland","abstract":[{"text":"Notes from the Third Plenary for the Research Data Alliance in Dublin, Ireland on March 26 to 28, 2014 with focus on starting an institutional research data repository.","lang":"eng"}],"author":[{"last_name":"Porsche","first_name":"Jana","full_name":"Porsche, Jana","id":"3252EDC2-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Porsche, Jana. <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none, 2014.","apa":"Porsche, J. (2014). <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none.","ama":"Porsche J. <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none; 2014.","ieee":"J. Porsche, <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none, 2014.","chicago":"Porsche, Jana. <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none, 2014.","short":"J. Porsche, Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland, none, 2014.","ista":"Porsche J. 2014. Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland, none,p."},"year":"2014","type":"report","date_updated":"2020-07-14T23:04:56Z","oa_version":"None","status":"public","date_created":"2018-12-12T11:39:14Z","pubrep_id":"254","date_published":"2014-01-01T00:00:00Z","file":[{"content_type":"application/pdf","creator":"system","file_size":648585,"relation":"main_file","date_created":"2018-12-12T11:53:40Z","checksum":"3954896648ce8afa8f7c4425e71cff08","file_name":"IST-2014-254-v1+1_Dublin_Day_3.pdf","access_level":"open_access","file_id":"5501","date_updated":"2020-07-14T12:46:50Z"},{"checksum":"9a0d42b0b832dfe7e4b22fb6816bcbba","file_name":"IST-2014-254-v1+2_Dublin_Day_1.pdf","access_level":"open_access","date_updated":"2020-07-14T12:46:50Z","file_id":"5502","file_size":221339,"content_type":"application/pdf","creator":"system","relation":"main_file","date_created":"2018-12-12T11:53:41Z"},{"file_size":187778,"content_type":"application/pdf","creator":"system","date_created":"2018-12-12T11:53:42Z","relation":"main_file","access_level":"open_access","file_name":"IST-2014-254-v1+3_Dublin_Day_2.pdf","checksum":"498b8d629fb1bd17bff1dc43700a93e6","date_updated":"2020-07-14T12:46:50Z","file_id":"5503"}],"publisher":"none","file_date_updated":"2020-07-14T12:46:50Z"},{"alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:15Z","month":"07","status":"public","date_published":"2014-07-29T00:00:00Z","file":[{"access_level":"open_access","checksum":"4b8fde4d9ef6653837f6803921d83032","file_name":"IST-2014-300-v1+1_main.pdf","date_updated":"2020-07-14T12:46:50Z","file_id":"5514","file_size":1270021,"creator":"system","content_type":"application/pdf","date_created":"2018-12-12T11:53:53Z","relation":"main_file"}],"page":"14","pubrep_id":"300","file_date_updated":"2020-07-14T12:46:50Z","publisher":"IST Austria","title":"A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks","related_material":{"record":[{"relation":"later_version","status":"public","id":"1714"}]},"oa":1,"doi":"10.15479/AT:IST-2014-300-v1-1","ddc":["005"],"language":[{"iso":"eng"}],"_id":"5423","has_accepted_license":"1","department":[{"_id":"KrCh"}],"publication_status":"published","abstract":[{"lang":"eng","text":"We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm- deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D(over), that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application. "}],"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">10.15479/AT:IST-2014-300-v1-1</a>.","apa":"Chatterjee, K., Kössler, A., Pavlogiannis, A., &#38; Schmid, U. (2014). <i>A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">https://doi.org/10.15479/AT:IST-2014-300-v1-1</a>","ista":"Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. 2014. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks, IST Austria, 14p.","short":"K. Chatterjee, A. Kössler, A. Pavlogiannis, U. Schmid, A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Alexander Kössler, Andreas Pavlogiannis, and Ulrich Schmid. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">https://doi.org/10.15479/AT:IST-2014-300-v1-1</a>.","ieee":"K. Chatterjee, A. Kössler, A. Pavlogiannis, and U. Schmid, <i>A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks</i>. IST Austria, 2014.","ama":"Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">10.15479/AT:IST-2014-300-v1-1</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Kössler, Alexander","first_name":"Alexander","last_name":"Kössler"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","first_name":"Andreas"},{"full_name":"Schmid, Ulrich","first_name":"Ulrich","last_name":"Schmid"}],"date_updated":"2023-02-23T10:11:15Z","type":"technical_report","oa_version":"Published Version","day":"29","year":"2014"},{"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">10.15479/AT:IST-2014-305-v1-1</a>.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2014). <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">https://doi.org/10.15479/AT:IST-2014-305-v1-1</a>","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria, 2014.","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">10.15479/AT:IST-2014-305-v1-1</a>","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 12p.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">https://doi.org/10.15479/AT:IST-2014-305-v1-1</a>.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik"},{"full_name":"Gupta, Raghav","first_name":"Raghav","last_name":"Gupta"},{"full_name":"Kanodia, Ayush","last_name":"Kanodia","first_name":"Ayush"}],"date_updated":"2023-02-23T12:25:52Z","type":"technical_report","oa_version":"Published Version","day":"09","year":"2014","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","related_material":{"record":[{"status":"public","relation":"later_version","id":"1732"},{"status":"public","relation":"later_version","id":"5426"}]},"doi":"10.15479/AT:IST-2014-305-v1-1","ddc":["005"],"oa":1,"language":[{"iso":"eng"}],"has_accepted_license":"1","_id":"5424","department":[{"_id":"KrCh"}],"publication_status":"published","abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty."}],"date_published":"2014-09-09T00:00:00Z","file":[{"access_level":"open_access","file_name":"IST-2014-305-v1+1_main.pdf","checksum":"35009d5fad01198341e6c1a3353481b7","file_id":"5512","date_updated":"2020-07-14T12:46:51Z","file_size":655774,"creator":"system","content_type":"application/pdf","date_created":"2018-12-12T11:53:51Z","relation":"main_file"}],"page":"12","pubrep_id":"305","file_date_updated":"2020-07-14T12:46:51Z","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:15Z","month":"09","status":"public"},{"alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"month":"09","date_created":"2018-12-12T11:39:16Z","status":"public","file":[{"file_size":656019,"content_type":"application/pdf","creator":"system","date_created":"2018-12-12T11:54:15Z","relation":"main_file","access_level":"open_access","file_name":"IST-2014-305-v2+1_main2.pdf","checksum":"730c0a8e97cf2712a884b2cc423f3919","file_id":"5537","date_updated":"2020-07-14T12:46:51Z"}],"date_published":"2014-09-29T00:00:00Z","pubrep_id":"311","page":"10","file_date_updated":"2020-07-14T12:46:51Z","publisher":"IST Austria","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","department":[{"_id":"KrCh"}],"_id":"5426","has_accepted_license":"1","oa":1,"language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"1732"},{"status":"public","relation":"earlier_version","id":"5424"}]},"doi":"10.15479/AT:IST-2014-305-v2-1","ddc":["005"],"abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty."}],"publication_status":"published","citation":{"chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">https://doi.org/10.15479/AT:IST-2014-305-v2-1</a>.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014.","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 10p.","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">10.15479/AT:IST-2014-305-v2-1</a>","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">10.15479/AT:IST-2014-305-v2-1</a>.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2014). <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">https://doi.org/10.15479/AT:IST-2014-305-v2-1</a>"},"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin"},{"last_name":"Gupta","first_name":"Raghav","full_name":"Gupta, Raghav"},{"first_name":"Ayush","last_name":"Kanodia","full_name":"Kanodia, Ayush"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","date_updated":"2023-02-23T12:25:47Z","type":"technical_report","year":"2014","day":"29"},{"year":"2014","day":"05","oa_version":"Published Version","date_updated":"2021-01-12T08:02:09Z","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus"},{"orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas"}],"citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2014). <i>Optimal tree-decomposition balancing and reachability on low treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">https://doi.org/10.15479/AT:IST-2014-314-v1-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">10.15479/AT:IST-2014-314-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Optimal tree-decomposition balancing and reachability on low treewidth graphs, IST Austria, 24p.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">https://doi.org/10.15479/AT:IST-2014-314-v1-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs, IST Austria, 2014.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Optimal tree-decomposition balancing and reachability on low treewidth graphs</i>. IST Austria, 2014.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">10.15479/AT:IST-2014-314-v1-1</a>"},"abstract":[{"text":"We consider graphs with n nodes together with their tree-decomposition that has b = O ( n ) bags and width t , on the standard RAM computational model with wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution is an algorithm that given a graph and its tree-decomposition as input, computes a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph in O ( b ) time and space, improving a long-standing (from 1992) bound of O ( n · log n ) time for constant treewidth graphs. Our second contribution is on reachability queries for low treewidth graphs. We build on our tree-balancing algorithm and present a data-structure for graph reachability that requires O ( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time for pair queries, and O ( n · t · log t/ log n ) time for single-source queries. For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries.","lang":"eng"}],"publication_status":"published","has_accepted_license":"1","_id":"5427","department":[{"_id":"KrCh"}],"ddc":["000"],"oa":1,"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2014-314-v1-1","title":"Optimal tree-decomposition balancing and reachability on low treewidth graphs","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:52Z","pubrep_id":"314","page":"24","file":[{"file_id":"5471","date_updated":"2020-07-14T12:46:52Z","access_level":"open_access","file_name":"IST-2014-314-v1+1_long.pdf","checksum":"9d3b90bf4fff74664f182f2d95ef727a","date_created":"2018-12-12T11:53:10Z","relation":"main_file","file_size":405561,"creator":"system","content_type":"application/pdf"}],"date_published":"2014-11-05T00:00:00Z","status":"public","month":"11","date_created":"2018-12-12T11:39:16Z","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"]},{"abstract":[{"lang":"eng","text":"Simulation is an attractive alternative for language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. For non-deterministic automata, while language inclusion is PSPACE-complete, simulation can be computed in polynomial time. Simulation has also been extended in two orthogonal directions, namely, (1) fair simulation, for simulation over specified set of infinite runs; and (2) quantitative simulation, for simulation between weighted automata. Again, while fair trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial time. For weighted automata, the (quantitative) language inclusion problem is undecidable for mean-payoff automata and the decidability is open for discounted-sum automata, whereas the (quantitative) simulation reduce to mean-payoff games and discounted-sum games, which admit pseudo-polynomial time algorithms.\r\n\r\nIn this work, we study (quantitative) simulation for weighted automata with Büchi acceptance conditions, i.e., we generalize fair simulation from non-weighted automata to weighted automata. We show that imposing Büchi acceptance conditions on weighted automata changes many fundamental properties of the simulation games. For example, whereas for mean-payoff and discounted-sum games, the players do not need memory to play optimally; we show in contrast that for simulation games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal strategies for both players require infinite memory in general, and (ii) for discounted-sum objectives, optimal strategies need not exist for both players. While the simulation games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory requirements for mean-payoff objectives) as compared to their counterpart without Büchi acceptance conditions, we still present pseudo-polynomial time algorithms to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff and weighted discounted-sum automata."}],"publication_status":"published","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"_id":"5428","has_accepted_license":"1","oa":1,"ddc":["004"],"language":[{"iso":"eng"}],"related_material":{"record":[{"id":"1066","relation":"later_version","status":"public"}]},"doi":"10.15479/AT:IST-2014-315-v1-1","title":"Quantitative fair simulation games","year":"2014","day":"05","oa_version":"Published Version","type":"technical_report","date_updated":"2023-09-20T12:07:48Z","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A"},{"first_name":"Jan","last_name":"Otop","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Velner, Yaron","first_name":"Yaron","last_name":"Velner"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Quantitative Fair Simulation Games</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">10.15479/AT:IST-2014-315-v1-1</a>.","apa":"Chatterjee, K., Henzinger, T. A., Otop, J., &#38; Velner, Y. (2014). <i>Quantitative fair simulation games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">https://doi.org/10.15479/AT:IST-2014-315-v1-1</a>","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and Y. Velner, <i>Quantitative fair simulation games</i>. IST Austria, 2014.","ama":"Chatterjee K, Henzinger TA, Otop J, Velner Y. <i>Quantitative Fair Simulation Games</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">10.15479/AT:IST-2014-315-v1-1</a>","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Quantitative Fair Simulation Games, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Yaron Velner. <i>Quantitative Fair Simulation Games</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">https://doi.org/10.15479/AT:IST-2014-315-v1-1</a>.","ista":"Chatterjee K, Henzinger TA, Otop J, Velner Y. 2014. Quantitative fair simulation games, IST Austria, 26p."},"status":"public","month":"12","date_created":"2018-12-12T11:39:16Z","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:52Z","pubrep_id":"315","page":"26","file":[{"creator":"system","content_type":"application/pdf","file_size":531046,"date_created":"2018-12-12T11:53:59Z","relation":"main_file","access_level":"open_access","checksum":"b1d573bc04365625ff9974880c0aa807","file_name":"IST-2014-315-v1+1_report.pdf","file_id":"5521","date_updated":"2020-07-14T12:46:52Z"}],"date_published":"2014-12-05T00:00:00Z"},{"publisher":"Springer","editor":[{"last_name":"Nelson","first_name":"Celeste","full_name":"Nelson, Celeste"}],"volume":1189,"status":"public","date_created":"2019-03-26T08:55:59Z","month":"08","place":"New York, NY","intvolume":"      1189","year":"2014","author":[{"first_name":"Michael","last_name":"Smutny","orcid":"0000-0002-5920-9090","full_name":"Smutny, Michael","id":"3FE6E4E8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Behrndt, Martin","id":"3ECECA3A-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Behrndt"},{"first_name":"Pedro","last_name":"Campinho","full_name":"Campinho, Pedro","orcid":"0000-0002-8526-5416","id":"3AFBBC42-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0003-4088-8633","full_name":"Ruprecht, Verena","id":"4D71A03A-F248-11E8-B48F-1D18A9856A87","first_name":"Verena","last_name":"Ruprecht"},{"last_name":"Heisenberg","first_name":"Carl-Philipp J","id":"39427864-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0912-4566","full_name":"Heisenberg, Carl-Philipp J"}],"quality_controlled":"1","citation":{"apa":"Smutny, M., Behrndt, M., Campinho, P., Ruprecht, V., &#38; Heisenberg, C.-P. J. (2014). UV laser ablation to measure cell and tissue-generated forces in the zebrafish embryo in vivo and ex vivo. In C. Nelson (Ed.), <i>Tissue Morphogenesis</i> (Vol. 1189, pp. 219–235). New York, NY: Springer. <a href=\"https://doi.org/10.1007/978-1-4939-1164-6_15\">https://doi.org/10.1007/978-1-4939-1164-6_15</a>","mla":"Smutny, Michael, et al. “UV Laser Ablation to Measure Cell and Tissue-Generated Forces in the Zebrafish Embryo in Vivo and Ex Vivo.” <i>Tissue Morphogenesis</i>, edited by Celeste Nelson, vol. 1189, Springer, 2014, pp. 219–35, doi:<a href=\"https://doi.org/10.1007/978-1-4939-1164-6_15\">10.1007/978-1-4939-1164-6_15</a>.","ieee":"M. Smutny, M. Behrndt, P. Campinho, V. Ruprecht, and C.-P. J. Heisenberg, “UV laser ablation to measure cell and tissue-generated forces in the zebrafish embryo in vivo and ex vivo,” in <i>Tissue Morphogenesis</i>, vol. 1189, C. Nelson, Ed. New York, NY: Springer, 2014, pp. 219–235.","ama":"Smutny M, Behrndt M, Campinho P, Ruprecht V, Heisenberg C-PJ. UV laser ablation to measure cell and tissue-generated forces in the zebrafish embryo in vivo and ex vivo. In: Nelson C, ed. <i>Tissue Morphogenesis</i>. Vol 1189. Methods in Molecular Biology. New York, NY: Springer; 2014:219-235. doi:<a href=\"https://doi.org/10.1007/978-1-4939-1164-6_15\">10.1007/978-1-4939-1164-6_15</a>","ista":"Smutny M, Behrndt M, Campinho P, Ruprecht V, Heisenberg C-PJ. 2014.UV laser ablation to measure cell and tissue-generated forces in the zebrafish embryo in vivo and ex vivo. In: Tissue Morphogenesis. vol. 1189, 219–235.","short":"M. Smutny, M. Behrndt, P. Campinho, V. Ruprecht, C.-P.J. Heisenberg, in:, C. Nelson (Ed.), Tissue Morphogenesis, Springer, New York, NY, 2014, pp. 219–235.","chicago":"Smutny, Michael, Martin Behrndt, Pedro Campinho, Verena Ruprecht, and Carl-Philipp J Heisenberg. “UV Laser Ablation to Measure Cell and Tissue-Generated Forces in the Zebrafish Embryo in Vivo and Ex Vivo.” In <i>Tissue Morphogenesis</i>, edited by Celeste Nelson, 1189:219–35. Methods in Molecular Biology. New York, NY: Springer, 2014. <a href=\"https://doi.org/10.1007/978-1-4939-1164-6_15\">https://doi.org/10.1007/978-1-4939-1164-6_15</a>."},"publication_status":"published","abstract":[{"lang":"eng","text":"Mechanically coupled cells can generate forces driving cell and tissue morphogenesis during development. Visualization and measuring of these forces is of major importance to better understand the complexity of the biomechanic processes that shape cells and tissues. Here, we describe how UV laser ablation can be utilized to quantitatively assess mechanical tension in different tissues of the developing zebrafish and in cultures of primary germ layer progenitor cells ex vivo."}],"_id":"6178","title":"UV laser ablation to measure cell and tissue-generated forces in the zebrafish embryo in vivo and ex vivo","publication":"Tissue Morphogenesis","pmid":1,"page":"219-235","date_published":"2014-08-22T00:00:00Z","external_id":{"pmid":["25245697"]},"publication_identifier":{"isbn":["9781493911639","9781493911646"],"eissn":["1940-6029"],"issn":["1064-3745"]},"day":"22","series_title":"Methods in Molecular Biology","type":"book_chapter","date_updated":"2023-09-05T14:12:00Z","oa_version":"None","article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","language":[{"iso":"eng"}],"doi":"10.1007/978-1-4939-1164-6_15","department":[{"_id":"CaHe"}]},{"citation":{"ieee":"H. Edelsbrunner, <i>A Short Course in Computational Geometry and Topology</i>, 1st ed. Cham: Springer Nature, 2014.","ama":"Edelsbrunner H. <i>A Short Course in Computational Geometry and Topology</i>. 1st ed. Cham: Springer Nature; 2014. doi:<a href=\"https://doi.org/10.1007/978-3-319-05957-0\">10.1007/978-3-319-05957-0</a>","ista":"Edelsbrunner H. 2014. A Short Course in Computational Geometry and Topology 1st ed., Cham: Springer Nature, IX, 110p.","chicago":"Edelsbrunner, Herbert. <i>A Short Course in Computational Geometry and Topology</i>. 1st ed. SpringerBriefs in Applied Sciences and Technology. Cham: Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-319-05957-0\">https://doi.org/10.1007/978-3-319-05957-0</a>.","short":"H. Edelsbrunner, A Short Course in Computational Geometry and Topology, 1st ed., Springer Nature, Cham, 2014.","mla":"Edelsbrunner, Herbert. <i>A Short Course in Computational Geometry and Topology</i>. 1st ed., Springer Nature, 2014, doi:<a href=\"https://doi.org/10.1007/978-3-319-05957-0\">10.1007/978-3-319-05957-0</a>.","apa":"Edelsbrunner, H. (2014). <i>A Short Course in Computational Geometry and Topology</i> (1st ed.). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-319-05957-0\">https://doi.org/10.1007/978-3-319-05957-0</a>"},"article_processing_charge":"No","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert"}],"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"None","date_updated":"2022-03-04T07:47:54Z","type":"book","series_title":"SpringerBriefs in Applied Sciences and Technology","year":"2014","day":"01","edition":"1","title":"A Short Course in Computational Geometry and Topology","_id":"6853","department":[{"_id":"HeEd"}],"related_material":{"link":[{"description":"available as eBook via catalog IST BookList","url":"https://koha.app.ist.ac.at/cgi-bin/koha/opac-detail.pl?biblionumber=356106","relation":"other"},{"description":"available via catalog IST BookList","url":"https://koha.app.ist.ac.at/cgi-bin/koha/opac-detail.pl?biblionumber=373842","relation":"other"}]},"doi":"10.1007/978-3-319-05957-0","language":[{"iso":"eng"}],"abstract":[{"text":"This monograph presents a short course in computational geometry and topology. In the first part the book covers Voronoi diagrams and Delaunay triangulations, then it presents the theory of alpha complexes which play a crucial role in biology. The central part of the book is the homology theory and their computation, including the theory of persistence which is indispensable for applications, e.g. shape reconstruction. The target audience comprises researchers and practitioners in mathematics, biology, neuroscience and computer science, but the book may also be beneficial to graduate students of these fields.","lang":"eng"}],"publication_status":"published","date_published":"2014-01-01T00:00:00Z","page":"IX, 110","publisher":"Springer Nature","alternative_title":["SpringerBriefs in Applied Sciences and Technology"],"place":"Cham","scopus_import":"1","publication_identifier":{"issn":["2191-530X"],"eisbn":["9-783-3190-5957-0"],"isbn":["9-783-3190-5956-3"],"eissn":["2191-5318"]},"month":"01","date_created":"2019-09-06T09:22:33Z","status":"public"},{"citation":{"ama":"Fulek R, Kynčl J, Malinović I, Pálvölgyi D. Clustered planarity testing revisited. In: <i>International Symposium on Graph Drawing</i>. Vol 8871. Cham: Springer Nature; 2014:428-436. doi:<a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">10.1007/978-3-662-45803-7_36</a>","ieee":"R. Fulek, J. Kynčl, I. Malinović, and D. Pálvölgyi, “Clustered planarity testing revisited,” in <i>International Symposium on Graph Drawing</i>, 2014, vol. 8871, pp. 428–436.","chicago":"Fulek, Radoslav, Jan Kynčl, Igor Malinović, and Dömötör Pálvölgyi. “Clustered Planarity Testing Revisited.” In <i>International Symposium on Graph Drawing</i>, 8871:428–36. Cham: Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">https://doi.org/10.1007/978-3-662-45803-7_36</a>.","short":"R. Fulek, J. Kynčl, I. Malinović, D. Pálvölgyi, in:, International Symposium on Graph Drawing, Springer Nature, Cham, 2014, pp. 428–436.","ista":"Fulek R, Kynčl J, Malinović I, Pálvölgyi D. 2014. Clustered planarity testing revisited. International Symposium on Graph Drawing. , LNCS, vol. 8871, 428–436.","mla":"Fulek, Radoslav, et al. “Clustered Planarity Testing Revisited.” <i>International Symposium on Graph Drawing</i>, vol. 8871, Springer Nature, 2014, pp. 428–36, doi:<a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">10.1007/978-3-662-45803-7_36</a>.","apa":"Fulek, R., Kynčl, J., Malinović, I., &#38; Pálvölgyi, D. (2014). Clustered planarity testing revisited. In <i>International Symposium on Graph Drawing</i> (Vol. 8871, pp. 428–436). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">https://doi.org/10.1007/978-3-662-45803-7_36</a>"},"author":[{"orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","last_name":"Fulek"},{"full_name":"Kynčl, Jan","first_name":"Jan","last_name":"Kynčl"},{"full_name":"Malinović, Igor","first_name":"Igor","last_name":"Malinović"},{"full_name":"Pálvölgyi, Dömötör","last_name":"Pálvölgyi","first_name":"Dömötör"}],"quality_controlled":"1","year":"2014","title":"Clustered planarity testing revisited","publication":"International Symposium on Graph Drawing","related_material":{"record":[{"id":"1642","status":"public","relation":"later_version"}]},"_id":"10793","publication_status":"published","abstract":[{"lang":"eng","text":"The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this classical result to clustered graphs with two disjoint clusters, and show that a straightforward extension of our result to flat clustered graphs with three or more disjoint clusters is not possible.\r\n\r\nWe also give a new and short proof for a related result by Di Battista and Frati based on the matroid intersection algorithm."}],"volume":8871,"publisher":"Springer Nature","intvolume":"      8871","place":"Cham","date_created":"2022-02-25T10:32:14Z","month":"01","status":"public","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T10:08:04Z","type":"conference","oa_version":"Preprint","day":"01","language":[{"iso":"eng"}],"doi":"10.1007/978-3-662-45803-7_36","department":[{"_id":"UlWa"}],"date_published":"2014-01-01T00:00:00Z","external_id":{"arxiv":["1305.4519"]},"page":"428-436","alternative_title":["LNCS"],"publication_identifier":{"issn":["0302-9743"]},"scopus_import":"1","arxiv":1},{"status":"public","month":"04","date_created":"2022-03-03T11:52:44Z","place":"Vienna","scopus_import":"1","publication_identifier":{"isbn":["9783709115251"],"eisbn":["9783709115268"]},"editor":[{"full_name":"Zažímalová, Eva","last_name":"Zažímalová","first_name":"Eva"},{"full_name":"Petrášek, Jan","first_name":"Jan","last_name":"Petrášek"},{"first_name":"Eva","last_name":"Benková","full_name":"Benková, Eva","orcid":"0000-0002-8510-9739","id":"38F4F166-F248-11E8-B48F-1D18A9856A87"}],"publisher":"Springer Nature","page":"444","date_published":"2014-04-01T00:00:00Z","abstract":[{"text":"Auxin is an important signaling compound in plants and vital for plant development and growth. The present book, Auxin and its Role in Plant Development, provides the reader with detailed and comprehensive insight into the functioning of the molecule on the whole and specifically in plant development. In the first part, the functioning, metabolism and signaling pathways of auxin in plants are explained, the second part depicts the specific role of auxin in plant development and the third part describes the interaction and functioning of the signaling compound  upon stimuli of the environment. Each chapter is written by international experts in the respective field and designed for scientists and researchers in plant biology, plant development and cell biology to summarize the recent progress in understanding the role of auxin and suggest future perspectives for auxin research.","lang":"eng"}],"publication_status":"published","_id":"10811","department":[{"_id":"EvBe"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-7091-1526-8","edition":"1","title":"Auxin and Its Role in Plant Development","year":"2014","day":"01","oa_version":"None","type":"book_editor","date_updated":"2022-03-04T07:38:15Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","quality_controlled":"1","citation":{"ama":"Zažímalová E, Petrášek J, Benková E, eds. <i>Auxin and Its Role in Plant Development</i>. 1st ed. Vienna: Springer Nature; 2014. doi:<a href=\"https://doi.org/10.1007/978-3-7091-1526-8\">10.1007/978-3-7091-1526-8</a>","ieee":"E. Zažímalová, J. Petrášek, and E. Benková, Eds., <i>Auxin and Its Role in Plant Development</i>, 1st ed. Vienna: Springer Nature, 2014.","ista":"Zažímalová E, Petrášek J, Benková E eds. 2014. Auxin and Its Role in Plant Development 1st ed., Vienna: Springer Nature, 444p.","short":"E. Zažímalová, J. Petrášek, E. Benková, eds., Auxin and Its Role in Plant Development, 1st ed., Springer Nature, Vienna, 2014.","chicago":"Zažímalová, Eva, Jan Petrášek, and Eva Benková, eds. <i>Auxin and Its Role in Plant Development</i>. 1st ed. Vienna: Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-7091-1526-8\">https://doi.org/10.1007/978-3-7091-1526-8</a>.","mla":"Zažímalová, Eva, et al., editors. <i>Auxin and Its Role in Plant Development</i>. 1st ed., Springer Nature, 2014, doi:<a href=\"https://doi.org/10.1007/978-3-7091-1526-8\">10.1007/978-3-7091-1526-8</a>.","apa":"Zažímalová, E., Petrášek, J., &#38; Benková, E. (Eds.). (2014). <i>Auxin and Its Role in Plant Development</i> (1st ed.). Vienna: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-7091-1526-8\">https://doi.org/10.1007/978-3-7091-1526-8</a>"}},{"keyword":["General Medicine"],"date_published":"2014-03-01T00:00:00Z","page":"21-41","volume":116,"article_type":"original","publisher":"Springer Nature","intvolume":"       116","scopus_import":"1","publication_identifier":{"eissn":["1869-7135"],"issn":["0012-0456"]},"month":"03","date_created":"2022-03-04T07:54:39Z","status":"public","citation":{"mla":"Seiringer, Robert. “The Excitation Spectrum for Bose Fluids with Weak Interactions.” <i>Jahresbericht Der Deutschen Mathematiker-Vereinigung</i>, vol. 116, Springer Nature, 2014, pp. 21–41, doi:<a href=\"https://doi.org/10.1365/s13291-014-0083-9\">10.1365/s13291-014-0083-9</a>.","apa":"Seiringer, R. (2014). The excitation spectrum for Bose fluids with weak interactions. <i>Jahresbericht Der Deutschen Mathematiker-Vereinigung</i>. Springer Nature. <a href=\"https://doi.org/10.1365/s13291-014-0083-9\">https://doi.org/10.1365/s13291-014-0083-9</a>","short":"R. Seiringer, Jahresbericht Der Deutschen Mathematiker-Vereinigung 116 (2014) 21–41.","chicago":"Seiringer, Robert. “The Excitation Spectrum for Bose Fluids with Weak Interactions.” <i>Jahresbericht Der Deutschen Mathematiker-Vereinigung</i>. Springer Nature, 2014. <a href=\"https://doi.org/10.1365/s13291-014-0083-9\">https://doi.org/10.1365/s13291-014-0083-9</a>.","ista":"Seiringer R. 2014. The excitation spectrum for Bose fluids with weak interactions. Jahresbericht der Deutschen Mathematiker-Vereinigung. 116, 21–41.","ama":"Seiringer R. The excitation spectrum for Bose fluids with weak interactions. <i>Jahresbericht der Deutschen Mathematiker-Vereinigung</i>. 2014;116:21-41. doi:<a href=\"https://doi.org/10.1365/s13291-014-0083-9\">10.1365/s13291-014-0083-9</a>","ieee":"R. Seiringer, “The excitation spectrum for Bose fluids with weak interactions,” <i>Jahresbericht der Deutschen Mathematiker-Vereinigung</i>, vol. 116. Springer Nature, pp. 21–41, 2014."},"quality_controlled":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Robert","last_name":"Seiringer","full_name":"Seiringer, Robert","orcid":"0000-0002-6781-0521","id":"4AFD0470-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","oa_version":"None","date_updated":"2023-09-05T14:19:47Z","type":"journal_article","year":"2014","day":"01","publication":"Jahresbericht der Deutschen Mathematiker-Vereinigung","title":"The excitation spectrum for Bose fluids with weak interactions","department":[{"_id":"RoSe"}],"_id":"10814","language":[{"iso":"eng"}],"doi":"10.1365/s13291-014-0083-9","abstract":[{"lang":"eng","text":"We review recent progress towards a rigorous understanding of the excitation spectrum of bosonic quantum many-body systems. In particular, we explain how one can rigorously establish the predictions resulting from the Bogoliubov approximation in the mean field limit. The latter predicts that the spectrum is made up of elementary excitations, whose energy behaves linearly in the momentum for small momentum. This property is crucial for the superfluid behavior of the system. We also discuss a list of open problems in this field."}],"publication_status":"published"}]