[{"related_material":{"record":[{"id":"2327","relation":"later_version","status":"public"}]},"ddc":["000"],"citation":{"ista":"Henzinger TA, Otop J. 2014. From model checking to model measuring, IST Austria, 14p.","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>","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>.","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.","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>."},"has_accepted_license":"1","abstract":[{"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.","lang":"eng"}],"pubrep_id":"175","title":"From model checking to model measuring","_id":"5417","day":"19","page":"14","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","month":"02","oa":1,"publisher":"IST Austria","date_created":"2018-12-12T11:39:13Z","file":[{"checksum":"fcc3eab903cfcd3778b338d2d0d44d18","date_updated":"2020-07-14T12:46:49Z","content_type":"application/pdf","access_level":"open_access","file_id":"5481","date_created":"2018-12-12T11:53:20Z","creator":"system","relation":"main_file","file_size":383052,"file_name":"IST-2014-172-v1+1_report.pdf"}],"date_published":"2014-02-19T00:00:00Z","date_updated":"2024-10-21T06:02:58Z","year":"2014","department":[{"_id":"ToHe"}],"publication_status":"published","file_date_updated":"2020-07-14T12:46:49Z","publication_identifier":{"issn":["2664-1690"]},"author":[{"orcid":"0000−0002−2985−7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"first_name":"Jan","last_name":"Otop","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"oa_version":"Published Version","doi":"10.15479/AT:IST-2014-172-v1-1","alternative_title":["IST Austria Technical Report"],"language":[{"iso":"eng"}],"status":"public"},{"oa":1,"month":"03","type":"technical_report","page":"18","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"22","_id":"5418","title":"Games with a weak adversary","pubrep_id":"176","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>.","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>","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>.","ieee":"K. Chatterjee and L. Doyen, <i>Games with a weak adversary</i>. IST Austria, 2014.","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p.","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>","short":"K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014."},"has_accepted_license":"1","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"}],"ddc":["000","005"],"related_material":{"record":[{"status":"public","relation":"later_version","id":"2163"}]},"status":"public","language":[{"iso":"eng"}],"alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2014-176-v1-1","oa_version":"Published Version","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Laurent","full_name":"Doyen, Laurent","last_name":"Doyen"}],"publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:49Z","department":[{"_id":"KrCh"}],"publication_status":"published","date_updated":"2025-04-15T07:55:59Z","year":"2014","date_published":"2014-03-22T00:00:00Z","file":[{"checksum":"1d6958aa60050e1c3e932c6e5f34c39f","content_type":"application/pdf","access_level":"open_access","date_updated":"2020-07-14T12:46:49Z","file_id":"5468","date_created":"2018-12-12T11:53:07Z","file_name":"IST-2014-176-v1+1_icalp_14.pdf","file_size":328253,"relation":"main_file","creator":"system"}],"date_created":"2018-12-12T11:39:13Z","publisher":"IST Austria"},{"file":[{"creator":"system","relation":"main_file","file_name":"IST-2014-187-v1+1_main_full_tech.pdf","file_size":670031,"date_created":"2018-12-12T11:54:25Z","date_updated":"2020-07-14T12:46:50Z","content_type":"application/pdf","access_level":"open_access","file_id":"5548","checksum":"c608e66030a4bf51d2d99b451f539b99"}],"date_created":"2018-12-12T11:39:13Z","date_published":"2014-04-14T00:00:00Z","publisher":"IST Austria","doi":"10.15479/AT:IST-2014-187-v1-1","oa_version":"Published Version","alternative_title":["IST Austria Technical Report"],"language":[{"iso":"eng"}],"status":"public","date_updated":"2021-01-12T08:02:03Z","year":"2014","publication_status":"published","department":[{"_id":"KrCh"}],"publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:50Z","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen"},{"orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"title":"Improved algorithms for reachability and shortest path on low tree-width graphs","_id":"5419","day":"14","page":"34","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"has_accepted_license":"1","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"}],"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>.","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>.","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.","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>","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>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014."},"pubrep_id":"187","oa":1,"type":"technical_report","month":"04"},{"file":[{"date_updated":"2020-07-14T12:46:50Z","content_type":"application/pdf","access_level":"open_access","file_id":"5520","checksum":"49e0fd3e62650346daf7dc04604f7a0a","relation":"main_file","creator":"system","file_size":584368,"file_name":"IST-2014-191-v1+1_main_full.pdf","date_created":"2018-12-12T11:53:58Z"}],"date_created":"2018-12-12T11:39:14Z","date_published":"2014-04-14T00:00:00Z","publisher":"IST Austria","doi":"10.15479/AT:IST-2014-191-v1-1","oa_version":"Published Version","status":"public","alternative_title":["IST Austria Technical Report"],"language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"publication_status":"published","date_updated":"2021-01-12T08:02:05Z","year":"2014","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"orcid":"0000-0003-4783-0389","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"file_date_updated":"2020-07-14T12:46:50Z","publication_identifier":{"issn":["2664-1690"]},"_id":"5420","day":"14","title":"The value 1 problem for concurrent mean-payoff games","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"49","ddc":["000","005"],"pubrep_id":"191","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"}],"has_accepted_license":"1","citation":{"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>.","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>","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>.","short":"K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff Games, IST Austria, 2014.","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>","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p."},"oa":1,"month":"04","type":"technical_report"},{"oa":1,"month":"04","type":"technical_report","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","page":"27","_id":"5421","day":"18","title":"The complexity of evolution on graphs","pubrep_id":"190","has_accepted_license":"1","citation":{"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>.","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>","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>.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolution on graphs</i>. IST Austria, 2014.","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>"},"abstract":[{"lang":"eng","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."}],"ddc":["000","005"],"related_material":{"record":[{"status":"public","id":"5432","relation":"later_version"},{"id":"5440","relation":"later_version","status":"public"}]},"status":"public","language":[{"iso":"eng"}],"alternative_title":["IST Austria Technical Report"],"oa_version":"Published Version","doi":"10.15479/AT:IST-2014-190-v2-2","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"}],"file_date_updated":"2020-07-14T12:46:50Z","publication_identifier":{"issn":["2664-1690"]},"department":[{"_id":"KrCh"}],"publication_status":"published","year":"2014","date_updated":"2023-02-23T12:26:33Z","date_published":"2014-04-18T00:00:00Z","file":[{"date_updated":"2020-07-14T12:46:50Z","access_level":"open_access","content_type":"application/pdf","file_id":"5538","checksum":"42f3d8b563286eb0d903832bd9a848d3","creator":"system","relation":"main_file","file_size":443529,"file_name":"IST-2014-190-v2+2_main_full.pdf","date_created":"2018-12-12T11:54:16Z"},{"date_created":"2019-09-06T07:30:20Z","file_size":440911,"file_name":"IST-2014-190-v1+1_main_full.pdf","creator":"kschuh","relation":"main_file","checksum":"0c9a2fd822309719634495a35957e34d","file_id":"6852","access_level":"open_access","content_type":"application/pdf","date_updated":"2020-07-14T12:46:50Z"}],"date_created":"2018-12-12T11:39:14Z","publisher":"IST Austria"},{"oa":1,"type":"report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5422","title":"Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland","pubrep_id":"254","abstract":[{"lang":"eng","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."}],"citation":{"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.","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.","chicago":"Porsche, Jana. <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.","mla":"Porsche, Jana. <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none, 2014."},"has_accepted_license":"1","ddc":["020"],"status":"public","language":[{"iso":"eng"}],"oa_version":"None","author":[{"full_name":"Porsche, Jana","id":"3252EDC2-F248-11E8-B48F-1D18A9856A87","first_name":"Jana","last_name":"Porsche"}],"file_date_updated":"2020-07-14T12:46:50Z","department":[{"_id":"E-Lib"}],"year":"2014","date_updated":"2020-07-14T23:04:56Z","date_published":"2014-01-01T00:00:00Z","file":[{"checksum":"3954896648ce8afa8f7c4425e71cff08","access_level":"open_access","content_type":"application/pdf","date_updated":"2020-07-14T12:46:50Z","file_id":"5501","date_created":"2018-12-12T11:53:40Z","file_size":648585,"file_name":"IST-2014-254-v1+1_Dublin_Day_3.pdf","relation":"main_file","creator":"system"},{"creator":"system","relation":"main_file","file_name":"IST-2014-254-v1+2_Dublin_Day_1.pdf","file_size":221339,"date_created":"2018-12-12T11:53:41Z","file_id":"5502","date_updated":"2020-07-14T12:46:50Z","access_level":"open_access","content_type":"application/pdf","checksum":"9a0d42b0b832dfe7e4b22fb6816bcbba"},{"checksum":"498b8d629fb1bd17bff1dc43700a93e6","access_level":"open_access","content_type":"application/pdf","date_updated":"2020-07-14T12:46:50Z","file_id":"5503","date_created":"2018-12-12T11:53:42Z","file_size":187778,"file_name":"IST-2014-254-v1+3_Dublin_Day_2.pdf","creator":"system","relation":"main_file"}],"date_created":"2018-12-12T11:39:14Z","publisher":"none"},{"pubrep_id":"300","has_accepted_license":"1","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":{"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.","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.","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>","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.","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>.","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>."},"ddc":["005"],"related_material":{"record":[{"status":"public","id":"1714","relation":"later_version"}]},"page":"14","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"29","_id":"5423","title":"A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks","month":"07","type":"technical_report","oa":1,"publisher":"IST Austria","date_published":"2014-07-29T00:00:00Z","date_created":"2018-12-12T11:39:15Z","file":[{"checksum":"4b8fde4d9ef6653837f6803921d83032","date_updated":"2020-07-14T12:46:50Z","content_type":"application/pdf","access_level":"open_access","file_id":"5514","date_created":"2018-12-12T11:53:53Z","relation":"main_file","creator":"system","file_size":1270021,"file_name":"IST-2014-300-v1+1_main.pdf"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Alexander","last_name":"Kössler","full_name":"Kössler, Alexander"},{"first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722"},{"last_name":"Schmid","first_name":"Ulrich","full_name":"Schmid, Ulrich"}],"publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:50Z","department":[{"_id":"KrCh"}],"publication_status":"published","date_updated":"2025-09-29T13:15:35Z","year":"2014","status":"public","language":[{"iso":"eng"}],"alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2014-300-v1-1","oa_version":"Published Version"},{"page":"12","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","day":"09","_id":"5424","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."}],"has_accepted_license":"1","citation":{"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>","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 12p.","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. <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>.","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>","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>."},"pubrep_id":"305","related_material":{"record":[{"status":"public","id":"5426","relation":"later_version"},{"relation":"later_version","id":"1732","status":"public"}]},"ddc":["005"],"oa":1,"type":"technical_report","month":"09","date_published":"2014-09-09T00:00:00Z","file":[{"access_level":"open_access","content_type":"application/pdf","date_updated":"2020-07-14T12:46:51Z","file_id":"5512","checksum":"35009d5fad01198341e6c1a3353481b7","file_name":"IST-2014-305-v1+1_main.pdf","file_size":655774,"creator":"system","relation":"main_file","date_created":"2018-12-12T11:53:51Z"}],"date_created":"2018-12-12T11:39:15Z","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"language":[{"iso":"eng"}],"status":"public","oa_version":"Published Version","doi":"10.15479/AT:IST-2014-305-v1-1","file_date_updated":"2020-07-14T12:46:51Z","publication_identifier":{"issn":["2664-1690"]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Gupta, Raghav","first_name":"Raghav","last_name":"Gupta"},{"first_name":"Ayush","last_name":"Kanodia","full_name":"Kanodia, Ayush"}],"date_updated":"2025-04-15T07:55:41Z","year":"2014","department":[{"_id":"KrCh"}],"publication_status":"published"},{"type":"technical_report","month":"09","oa":1,"related_material":{"record":[{"status":"public","relation":"later_version","id":"1529"}]},"ddc":["000"],"abstract":[{"lang":"eng","text":" We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objective we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest."}],"has_accepted_license":"1","citation":{"short":"1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Optimal Cost Almost-Sure Reachability in POMDPs, IST Austria, 2014.","ista":"Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2014. Optimal cost almost-sure reachability in POMDPs, IST Austria, 22p.","apa":"Anonymous, 1, Anonymous, 2, Anonymous, 3, &#38; Anonymous, 4. (2014). <i>Optimal cost almost-sure reachability in POMDPs</i>. IST Austria.","mla":"Anonymous, 1, et al. <i>Optimal Cost Almost-Sure Reachability in POMDPs</i>. IST Austria, 2014.","ieee":"1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, <i>Optimal cost almost-sure reachability in POMDPs</i>. IST Austria, 2014.","ama":"Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. <i>Optimal Cost Almost-Sure Reachability in POMDPs</i>. IST Austria; 2014.","chicago":"Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. <i>Optimal Cost Almost-Sure Reachability in POMDPs</i>. IST Austria, 2014."},"pubrep_id":"307","title":"Optimal cost almost-sure reachability in POMDPs","day":"09","_id":"5425","page":"22","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-09-18T11:05:08Z","year":"2014","publication_status":"published","file_date_updated":"2020-07-14T12:46:51Z","publication_identifier":{"issn":["2664-1690"]},"author":[{"full_name":"Anonymous, 1","first_name":"1","last_name":"Anonymous"},{"last_name":"Anonymous","full_name":"Anonymous, 2","first_name":"2"},{"first_name":"3","last_name":"Anonymous","full_name":"Anonymous, 3"},{"full_name":"Anonymous, 4","first_name":"4","last_name":"Anonymous"}],"oa_version":"Published Version","scopus_import":1,"alternative_title":["IST Austria Technical Report"],"language":[{"iso":"eng"}],"status":"public","publisher":"IST Austria","file":[{"relation":"main_file","creator":"system","file_name":"IST-2014-307-v1+1_main.pdf","file_size":2725429,"date_created":"2018-12-12T11:53:17Z","file_id":"5478","date_updated":"2020-07-14T12:46:51Z","content_type":"application/pdf","access_level":"open_access","checksum":"b9668a70d53c550b3cd64f0c77451c3d"},{"file_id":"6322","access_level":"closed","content_type":"text/plain","date_updated":"2020-07-14T12:46:51Z","checksum":"808ada1dddecc48ca041526fcc6a9efd","file_size":117,"file_name":"IST-2014-307-v1+2_authors.txt","creator":"dernst","relation":"main_file","date_created":"2019-04-16T14:16:12Z"}],"date_created":"2018-12-12T11:39:15Z","date_published":"2014-09-09T00:00:00Z"},{"oa_version":"Published Version","doi":"10.15479/AT:IST-2014-305-v2-1","alternative_title":["IST Austria Technical Report"],"language":[{"iso":"eng"}],"status":"public","date_updated":"2025-04-15T07:55:41Z","year":"2014","department":[{"_id":"KrCh"}],"publication_status":"published","file_date_updated":"2020-07-14T12:46:51Z","publication_identifier":{"issn":["2664-1690"]},"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin"},{"last_name":"Gupta","first_name":"Raghav","full_name":"Gupta, Raghav"},{"last_name":"Kanodia","full_name":"Kanodia, Ayush","first_name":"Ayush"}],"date_created":"2018-12-12T11:39:16Z","file":[{"file_id":"5537","date_updated":"2020-07-14T12:46:51Z","content_type":"application/pdf","access_level":"open_access","checksum":"730c0a8e97cf2712a884b2cc423f3919","creator":"system","relation":"main_file","file_name":"IST-2014-305-v2+1_main2.pdf","file_size":656019,"date_created":"2018-12-12T11:54:15Z"}],"date_published":"2014-09-29T00:00:00Z","publisher":"IST Austria","oa":1,"type":"technical_report","month":"09","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","_id":"5426","day":"29","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"10","related_material":{"record":[{"id":"5424","relation":"earlier_version","status":"public"},{"status":"public","id":"1732","relation":"later_version"}]},"ddc":["005"],"has_accepted_license":"1","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"}],"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>.","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-v2-1\">10.15479/AT:IST-2014-305-v2-1</a>","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>.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014.","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>","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 10p."},"pubrep_id":"311"},{"publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:52Z","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas"}],"year":"2014","date_updated":"2021-01-12T08:02:09Z","publication_status":"published","department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"alternative_title":["IST Austria Technical Report"],"status":"public","doi":"10.15479/AT:IST-2014-314-v1-1","oa_version":"Published Version","publisher":"IST Austria","date_published":"2014-11-05T00:00:00Z","file":[{"date_updated":"2020-07-14T12:46:52Z","content_type":"application/pdf","access_level":"open_access","file_id":"5471","checksum":"9d3b90bf4fff74664f182f2d95ef727a","relation":"main_file","creator":"system","file_size":405561,"file_name":"IST-2014-314-v1+1_long.pdf","date_created":"2018-12-12T11:53:10Z"}],"date_created":"2018-12-12T11:39:16Z","type":"technical_report","month":"11","oa":1,"citation":{"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>.","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>.","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>","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>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Optimal tree-decomposition balancing and reachability on low treewidth graphs, IST Austria, 24p.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs, IST Austria, 2014."},"has_accepted_license":"1","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"}],"pubrep_id":"314","ddc":["000"],"page":"24","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Optimal tree-decomposition balancing and reachability on low treewidth graphs","day":"05","_id":"5427"},{"oa_version":"Published Version","doi":"10.15479/AT:IST-2014-315-v1-1","alternative_title":["IST Austria Technical Report"],"language":[{"iso":"eng"}],"status":"public","year":"2014","date_updated":"2026-06-18T08:47:00Z","publication_status":"published","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:52Z","publication_identifier":{"issn":["2664-1690"]},"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724"},{"full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","last_name":"Otop","first_name":"Jan"},{"last_name":"Velner","first_name":"Yaron","full_name":"Velner, Yaron"}],"date_created":"2018-12-12T11:39:16Z","file":[{"file_id":"5521","date_updated":"2020-07-14T12:46:52Z","content_type":"application/pdf","access_level":"open_access","checksum":"b1d573bc04365625ff9974880c0aa807","creator":"system","relation":"main_file","file_name":"IST-2014-315-v1+1_report.pdf","file_size":531046,"date_created":"2018-12-12T11:53:59Z"}],"date_published":"2014-12-05T00:00:00Z","publisher":"IST Austria","oa":1,"type":"technical_report","month":"12","title":"Quantitative fair simulation games","day":"05","_id":"5428","page":"26","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","relation":"later_version","id":"1066"}]},"ddc":["004"],"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."}],"citation":{"ista":"Chatterjee K, Henzinger TA, Otop J, Velner Y. 2014. Quantitative fair simulation games, IST Austria, 26p.","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>","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Quantitative Fair Simulation Games, 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>","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and Y. Velner, <i>Quantitative fair simulation games</i>. 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>.","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>."},"has_accepted_license":"1","pubrep_id":"315"},{"date_created":"2019-03-26T08:55:59Z","series_title":"MIMB","date_published":"2014-08-22T00:00:00Z","place":"New York","external_id":{"pmid":["25245697"]},"oa_version":"None","doi":"10.1007/978-1-4939-1164-6_15","quality_controlled":"1","language":[{"iso":"eng"}],"alternative_title":["Methods in Molecular Biology"],"status":"public","year":"2014","date_updated":"2026-04-16T10:31:19Z","publication":"Tissue Morphogenesis","publication_identifier":{"eisbn":["9781493911646"],"issn":["1064-3745"],"eissn":["1940-6029"],"isbn":["9781493911639"]},"author":[{"id":"3FE6E4E8-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","full_name":"Smutny, Michael","last_name":"Smutny","orcid":"0000-0002-5920-9090"},{"last_name":"Behrndt","id":"3ECECA3A-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","full_name":"Behrndt, Martin"},{"last_name":"Campinho","full_name":"Campinho, Pedro","first_name":"Pedro","id":"3AFBBC42-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8526-5416"},{"last_name":"Ruprecht","id":"4D71A03A-F248-11E8-B48F-1D18A9856A87","first_name":"Verena","full_name":"Ruprecht, Verena","orcid":"0000-0003-4088-8633"},{"orcid":"0000-0002-0912-4566","id":"39427864-F248-11E8-B48F-1D18A9856A87","full_name":"Heisenberg, Carl-Philipp J","first_name":"Carl-Philipp J","last_name":"Heisenberg"}],"title":"UV laser ablation to measure cell and tissue-generated forces in the zebrafish embryo in vivo and ex vivo","_id":"6178","corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","editor":[{"full_name":"Nelson, Celeste","last_name":"Nelson","first_name":"Celeste"}],"volume":1189,"type":"book_chapter","intvolume":"      1189","publisher":"Springer","article_processing_charge":"No","department":[{"_id":"CaHe"}],"publication_status":"published","day":"22","pmid":1,"page":"219-235","citation":{"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. Methods in Molecular Biology, vol. 1189, 219–235.","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: 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>","short":"M. Smutny, M. Behrndt, P. Campinho, V. Ruprecht, C.-P.J. Heisenberg, in:, C. Nelson (Ed.), Tissue Morphogenesis, Springer, New York, 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. MIMB. New York: 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>.","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: 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. MIMB. New York: 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>","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>."},"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."}],"month":"08"},{"isi":1,"volume":24,"type":"journal_article","project":[{"_id":"25716A02-B435-11E9-9278-68D0E5697425","grant_number":"282300","name":"Polarity and subcellular dynamics in plants","call_identifier":"FP7"}],"_id":"1994","title":"Directional auxin transport mechanisms in early diverging land plants","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","year":"2014","date_updated":"2025-09-29T12:07:20Z","author":[{"full_name":"Viaene, Tom","first_name":"Tom","last_name":"Viaene"},{"full_name":"Landberg, Katarina","last_name":"Landberg","first_name":"Katarina"},{"last_name":"Thelander","full_name":"Thelander, Mattias","first_name":"Mattias"},{"first_name":"Eva","full_name":"Medvecka, Eva","last_name":"Medvecka"},{"full_name":"Pederson, Eric","first_name":"Eric","last_name":"Pederson"},{"full_name":"Feraru, Elena","last_name":"Feraru","first_name":"Elena"},{"last_name":"Cooper","first_name":"Endymion","full_name":"Cooper, Endymion"},{"last_name":"Karimi","first_name":"Mansour","full_name":"Karimi, Mansour"},{"full_name":"Delwiche, Charles","first_name":"Charles","last_name":"Delwiche"},{"last_name":"Ljung","first_name":"Karin","full_name":"Ljung, Karin"},{"first_name":"Markus","last_name":"Geisler","full_name":"Geisler, Markus"},{"full_name":"Sundberg, Eva","first_name":"Eva","last_name":"Sundberg"},{"orcid":"0000-0002-8302-7596","full_name":"Friml, Jirí","id":"4159519E-F248-11E8-B48F-1D18A9856A87","last_name":"Friml","first_name":"Jirí"}],"publist_id":"5088","publication":"Current Biology","quality_controlled":"1","doi":"10.1016/j.cub.2014.09.056","oa_version":"None","issue":"23","status":"public","language":[{"iso":"eng"}],"external_id":{"isi":["000345808700019"]},"date_created":"2018-12-11T11:55:06Z","date_published":"2014-12-01T00:00:00Z","ec_funded":1,"month":"12","citation":{"chicago":"Viaene, Tom, Katarina Landberg, Mattias Thelander, Eva Medvecka, Eric Pederson, Elena Feraru, Endymion Cooper, et al. “Directional Auxin Transport Mechanisms in Early Diverging Land Plants.” <i>Current Biology</i>. Cell Press, 2014. <a href=\"https://doi.org/10.1016/j.cub.2014.09.056\">https://doi.org/10.1016/j.cub.2014.09.056</a>.","ama":"Viaene T, Landberg K, Thelander M, et al. Directional auxin transport mechanisms in early diverging land plants. <i>Current Biology</i>. 2014;24(23):2786-2791. doi:<a href=\"https://doi.org/10.1016/j.cub.2014.09.056\">10.1016/j.cub.2014.09.056</a>","ieee":"T. Viaene <i>et al.</i>, “Directional auxin transport mechanisms in early diverging land plants,” <i>Current Biology</i>, vol. 24, no. 23. Cell Press, pp. 2786–2791, 2014.","mla":"Viaene, Tom, et al. “Directional Auxin Transport Mechanisms in Early Diverging Land Plants.” <i>Current Biology</i>, vol. 24, no. 23, Cell Press, 2014, pp. 2786–91, doi:<a href=\"https://doi.org/10.1016/j.cub.2014.09.056\">10.1016/j.cub.2014.09.056</a>.","ista":"Viaene T, Landberg K, Thelander M, Medvecka E, Pederson E, Feraru E, Cooper E, Karimi M, Delwiche C, Ljung K, Geisler M, Sundberg E, Friml J. 2014. Directional auxin transport mechanisms in early diverging land plants. Current Biology. 24(23), 2786–2791.","apa":"Viaene, T., Landberg, K., Thelander, M., Medvecka, E., Pederson, E., Feraru, E., … Friml, J. (2014). Directional auxin transport mechanisms in early diverging land plants. <i>Current Biology</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.cub.2014.09.056\">https://doi.org/10.1016/j.cub.2014.09.056</a>","short":"T. Viaene, K. Landberg, M. Thelander, E. Medvecka, E. Pederson, E. Feraru, E. Cooper, M. Karimi, C. Delwiche, K. Ljung, M. Geisler, E. Sundberg, J. Friml, Current Biology 24 (2014) 2786–2791."},"abstract":[{"text":"The emergence and radiation of multicellular land plants was driven by crucial innovations to their body plans [1]. The directional transport of the phytohormone auxin represents a key, plant-specific mechanism for polarization and patterning in complex seed plants [2-5]. Here, we show that already in the early diverging land plant lineage, as exemplified by the moss Physcomitrella patens, auxin transport by PIN transporters is operational and diversified into ER-localized and plasma membrane-localized PIN proteins. Gain-of-function and loss-of-function analyses revealed that PIN-dependent intercellular auxin transport in Physcomitrella mediates crucial developmental transitions in tip-growing filaments and waves of polarization and differentiation in leaf-like structures. Plasma membrane PIN proteins localize in a polar manner to the tips of moss filaments, revealing an unexpected relation between polarization mechanisms in moss tip-growing cells and multicellular tissues of seed plants. Our results trace the origins of polarization and auxin-mediated patterning mechanisms and highlight the crucial role of polarized auxin transport during the evolution of multicellular land plants.","lang":"eng"}],"day":"01","page":"2786 - 2791","publication_status":"published","department":[{"_id":"JiFr"}],"scopus_import":"1","article_processing_charge":"No","intvolume":"        24","publisher":"Cell Press"},{"external_id":{"isi":["000346049700005"],"arxiv":["1410.5972"]},"date_created":"2018-12-11T11:55:06Z","ec_funded":1,"date_published":"2014-12-08T00:00:00Z","date_updated":"2025-09-29T12:06:45Z","year":"2014","publist_id":"5085","publication":"Physical Review Letters","author":[{"full_name":"Fratini, Filippo","last_name":"Fratini","first_name":"Filippo"},{"last_name":"Mascarenhas","full_name":"Mascarenhas, Eduardo","first_name":"Eduardo"},{"full_name":"Safari, Laleh","first_name":"Laleh","id":"3C325E5E-F248-11E8-B48F-1D18A9856A87","last_name":"Safari"},{"first_name":"Jean","full_name":"Poizat, Jean","last_name":"Poizat"},{"last_name":"Valente","full_name":"Valente, Daniel","first_name":"Daniel"},{"last_name":"Auffèves","first_name":"Alexia","full_name":"Auffèves, Alexia"},{"last_name":"Gerace","first_name":"Dario","full_name":"Gerace, Dario"},{"first_name":"Marcelo","full_name":"Santos, Marcelo","last_name":"Santos"}],"doi":"10.1103/PhysRevLett.113.243601","oa_version":"Submitted Version","quality_controlled":"1","language":[{"iso":"eng"}],"issue":"24","status":"public","title":"Fabry-Perot interferometer with quantum mirrors: Nonlinear light transport and rectification","_id":"1995","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","volume":113,"type":"journal_article","isi":1,"project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"arxiv":1,"intvolume":"       113","publisher":"American Physical Society","publication_status":"published","department":[{"_id":"MiLe"}],"article_number":"243601","scopus_import":"1","article_processing_charge":"No","citation":{"mla":"Fratini, Filippo, et al. “Fabry-Perot Interferometer with Quantum Mirrors: Nonlinear Light Transport and Rectification.” <i>Physical Review Letters</i>, vol. 113, no. 24, 243601, American Physical Society, 2014, doi:<a href=\"https://doi.org/10.1103/PhysRevLett.113.243601\">10.1103/PhysRevLett.113.243601</a>.","chicago":"Fratini, Filippo, Eduardo Mascarenhas, Laleh Safari, Jean Poizat, Daniel Valente, Alexia Auffèves, Dario Gerace, and Marcelo Santos. “Fabry-Perot Interferometer with Quantum Mirrors: Nonlinear Light Transport and Rectification.” <i>Physical Review Letters</i>. American Physical Society, 2014. <a href=\"https://doi.org/10.1103/PhysRevLett.113.243601\">https://doi.org/10.1103/PhysRevLett.113.243601</a>.","ieee":"F. Fratini <i>et al.</i>, “Fabry-Perot interferometer with quantum mirrors: Nonlinear light transport and rectification,” <i>Physical Review Letters</i>, vol. 113, no. 24. American Physical Society, 2014.","ama":"Fratini F, Mascarenhas E, Safari L, et al. Fabry-Perot interferometer with quantum mirrors: Nonlinear light transport and rectification. <i>Physical Review Letters</i>. 2014;113(24). doi:<a href=\"https://doi.org/10.1103/PhysRevLett.113.243601\">10.1103/PhysRevLett.113.243601</a>","ista":"Fratini F, Mascarenhas E, Safari L, Poizat J, Valente D, Auffèves A, Gerace D, Santos M. 2014. Fabry-Perot interferometer with quantum mirrors: Nonlinear light transport and rectification. Physical Review Letters. 113(24), 243601.","apa":"Fratini, F., Mascarenhas, E., Safari, L., Poizat, J., Valente, D., Auffèves, A., … Santos, M. (2014). Fabry-Perot interferometer with quantum mirrors: Nonlinear light transport and rectification. <i>Physical Review Letters</i>. American Physical Society. <a href=\"https://doi.org/10.1103/PhysRevLett.113.243601\">https://doi.org/10.1103/PhysRevLett.113.243601</a>","short":"F. Fratini, E. Mascarenhas, L. Safari, J. Poizat, D. Valente, A. Auffèves, D. Gerace, M. Santos, Physical Review Letters 113 (2014)."},"abstract":[{"text":"Optical transport represents a natural route towards fast communications, and it is currently used in large scale data transfer. The progressive miniaturization of devices for information processing calls for the microscopic tailoring of light transport and confinement at length scales appropriate for upcoming technologies. With this goal in mind, we present a theoretical analysis of a one-dimensional Fabry-Perot interferometer built with two highly saturable nonlinear mirrors: a pair of two-level systems. Our approach captures nonlinear and nonreciprocal effects of light transport that were not reported previously. Remarkably, we show that such an elementary device can operate as a microscopic integrated optical rectifier.","lang":"eng"}],"day":"08","month":"12","main_file_link":[{"url":"http://arxiv.org/abs/1410.5972","open_access":"1"}],"oa":1},{"article_processing_charge":"No","scopus_import":"1","publication_status":"published","department":[{"_id":"JiFr"}],"publisher":"National Academy of Sciences","intvolume":"       111","oa":1,"main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4273421/","open_access":"1"}],"month":"12","page":"E5471 - E5479","day":"16","abstract":[{"text":"Auxin polar transport, local maxima, and gradients have become an importantmodel system for studying self-organization. Auxin distribution is regulated by auxin-dependent positive feedback loops that are not well-understood at the molecular level. Previously, we showed the involvement of the RHO of Plants (ROP) effector INTERACTOR of CONSTITUTIVELY active ROP 1 (ICR1) in regulation of auxin transport and that ICR1 levels are posttranscriptionally repressed at the site of maximum auxin accumulation at the root tip. Here, we show that bimodal regulation of ICR1 levels by auxin is essential for regulating formation of auxin local maxima and gradients. ICR1 levels increase concomitant with increase in auxin response in lateral root primordia, cotyledon tips, and provascular tissues. However, in the embryo hypophysis and root meristem, when auxin exceeds critical levels, ICR1 is rapidly destabilized by an SCF(TIR1/AFB) [SKP, Cullin, F-box (transport inhibitor response 1/auxin signaling F-box protein)]-dependent auxin signaling mechanism. Furthermore, ectopic expression of ICR1 in the embryo hypophysis resulted in reduction of auxin accumulation and concomitant root growth arrest. ICR1 disappeared during root regeneration and lateral root initiation concomitantly with the formation of a local auxin maximum in response to external auxin treatments and transiently after gravitropic stimulation. Destabilization of ICR1 was impaired after inhibition of auxin transport and signaling, proteasome function, and protein synthesis. A mathematical model based on these findings shows that an in vivo-like auxin distribution, rootward auxin flux, and shootward reflux can be simulated without assuming preexisting tissue polarity. Our experimental results and mathematical modeling indicate that regulation of auxin distribution is tightly associated with auxin-dependent ICR1 levels.","lang":"eng"}],"citation":{"ista":"Hazak O, Obolski U, Prat T, Friml J, Hadany L, Yalovsky S. 2014. Bimodal regulation of ICR1 levels generates self-organizing auxin distribution. PNAS. 111(50), E5471–E5479.","apa":"Hazak, O., Obolski, U., Prat, T., Friml, J., Hadany, L., &#38; Yalovsky, S. (2014). Bimodal regulation of ICR1 levels generates self-organizing auxin distribution. <i>PNAS</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.1413918111\">https://doi.org/10.1073/pnas.1413918111</a>","short":"O. Hazak, U. Obolski, T. Prat, J. Friml, L. Hadany, S. Yalovsky, PNAS 111 (2014) E5471–E5479.","mla":"Hazak, Ora, et al. “Bimodal Regulation of ICR1 Levels Generates Self-Organizing Auxin Distribution.” <i>PNAS</i>, vol. 111, no. 50, National Academy of Sciences, 2014, pp. E5471–79, doi:<a href=\"https://doi.org/10.1073/pnas.1413918111\">10.1073/pnas.1413918111</a>.","ieee":"O. Hazak, U. Obolski, T. Prat, J. Friml, L. Hadany, and S. Yalovsky, “Bimodal regulation of ICR1 levels generates self-organizing auxin distribution,” <i>PNAS</i>, vol. 111, no. 50. National Academy of Sciences, pp. E5471–E5479, 2014.","chicago":"Hazak, Ora, Uri Obolski, Tomas Prat, Jiří Friml, Lilach Hadany, and Shaul Yalovsky. “Bimodal Regulation of ICR1 Levels Generates Self-Organizing Auxin Distribution.” <i>PNAS</i>. National Academy of Sciences, 2014. <a href=\"https://doi.org/10.1073/pnas.1413918111\">https://doi.org/10.1073/pnas.1413918111</a>.","ama":"Hazak O, Obolski U, Prat T, Friml J, Hadany L, Yalovsky S. Bimodal regulation of ICR1 levels generates self-organizing auxin distribution. <i>PNAS</i>. 2014;111(50):E5471-E5479. doi:<a href=\"https://doi.org/10.1073/pnas.1413918111\">10.1073/pnas.1413918111</a>"},"status":"public","issue":"50","language":[{"iso":"eng"}],"quality_controlled":"1","doi":"10.1073/pnas.1413918111","oa_version":"Submitted Version","author":[{"first_name":"Ora","full_name":"Hazak, Ora","last_name":"Hazak"},{"last_name":"Obolski","first_name":"Uri","full_name":"Obolski, Uri"},{"id":"3DA3BFEE-F248-11E8-B48F-1D18A9856A87","full_name":"Prat, Tomas","first_name":"Tomas","last_name":"Prat"},{"orcid":"0000-0002-8302-7596","first_name":"Jiří","id":"4159519E-F248-11E8-B48F-1D18A9856A87","last_name":"Friml","full_name":"Friml, Jiří"},{"last_name":"Hadany","first_name":"Lilach","full_name":"Hadany, Lilach"},{"full_name":"Yalovsky, Shaul","last_name":"Yalovsky","first_name":"Shaul"}],"publication":"PNAS","publist_id":"5083","year":"2014","date_updated":"2025-09-29T12:06:13Z","date_published":"2014-12-16T00:00:00Z","date_created":"2018-12-11T11:55:07Z","external_id":{"isi":["000346366500020"]},"isi":1,"volume":111,"type":"journal_article","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"1996","title":"Bimodal regulation of ICR1 levels generates self-organizing auxin distribution"},{"intvolume":"        35","publisher":"Elsevier","scopus_import":"1","article_processing_charge":"No","department":[{"_id":"SyCr"}],"publication_status":"published","day":"01","page":"471 - 482","abstract":[{"text":"Immune systems are able to protect the body against secondary infection with the same parasite. In insect colonies, this protection is not restricted to the level of the individual organism, but also occurs at the societal level. Here, we review recent evidence for and insights into the mechanisms underlying individual and social immunisation in insects. We disentangle general immune-protective effects from specific immune memory (priming), and examine immunisation in the context of the lifetime of an individual and that of a colony, and of transgenerational immunisation that benefits offspring. When appropriate, we discuss parallels with disease defence strategies in human societies. We propose that recurrent parasitic threats have shaped the evolution of both the individual immune systems and colony-level social immunity in insects.","lang":"eng"}],"citation":{"ista":"El Masri L, Cremer S. 2014. Individual and social immunisation in insects. Trends in Immunology. 35(10), 471–482.","apa":"El Masri, L., &#38; Cremer, S. (2014). Individual and social immunisation in insects. <i>Trends in Immunology</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.it.2014.08.005\">https://doi.org/10.1016/j.it.2014.08.005</a>","short":"L. El Masri, S. Cremer, Trends in Immunology 35 (2014) 471–482.","mla":"El Masri, Leila, and Sylvia Cremer. “Individual and Social Immunisation in Insects.” <i>Trends in Immunology</i>, vol. 35, no. 10, Elsevier, 2014, pp. 471–82, doi:<a href=\"https://doi.org/10.1016/j.it.2014.08.005\">10.1016/j.it.2014.08.005</a>.","chicago":"El Masri, Leila, and Sylvia Cremer. “Individual and Social Immunisation in Insects.” <i>Trends in Immunology</i>. Elsevier, 2014. <a href=\"https://doi.org/10.1016/j.it.2014.08.005\">https://doi.org/10.1016/j.it.2014.08.005</a>.","ieee":"L. El Masri and S. Cremer, “Individual and social immunisation in insects,” <i>Trends in Immunology</i>, vol. 35, no. 10. Elsevier, pp. 471–482, 2014.","ama":"El Masri L, Cremer S. Individual and social immunisation in insects. <i>Trends in Immunology</i>. 2014;35(10):471-482. doi:<a href=\"https://doi.org/10.1016/j.it.2014.08.005\">10.1016/j.it.2014.08.005</a>"},"month":"10","date_created":"2018-12-11T11:55:07Z","date_published":"2014-10-01T00:00:00Z","external_id":{"isi":["000343632600006"]},"doi":"10.1016/j.it.2014.08.005","oa_version":"None","quality_controlled":"1","language":[{"iso":"eng"}],"status":"public","issue":"10","date_updated":"2025-09-29T12:05:29Z","year":"2014","publication":"Trends in Immunology","publist_id":"5081","author":[{"full_name":"El Masri, Leila","first_name":"Leila","last_name":"El Masri","id":"349A6E66-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Sylvia","full_name":"Cremer, Sylvia","last_name":"Cremer","id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2193-3868"}],"title":"Individual and social immunisation in insects","_id":"1998","corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","volume":35,"acknowledgement":"This work was funded by an ERC Starting Grant by the European Research Council (to S.C.) and the ISTFELLOW program (Co-fund Marie Curie Actions of the European Commission; to L.M.).\r\nWe thank Christopher D. Pull, Sophie A.O. Armitage, Hinrich Schulenburg, Line V. Ugelvig, Matthias Konrad, Matthias Fürst, Miriam Stock, Barbara Casillas-Perez and three anonymous referees for comments on the manuscript. ","type":"journal_article","isi":1},{"intvolume":"        12","publisher":"Springer Nature","series_title":"NEUROSCI","date_created":"2025-07-10T14:06:05Z","date_published":"2014-10-30T00:00:00Z","OA_type":"closed access","publication_status":"published","department":[{"_id":"JoCs"}],"date_updated":"2025-09-23T09:36:44Z","year":"2014","author":[{"full_name":"Dupret, David","last_name":"Dupret","first_name":"David"},{"last_name":"Csicsvari","id":"3FA14672-F248-11E8-B48F-1D18A9856A87","full_name":"Csicsvari, Jozsef L","first_name":"Jozsef L","orcid":"0000-0002-5193-4036"}],"publication":"Analysis and Modeling of Coordinated Multi-neuronal Activity","publication_identifier":{"isbn":["9781493919680"],"eissn":["2197-1919"],"eisbn":["9781493919697"],"issn":["2197-1900"]},"scopus_import":"1","quality_controlled":"1","oa_version":"None","doi":"10.1007/978-1-4939-1969-7_6","article_processing_charge":"No","status":"public","language":[{"iso":"eng"}],"alternative_title":["Springer Series in Computational Neuroscience"],"abstract":[{"lang":"eng","text":"Firing patterns of hippocampal principal cells are thought to participate in the formation of mnemonic representations of place, which ultimately can be used to guide the behavior of animals in space. Past studies have suggested that place-selective activity in the hippocampus can emphasize the representation of discrete locations associated with a strong behavioral salience. In the first part of this book chapter, we review work that has described how that hippocampal neuronal activity patterns reorganize during spatial learning. These studies revealed that new hippocampal maps emerge during spatial learning to represent the location of goal locations and demonstrated that, during recall, the reinstatement of these maps predicts successful memory performance. In the second part of this chapter, we discuss the role of sleep in memory consolidation in the context of goal-oriented spatial learning. We summarize work that has demonstrated the replay of goal-oriented neuronal assembly patterns that predict subsequent memory recall. Moreover, we argue that the initial strengthening of new maps may in fact take place during learning, triggered by waking sharp-wave/ripple patterns occurring at goal locations. These reviewed studies highlight that the reorganization and replay of place cell firing patterns might constitute a circuit signature for the expression of newly acquired hippocampal engrams."}],"citation":{"mla":"Dupret, David, and Jozsef L. Csicsvari. “Reorganization of Hippocampal Place-Selective Patterns During Goal-Directed Learning and Their Reactivation During Sleep.” <i>Analysis and Modeling of Coordinated Multi-Neuronal Activity</i>, vol. 12, Springer Nature, 2014, doi:<a href=\"https://doi.org/10.1007/978-1-4939-1969-7_6\">10.1007/978-1-4939-1969-7_6</a>.","ama":"Dupret D, Csicsvari JL. Reorganization of Hippocampal Place-Selective Patterns During Goal-Directed Learning and Their Reactivation During Sleep. In: <i>Analysis and Modeling of Coordinated Multi-Neuronal Activity</i>. Vol 12. NEUROSCI. Springer Nature; 2014. doi:<a href=\"https://doi.org/10.1007/978-1-4939-1969-7_6\">10.1007/978-1-4939-1969-7_6</a>","ieee":"D. Dupret and J. L. Csicsvari, “Reorganization of Hippocampal Place-Selective Patterns During Goal-Directed Learning and Their Reactivation During Sleep,” in <i>Analysis and Modeling of Coordinated Multi-neuronal Activity</i>, vol. 12, Springer Nature, 2014.","chicago":"Dupret, David, and Jozsef L Csicsvari. “Reorganization of Hippocampal Place-Selective Patterns During Goal-Directed Learning and Their Reactivation During Sleep.” In <i>Analysis and Modeling of Coordinated Multi-Neuronal Activity</i>, Vol. 12. NEUROSCI. Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-1-4939-1969-7_6\">https://doi.org/10.1007/978-1-4939-1969-7_6</a>.","short":"D. Dupret, J.L. Csicsvari, in:, Analysis and Modeling of Coordinated Multi-Neuronal Activity, Springer Nature, 2014.","apa":"Dupret, D., &#38; Csicsvari, J. L. (2014). Reorganization of Hippocampal Place-Selective Patterns During Goal-Directed Learning and Their Reactivation During Sleep. In <i>Analysis and Modeling of Coordinated Multi-neuronal Activity</i> (Vol. 12). Springer Nature. <a href=\"https://doi.org/10.1007/978-1-4939-1969-7_6\">https://doi.org/10.1007/978-1-4939-1969-7_6</a>","ista":"Dupret D, Csicsvari JL. 2014.Reorganization of Hippocampal Place-Selective Patterns During Goal-Directed Learning and Their Reactivation During Sleep. In: Analysis and Modeling of Coordinated Multi-neuronal Activity. Springer Series in Computational Neuroscience, vol. 12."},"day":"30","_id":"19994","title":"Reorganization of Hippocampal Place-Selective Patterns During Goal-Directed Learning and Their Reactivation During Sleep","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"10","volume":12,"type":"book_chapter"},{"external_id":{"isi":["000345702700002"]},"ec_funded":1,"date_published":"2014-06-22T00:00:00Z","date_created":"2018-12-11T11:55:08Z","publication":"Environmental Microbiology Reports","publist_id":"5076","author":[{"last_name":"Mitosch","first_name":"Karin","id":"39B66846-F248-11E8-B48F-1D18A9856A87","full_name":"Mitosch, Karin"},{"id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","full_name":"Bollenbach, Tobias","first_name":"Tobias","last_name":"Bollenbach","orcid":"0000-0003-4398-476X"}],"date_updated":"2026-04-08T14:21:56Z","year":"2014","language":[{"iso":"eng"}],"issue":"6","status":"public","oa_version":"None","doi":"10.1111/1758-2229.12190","quality_controlled":"1","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"818"}]},"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"Bacterial responses to antibiotics and their combinations","_id":"2001","volume":6,"type":"journal_article","isi":1,"project":[{"name":"Revealing the fundamental limits of cell growth","grant_number":"RGP0042/2013","_id":"25EB3A80-B435-11E9-9278-68D0E5697425"},{"grant_number":"303507","_id":"25E83C2C-B435-11E9-9278-68D0E5697425","name":"Optimality principles in responses to antibiotics","call_identifier":"FP7"}],"publisher":"Wiley","intvolume":"         6","department":[{"_id":"ToBo"}],"publication_status":"published","article_processing_charge":"No","scopus_import":"1","citation":{"short":"K. Mitosch, M.T. Bollenbach, Environmental Microbiology Reports 6 (2014) 545–557.","apa":"Mitosch, K., &#38; Bollenbach, M. T. (2014). Bacterial responses to antibiotics and their combinations. <i>Environmental Microbiology Reports</i>. Wiley. <a href=\"https://doi.org/10.1111/1758-2229.12190\">https://doi.org/10.1111/1758-2229.12190</a>","ista":"Mitosch K, Bollenbach MT. 2014. Bacterial responses to antibiotics and their combinations. Environmental Microbiology Reports. 6(6), 545–557.","ama":"Mitosch K, Bollenbach MT. Bacterial responses to antibiotics and their combinations. <i>Environmental Microbiology Reports</i>. 2014;6(6):545-557. doi:<a href=\"https://doi.org/10.1111/1758-2229.12190\">10.1111/1758-2229.12190</a>","ieee":"K. Mitosch and M. T. Bollenbach, “Bacterial responses to antibiotics and their combinations,” <i>Environmental Microbiology Reports</i>, vol. 6, no. 6. Wiley, pp. 545–557, 2014.","chicago":"Mitosch, Karin, and Mark Tobias Bollenbach. “Bacterial Responses to Antibiotics and Their Combinations.” <i>Environmental Microbiology Reports</i>. Wiley, 2014. <a href=\"https://doi.org/10.1111/1758-2229.12190\">https://doi.org/10.1111/1758-2229.12190</a>.","mla":"Mitosch, Karin, and Mark Tobias Bollenbach. “Bacterial Responses to Antibiotics and Their Combinations.” <i>Environmental Microbiology Reports</i>, vol. 6, no. 6, Wiley, 2014, pp. 545–57, doi:<a href=\"https://doi.org/10.1111/1758-2229.12190\">10.1111/1758-2229.12190</a>."},"abstract":[{"text":"Antibiotics affect bacterial cell physiology at many levels. Rather than just compensating for the direct cellular defects caused by the drug, bacteria respond to antibiotics by changing their morphology, macromolecular composition, metabolism, gene expression and possibly even their mutation rate. Inevitably, these processes affect each other, resulting in a complex response with changes in the expression of numerous genes. Genome‐wide approaches can thus help in gaining a comprehensive understanding of bacterial responses to antibiotics. In addition, a combination of experimental and theoretical approaches is needed for identifying general principles that underlie these responses. Here, we review recent progress in our understanding of bacterial responses to antibiotics and their combinations, focusing on effects at the levels of growth rate and gene expression. We concentrate on studies performed in controlled laboratory conditions, which combine promising experimental techniques with quantitative data analysis and mathematical modeling. While these basic research approaches are not immediately applicable in the clinic, uncovering the principles and mechanisms underlying bacterial responses to antibiotics may, in the long term, contribute to the development of new treatment strategies to cope with and prevent the rise of resistant pathogenic bacteria.","lang":"eng"}],"page":"545 - 557","day":"22","month":"06"},{"license":"https://creativecommons.org/licenses/by-sa/4.0/","external_id":{"isi":["000345533200070"]},"file":[{"date_created":"2018-12-12T10:14:52Z","file_name":"IST-2016-434-v1+1_journal.pone.0113124.pdf","file_size":5179993,"relation":"main_file","creator":"system","checksum":"85e4f4ea144f827272aaf376b2830564","access_level":"open_access","content_type":"application/pdf","date_updated":"2020-07-14T12:45:24Z","file_id":"5107"}],"date_created":"2018-12-11T11:55:09Z","date_published":"2014-11-19T00:00:00Z","ec_funded":1,"year":"2014","date_updated":"2025-09-29T12:03:47Z","author":[{"last_name":"Kim","first_name":"Sooyun","id":"394AB1C8-F248-11E8-B48F-1D18A9856A87","full_name":"Kim, Sooyun"}],"publication":"PLoS One","publist_id":"5074","quality_controlled":"1","doi":"10.1371/journal.pone.0113124","oa_version":"Published Version","issue":"11","status":"public","language":[{"iso":"eng"}],"tmp":{"short":"CC BY-SA (4.0)","image":"/images/cc_by_sa.png","name":"Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-sa/4.0/legalcode"},"pubrep_id":"434","has_accepted_license":"1","_id":"2002","title":"Action potential modulation in CA1 pyramidal neuron axons facilitates OLM interneuron activation in recurrent inhibitory microcircuits of rat hippocampus","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","isi":1,"type":"journal_article","volume":9,"project":[{"call_identifier":"FP7","name":"Nanophysiology of fast-spiking, parvalbumin-expressing GABAergic interneurons","_id":"25C0F108-B435-11E9-9278-68D0E5697425","grant_number":"268548"}],"intvolume":"         9","publisher":"Public Library of Science","department":[{"_id":"PeJo"}],"publication_status":"published","file_date_updated":"2020-07-14T12:45:24Z","scopus_import":"1","article_number":"0113124","article_processing_charge":"No","ddc":["570"],"citation":{"mla":"Kim, Sooyun. “Action Potential Modulation in CA1 Pyramidal Neuron Axons Facilitates OLM Interneuron Activation in Recurrent Inhibitory Microcircuits of Rat Hippocampus.” <i>PLoS One</i>, vol. 9, no. 11, 0113124, Public Library of Science, 2014, doi:<a href=\"https://doi.org/10.1371/journal.pone.0113124\">10.1371/journal.pone.0113124</a>.","ama":"Kim S. Action potential modulation in CA1 pyramidal neuron axons facilitates OLM interneuron activation in recurrent inhibitory microcircuits of rat hippocampus. <i>PLoS One</i>. 2014;9(11). doi:<a href=\"https://doi.org/10.1371/journal.pone.0113124\">10.1371/journal.pone.0113124</a>","chicago":"Kim, Sooyun. “Action Potential Modulation in CA1 Pyramidal Neuron Axons Facilitates OLM Interneuron Activation in Recurrent Inhibitory Microcircuits of Rat Hippocampus.” <i>PLoS One</i>. Public Library of Science, 2014. <a href=\"https://doi.org/10.1371/journal.pone.0113124\">https://doi.org/10.1371/journal.pone.0113124</a>.","ieee":"S. Kim, “Action potential modulation in CA1 pyramidal neuron axons facilitates OLM interneuron activation in recurrent inhibitory microcircuits of rat hippocampus,” <i>PLoS One</i>, vol. 9, no. 11. Public Library of Science, 2014.","short":"S. Kim, PLoS One 9 (2014).","apa":"Kim, S. (2014). Action potential modulation in CA1 pyramidal neuron axons facilitates OLM interneuron activation in recurrent inhibitory microcircuits of rat hippocampus. <i>PLoS One</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0113124\">https://doi.org/10.1371/journal.pone.0113124</a>","ista":"Kim S. 2014. Action potential modulation in CA1 pyramidal neuron axons facilitates OLM interneuron activation in recurrent inhibitory microcircuits of rat hippocampus. PLoS One. 9(11), 0113124."},"abstract":[{"text":"Oriens-lacunosum moleculare (O-LM) interneurons in the CA1 region of the hippocampus play a key role in feedback inhibition and in the control of network activity. However, how these cells are efficiently activated in the network remains unclear. To address this question, I performed recordings from CA1 pyramidal neuron axons, the presynaptic fibers that provide feedback innervation of these interneurons. Two forms of axonal action potential (AP) modulation were identified. First, repetitive stimulation resulted in activity-dependent AP broadening. Broadening showed fast onset, with marked changes in AP shape following a single AP. Second, tonic depolarization in CA1 pyramidal neuron somata induced AP broadening in the axon, and depolarization-induced broadening summated with activity-dependent broadening. Outsideout patch recordings from CA1 pyramidal neuron axons revealed a high density of a-dendrotoxin (α-DTX)-sensitive, inactivating K+ channels, suggesting that K+ channel inactivation mechanistically contributes to AP broadening. To examine the functional consequences of axonal AP modulation for synaptic transmission, I performed paired recordings between synaptically connected CA1 pyramidal neurons and O-LM interneurons. CA1 pyramidal neuron-O-LM interneuron excitatory postsynaptic currents (EPSCs) showed facilitation during both repetitive stimulation and tonic depolarization of the presynaptic neuron. Both effects were mimicked and occluded by α-DTX, suggesting that they were mediated by K+ channel inactivation. Therefore, axonal AP modulation can greatly facilitate the activation of O-LM interneurons. In conclusion, modulation of AP shape in CA1 pyramidal neuron axons substantially enhances the efficacy of principal neuron-interneuron synapses, promoting the activation of O-LM interneurons in recurrent inhibitory microcircuits.","lang":"eng"}],"day":"19","month":"11","oa":1}]