[{"day":"14","month":"04","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","doi":"10.15479/AT:IST-2014-187-v1-1","date_published":"2014-04-14T00:00:00Z","language":[{"iso":"eng"}],"citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Improved algorithms for reachability and shortest path on low tree-width graphs. IST Austria, 2014.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2014). Improved algorithms for reachability and shortest path on low tree-width graphs. IST Austria. https://doi.org/10.15479/AT:IST-2014-187-v1-1","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs. IST Austria; 2014. doi:10.15479/AT:IST-2014-187-v1-1","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-187-v1-1.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs. IST Austria, 2014, doi:10.15479/AT:IST-2014-187-v1-1."},"oa":1,"page":"34","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"}],"file_date_updated":"2020-07-14T12:46:50Z","type":"technical_report","alternative_title":["IST Austria Technical Report"],"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","first_name":"Rasmus","last_name":"Ibsen-Jensen"},{"full_name":"Pavlogiannis, Andreas","first_name":"Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722"}],"pubrep_id":"187","date_created":"2018-12-12T11:39:13Z","date_updated":"2021-01-12T08:02:03Z","file":[{"relation":"main_file","file_id":"5548","checksum":"c608e66030a4bf51d2d99b451f539b99","date_created":"2018-12-12T11:54:25Z","date_updated":"2020-07-14T12:46:50Z","access_level":"open_access","file_name":"IST-2014-187-v1+1_main_full_tech.pdf","content_type":"application/pdf","file_size":670031,"creator":"system"}],"oa_version":"Published Version","year":"2014","_id":"5419","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Improved algorithms for reachability and shortest path on low tree-width graphs","ddc":["000"],"status":"public","publication_status":"published","department":[{"_id":"KrCh"}],"publisher":"IST Austria"},{"file_date_updated":"2020-07-14T12:46:49Z","abstract":[{"lang":"eng","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."}],"type":"technical_report","alternative_title":["IST Austria Technical Report"],"related_material":{"record":[{"id":"2163","status":"public","relation":"later_version"}]},"pubrep_id":"176","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"}],"oa_version":"Published Version","file":[{"file_name":"IST-2014-176-v1+1_icalp_14.pdf","access_level":"open_access","creator":"system","file_size":328253,"content_type":"application/pdf","file_id":"5468","relation":"main_file","date_created":"2018-12-12T11:53:07Z","date_updated":"2020-07-14T12:46:49Z","checksum":"1d6958aa60050e1c3e932c6e5f34c39f"}],"date_created":"2018-12-12T11:39:13Z","date_updated":"2023-02-23T10:30:58Z","_id":"5418","year":"2014","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"}],"publisher":"IST Austria","title":"Games with a weak adversary","ddc":["000","005"],"publication_status":"published","status":"public","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"month":"03","day":"22","date_published":"2014-03-22T00:00:00Z","doi":"10.15479/AT:IST-2014-176-v1-1","language":[{"iso":"eng"}],"oa":1,"citation":{"ieee":"K. Chatterjee and L. Doyen, Games with a weak adversary. IST Austria, 2014.","apa":"Chatterjee, K., & Doyen, L. (2014). Games with a weak adversary. IST Austria. https://doi.org/10.15479/AT:IST-2014-176-v1-1","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p.","ama":"Chatterjee K, Doyen L. Games with a Weak Adversary. IST Austria; 2014. doi:10.15479/AT:IST-2014-176-v1-1","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. Games with a Weak Adversary. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-176-v1-1.","short":"K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. Games with a Weak Adversary. IST Austria, 2014, doi:10.15479/AT:IST-2014-176-v1-1."},"page":"18"},{"month":"04","day":"14","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","oa":1,"citation":{"mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Value 1 Problem for Concurrent Mean-Payoff Games. IST Austria, 2014, doi:10.15479/AT:IST-2014-191-v1-1.","short":"K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff Games, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Value 1 Problem for Concurrent Mean-Payoff Games. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-191-v1-1.","ama":"Chatterjee K, Ibsen-Jensen R. The Value 1 Problem for Concurrent Mean-Payoff Games. IST Austria; 2014. doi:10.15479/AT:IST-2014-191-v1-1","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p.","apa":"Chatterjee, K., & Ibsen-Jensen, R. (2014). The value 1 problem for concurrent mean-payoff games. IST Austria. https://doi.org/10.15479/AT:IST-2014-191-v1-1","ieee":"K. Chatterjee and R. Ibsen-Jensen, The value 1 problem for concurrent mean-payoff games. IST Austria, 2014."},"page":"49","date_published":"2014-04-14T00:00:00Z","doi":"10.15479/AT:IST-2014-191-v1-1","language":[{"iso":"eng"}],"type":"technical_report","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:50Z","abstract":[{"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).","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5420","year":"2014","status":"public","ddc":["000","005"],"title":"The value 1 problem for concurrent mean-payoff games","publication_status":"published","department":[{"_id":"KrCh"}],"publisher":"IST Austria","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus"}],"pubrep_id":"191","date_updated":"2021-01-12T08:02:05Z","date_created":"2018-12-12T11:39:14Z","file":[{"access_level":"open_access","file_name":"IST-2014-191-v1+1_main_full.pdf","file_size":584368,"content_type":"application/pdf","creator":"system","relation":"main_file","file_id":"5520","checksum":"49e0fd3e62650346daf7dc04604f7a0a","date_created":"2018-12-12T11:53:58Z","date_updated":"2020-07-14T12:46:50Z"}],"oa_version":"Published Version"},{"oa":1,"citation":{"mla":"Chatterjee, Krishnendu, et al. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria, 2014, doi:10.15479/AT:IST-2014-305-v1-1.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-305-v1-1.","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria; 2014. doi:10.15479/AT:IST-2014-305-v1-1","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 12p.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., & Kanodia, A. (2014). Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. IST Austria. https://doi.org/10.15479/AT:IST-2014-305-v1-1","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. IST Austria, 2014."},"page":"12","date_published":"2014-09-09T00:00:00Z","doi":"10.15479/AT:IST-2014-305-v1-1","language":[{"iso":"eng"}],"month":"09","day":"09","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","year":"2014","_id":"5424","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["005"],"publication_status":"published","status":"public","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","department":[{"_id":"KrCh"}],"publisher":"IST Austria","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Gupta, Raghav","first_name":"Raghav","last_name":"Gupta"},{"full_name":"Kanodia, Ayush","first_name":"Ayush","last_name":"Kanodia"}],"pubrep_id":"305","related_material":{"record":[{"id":"1732","relation":"later_version","status":"public"},{"id":"5426","status":"public","relation":"later_version"}]},"date_updated":"2023-02-23T12:25:52Z","date_created":"2018-12-12T11:39:15Z","oa_version":"Published Version","file":[{"checksum":"35009d5fad01198341e6c1a3353481b7","date_updated":"2020-07-14T12:46:51Z","date_created":"2018-12-12T11:53:51Z","file_id":"5512","relation":"main_file","creator":"system","content_type":"application/pdf","file_size":655774,"access_level":"open_access","file_name":"IST-2014-305-v1+1_main.pdf"}],"type":"technical_report","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:51Z","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."}]},{"doi":"10.15479/AT:IST-2014-305-v2-1","date_published":"2014-09-29T00:00:00Z","language":[{"iso":"eng"}],"oa":1,"citation":{"chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-305-v2-1.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria, 2014, doi:10.15479/AT:IST-2014-305-v2-1.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., & Kanodia, A. (2014). Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. IST Austria. https://doi.org/10.15479/AT:IST-2014-305-v2-1","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and 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. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria; 2014. doi:10.15479/AT:IST-2014-305-v2-1"},"page":"10","day":"29","month":"09","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Gupta, Raghav","last_name":"Gupta","first_name":"Raghav"},{"full_name":"Kanodia, Ayush","last_name":"Kanodia","first_name":"Ayush"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"1732"},{"status":"public","relation":"earlier_version","id":"5424"}]},"pubrep_id":"311","date_updated":"2023-02-23T12:25:47Z","date_created":"2018-12-12T11:39:16Z","file":[{"relation":"main_file","file_id":"5537","checksum":"730c0a8e97cf2712a884b2cc423f3919","date_updated":"2020-07-14T12:46:51Z","date_created":"2018-12-12T11:54:15Z","access_level":"open_access","file_name":"IST-2014-305-v2+1_main2.pdf","content_type":"application/pdf","file_size":656019,"creator":"system"}],"oa_version":"Published Version","_id":"5426","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2014","ddc":["005"],"title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","publication_status":"published","status":"public","department":[{"_id":"KrCh"}],"publisher":"IST Austria","abstract":[{"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.","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:51Z","type":"technical_report","alternative_title":["IST Austria Technical Report"]}]