[{"page":"2866 - 2880","date_published":"2015-06-15T00:00:00Z","abstract":[{"text":"Dendritic cells are potent antigen-presenting cells endowed with the unique ability to initiate adaptive immune responses upon inflammation. Inflammatory processes are often associated with an increased production of serotonin, which operates by activating specific receptors. However, the functional role of serotonin receptors in regulation of dendritic cell functions is poorly understood. Here, we demonstrate that expression of serotonin receptor 5-HT7 (5-HT7TR) as well as its downstream effector Cdc42 is upregulated in dendritic cells upon maturation. Although dendritic cell maturation was independent of 5-HT7TR, receptor stimulation affected dendritic cell morphology through Cdc42-mediated signaling. In addition, basal activity of 5-HT7TR was required for the proper expression of the chemokine receptor CCR7, which is a key factor that controls dendritic cell migration. Consistent with this, we observed that 5-HT7TR enhances chemotactic motility of dendritic cells in vitro by modulating their directionality and migration velocity. Accordingly, migration of dendritic cells in murine colon explants was abolished after pharmacological receptor inhibition. Our results indicate that there is a crucial role for 5-HT7TR-Cdc42-mediated signaling in the regulation of dendritic cell morphology and motility, suggesting that 5-HT7TR could be a new target for treatment of a variety of inflammatory and immune disorders.","lang":"eng"}],"day":"15","fulldoi":"https://doi.org/10.1242/jcs.167999","publication":"Journal of Cell Science","language":[{"iso":"eng"}],"publication_status":"published","quality_controlled":"1","type":"journal_article","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","scopus_import":"1","doi":"10.1242/jcs.167999","_id":"477","external_id":{"isi":["000359782100013"]},"article_processing_charge":"No","volume":128,"date_created":"2018-12-11T11:46:41Z","citation":{"short":"K. Holst, D. Guseva, S. Schindler, M.K. Sixt, A. Braun, H. Chopra, O. Pabst, E. Ponimaskin, Journal of Cell Science 128 (2015) 2866–2880.","apa":"Holst, K., Guseva, D., Schindler, S., Sixt, M. K., Braun, A., Chopra, H., … Ponimaskin, E. (2015). The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells. <i>Journal of Cell Science</i>. Company of Biologists. <a href=\"https://doi.org/10.1242/jcs.167999\">https://doi.org/10.1242/jcs.167999</a>","ama":"Holst K, Guseva D, Schindler S, et al. The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells. <i>Journal of Cell Science</i>. 2015;128(15):2866-2880. doi:<a href=\"https://doi.org/10.1242/jcs.167999\">10.1242/jcs.167999</a>","ista":"Holst K, Guseva D, Schindler S, Sixt MK, Braun A, Chopra H, Pabst O, Ponimaskin E. 2015. The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells. Journal of Cell Science. 128(15), 2866–2880.","mla":"Holst, Katrin, et al. “The Serotonin Receptor 5-HT7R Regulates the Morphology and Migratory Properties of Dendritic Cells.” <i>Journal of Cell Science</i>, vol. 128, no. 15, Company of Biologists, 2015, pp. 2866–80, doi:<a href=\"https://doi.org/10.1242/jcs.167999\">10.1242/jcs.167999</a>.","chicago":"Holst, Katrin, Daria Guseva, Susann Schindler, Michael K Sixt, Armin Braun, Himpriya Chopra, Oliver Pabst, and Evgeni Ponimaskin. “The Serotonin Receptor 5-HT7R Regulates the Morphology and Migratory Properties of Dendritic Cells.” <i>Journal of Cell Science</i>. Company of Biologists, 2015. <a href=\"https://doi.org/10.1242/jcs.167999\">https://doi.org/10.1242/jcs.167999</a>.","ieee":"K. Holst <i>et al.</i>, “The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells,” <i>Journal of Cell Science</i>, vol. 128, no. 15. Company of Biologists, pp. 2866–2880, 2015."},"publisher":"Company of Biologists","status":"public","intvolume":"       128","title":"The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells","year":"2015","oa_version":"None","author":[{"first_name":"Katrin","full_name":"Holst, Katrin","last_name":"Holst"},{"first_name":"Daria","last_name":"Guseva","full_name":"Guseva, Daria"},{"last_name":"Schindler","full_name":"Schindler, Susann","first_name":"Susann"},{"first_name":"Michael K","orcid":"0000-0002-6620-9179","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","last_name":"Sixt","full_name":"Sixt, Michael K"},{"last_name":"Braun","full_name":"Braun, Armin","first_name":"Armin"},{"full_name":"Chopra, Himpriya","last_name":"Chopra","first_name":"Himpriya"},{"first_name":"Oliver","full_name":"Pabst, Oliver","last_name":"Pabst"},{"full_name":"Ponimaskin, Evgeni","last_name":"Ponimaskin","first_name":"Evgeni"}],"publist_id":"7343","date_updated":"2025-09-23T14:16:38Z","isi":1,"month":"06","department":[{"_id":"MiSi"}],"issue":"15"},{"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"ec_funded":1,"fulldoi":"https://doi.org/10.1016/j.ic.2015.03.010","day":"24","abstract":[{"lang":"eng","text":"We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window."}],"date_published":"2015-03-24T00:00:00Z","page":"25 - 52","doi":"10.1016/j.ic.2015.03.010","scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","type":"journal_article","publication_status":"published","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","id":"2279","relation":"earlier_version"}]},"publication":"Information and Computation","intvolume":"       242","title":"Looking at mean-payoff and total-payoff through windows","oa":1,"status":"public","arxiv":1,"publisher":"Elsevier","citation":{"ieee":"K. Chatterjee, L. Doyen, M. Randour, and J. Raskin, “Looking at mean-payoff and total-payoff through windows,” <i>Information and Computation</i>, vol. 242, no. 6. Elsevier, pp. 25–52, 2015.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Mickael Randour, and Jean Raskin. “Looking at Mean-Payoff and Total-Payoff through Windows.” <i>Information and Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">https://doi.org/10.1016/j.ic.2015.03.010</a>.","ista":"Chatterjee K, Doyen L, Randour M, Raskin J. 2015. Looking at mean-payoff and total-payoff through windows. Information and Computation. 242(6), 25–52.","ama":"Chatterjee K, Doyen L, Randour M, Raskin J. Looking at mean-payoff and total-payoff through windows. <i>Information and Computation</i>. 2015;242(6):25-52. doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">10.1016/j.ic.2015.03.010</a>","mla":"Chatterjee, Krishnendu, et al. “Looking at Mean-Payoff and Total-Payoff through Windows.” <i>Information and Computation</i>, vol. 242, no. 6, Elsevier, 2015, pp. 25–52, doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">10.1016/j.ic.2015.03.010</a>.","apa":"Chatterjee, K., Doyen, L., Randour, M., &#38; Raskin, J. (2015). Looking at mean-payoff and total-payoff through windows. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">https://doi.org/10.1016/j.ic.2015.03.010</a>","short":"K. Chatterjee, L. Doyen, M. Randour, J. Raskin, Information and Computation 242 (2015) 25–52."},"article_processing_charge":"No","date_created":"2018-12-11T11:46:57Z","volume":242,"external_id":{"arxiv":["1302.4248"],"isi":["000355664900003"]},"_id":"523","issue":"6","department":[{"_id":"KrCh"}],"month":"03","main_file_link":[{"url":"https://arxiv.org/abs/1302.4248","open_access":"1"}],"isi":1,"date_updated":"2025-09-23T09:29:55Z","publist_id":"7296","author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"},{"full_name":"Randour, Mickael","last_name":"Randour","first_name":"Mickael"},{"first_name":"Jean","full_name":"Raskin, Jean","last_name":"Raskin"}],"oa_version":"Preprint","year":"2015"},{"language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","id":"5403","relation":"earlier_version"}]},"publication":"Information and Computation","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","scopus_import":"1","doi":"10.1016/j.ic.2015.03.009","publication_status":"published","type":"journal_article","quality_controlled":"1","abstract":[{"lang":"eng","text":"We consider concurrent games played by two players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question of whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time."}],"day":"11","page":"2 - 24","date_published":"2015-10-11T00:00:00Z","corr_author":"1","fulldoi":"https://doi.org/10.1016/j.ic.2015.03.009","publist_id":"7295","date_updated":"2025-09-23T09:56:28Z","year":"2015","oa_version":"Preprint","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000-0003-4783-0389","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"issue":"6","isi":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1409.5306"}],"month":"10","department":[{"_id":"KrCh"}],"volume":242,"citation":{"chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” <i>Information and Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">https://doi.org/10.1016/j.ic.2015.03.009</a>.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “Qualitative analysis of concurrent mean payoff games,” <i>Information and Computation</i>, vol. 242, no. 6. Elsevier, pp. 2–24, 2015.","short":"K. Chatterjee, R. Ibsen-Jensen, Information and Computation 242 (2015) 2–24.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2015). Qualitative analysis of concurrent mean payoff games. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">https://doi.org/10.1016/j.ic.2015.03.009</a>","ista":"Chatterjee K, Ibsen-Jensen R. 2015. Qualitative analysis of concurrent mean payoff games. Information and Computation. 242(6), 2–24.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” <i>Information and Computation</i>, vol. 242, no. 6, Elsevier, 2015, pp. 2–24, doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">10.1016/j.ic.2015.03.009</a>.","ama":"Chatterjee K, Ibsen-Jensen R. Qualitative analysis of concurrent mean payoff games. <i>Information and Computation</i>. 2015;242(6):2-24. doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">10.1016/j.ic.2015.03.009</a>"},"article_processing_charge":"No","date_created":"2018-12-11T11:46:57Z","publisher":"Elsevier","_id":"524","external_id":{"isi":["000355664900002"],"arxiv":["1409.5306"]},"oa":1,"title":"Qualitative analysis of concurrent mean payoff games","intvolume":"       242","arxiv":1,"status":"public"},{"fulldoi":"https://doi.org/10.1016/j.cell.2015.09.037","abstract":[{"lang":"eng","text":"Ethylene is a gaseous phytohormone that plays vital roles in plant growth and development. Previous studies uncovered EIN2 as an essential signal transducer linking ethylene perception on ER to transcriptional regulation in the nucleus through a “cleave and shuttle” model. In this study, we report another mechanism of EIN2-mediated ethylene signaling, whereby EIN2 imposes the translational repression of EBF1 and EBF2 mRNA. We find that the EBF1/2 3′ UTRs mediate EIN2-directed translational repression and identify multiple poly-uridylates (PolyU) motifs as functional cis elements of 3′ UTRs. Furthermore, we demonstrate that ethylene induces EIN2 to associate with 3′ UTRs and target EBF1/2 mRNA to cytoplasmic processing-body (P-body) through interacting with multiple P-body factors, including EIN5 and PABs. Our study illustrates translational regulation as a key step in ethylene signaling and presents mRNA 3′ UTR functioning as a “signal transducer” to sense and relay cellular signaling in plants."}],"day":"22","page":"670 - 683","date_published":"2015-10-22T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","doi":"10.1016/j.cell.2015.09.037","scopus_import":"1","type":"journal_article","quality_controlled":"1","publication_status":"published","language":[{"iso":"eng"}],"publication":"Cell","title":"EIN2-directed translational regulation of ethylene signaling in arabidopsis","intvolume":"       163","status":"public","article_processing_charge":"No","volume":163,"date_created":"2018-12-11T11:47:00Z","citation":{"ama":"Li W, Ma M, Feng Y, et al. EIN2-directed translational regulation of ethylene signaling in arabidopsis. <i>Cell</i>. 2015;163(3):670-683. doi:<a href=\"https://doi.org/10.1016/j.cell.2015.09.037\">10.1016/j.cell.2015.09.037</a>","mla":"Li, Wenyang, et al. “EIN2-Directed Translational Regulation of Ethylene Signaling in Arabidopsis.” <i>Cell</i>, vol. 163, no. 3, Cell Press, 2015, pp. 670–83, doi:<a href=\"https://doi.org/10.1016/j.cell.2015.09.037\">10.1016/j.cell.2015.09.037</a>.","ista":"Li W, Ma M, Feng Y, Li H, Wang Y, Ma Y, Li M, An F, Guo H. 2015. EIN2-directed translational regulation of ethylene signaling in arabidopsis. Cell. 163(3), 670–683.","apa":"Li, W., Ma, M., Feng, Y., Li, H., Wang, Y., Ma, Y., … Guo, H. (2015). EIN2-directed translational regulation of ethylene signaling in arabidopsis. <i>Cell</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.cell.2015.09.037\">https://doi.org/10.1016/j.cell.2015.09.037</a>","short":"W. Li, M. Ma, Y. Feng, H. Li, Y. Wang, Y. Ma, M. Li, F. An, H. Guo, Cell 163 (2015) 670–683.","ieee":"W. Li <i>et al.</i>, “EIN2-directed translational regulation of ethylene signaling in arabidopsis,” <i>Cell</i>, vol. 163, no. 3. Cell Press, pp. 670–683, 2015.","chicago":"Li, Wenyang, Mengdi Ma, Ying Feng, Hongjiang Li, Yichuan Wang, Yutong Ma, Mingzhe Li, Fengying An, and Hongwei Guo. “EIN2-Directed Translational Regulation of Ethylene Signaling in Arabidopsis.” <i>Cell</i>. Cell Press, 2015. <a href=\"https://doi.org/10.1016/j.cell.2015.09.037\">https://doi.org/10.1016/j.cell.2015.09.037</a>."},"publisher":"Cell Press","_id":"532","external_id":{"isi":["000364828900020"]},"issue":"3","month":"10","isi":1,"department":[{"_id":"JiFr"}],"date_updated":"2025-09-23T08:40:43Z","publist_id":"7285","year":"2015","oa_version":"None","author":[{"last_name":"Li","full_name":"Li, Wenyang","first_name":"Wenyang"},{"first_name":"Mengdi","full_name":"Ma, Mengdi","last_name":"Ma"},{"full_name":"Feng, Ying","last_name":"Feng","first_name":"Ying"},{"orcid":"0000-0001-5039-9660","first_name":"Hongjiang","last_name":"Li","id":"33CA54A6-F248-11E8-B48F-1D18A9856A87","full_name":"Li, Hongjiang"},{"full_name":"Wang, Yichuan","last_name":"Wang","first_name":"Yichuan"},{"first_name":"Yutong","full_name":"Ma, Yutong","last_name":"Ma"},{"last_name":"Li","full_name":"Li, Mingzhe","first_name":"Mingzhe"},{"full_name":"An, Fengying","last_name":"An","first_name":"Fengying"},{"full_name":"Guo, Hongwei","last_name":"Guo","first_name":"Hongwei"}]},{"oa_version":"Published Version","year":"2015","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"orcid":"0000-0003-4783-0389","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","orcid":"0000-0002-8943-0722"}],"date_updated":"2025-09-23T08:47:23Z","ddc":["000"],"month":"02","pubrep_id":"319","department":[{"_id":"KrCh"}],"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"_id":"5430","date_created":"2018-12-12T11:39:17Z","citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2015). <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">https://doi.org/10.15479/AT:IST-2015-319-v1-1</a>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 31p.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">10.15479/AT:IST-2015-319-v1-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">10.15479/AT:IST-2015-319-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">https://doi.org/10.15479/AT:IST-2015-319-v1-1</a>.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria, 2015."},"publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:52Z","status":"public","title":"Faster algorithms for quantitative verification in constant treewidth graphs","oa":1,"related_material":{"record":[{"relation":"later_version","id":"5437","status":"public"},{"status":"public","id":"1607","relation":"later_version"}]},"language":[{"iso":"eng"}],"type":"technical_report","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.15479/AT:IST-2015-319-v1-1","page":"31","date_published":"2015-02-10T00:00:00Z","file":[{"access_level":"open_access","file_id":"5482","checksum":"62c6ea01e342553dcafb88a070fb1ad5","date_updated":"2020-07-14T12:46:52Z","date_created":"2018-12-12T11:53:21Z","creator":"system","file_size":1089651,"content_type":"application/pdf","file_name":"IST-2015-319-v1+1_long.pdf","relation":"main_file"}],"abstract":[{"text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean- payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) ) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O ( n · log( | a · b · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · log( n · W )) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.","lang":"eng"}],"day":"10","fulldoi":"https://doi.org/10.15479/AT:IST-2015-319-v1-1","publication_identifier":{"issn":["2664-1690"]}},{"language":[{"iso":"eng"}],"ddc":["005","519"],"date_updated":"2021-01-12T08:02:13Z","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","first_name":"Rasmus"},{"first_name":"Kristoffer","last_name":"Hansen","full_name":"Hansen, Kristoffer"}],"year":"2015","oa_version":"Published Version","doi":"10.15479/AT:IST-2015-322-v1-1","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"}],"pubrep_id":"322","publication_status":"published","month":"02","type":"technical_report","day":"19","publisher":"IST Austria","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, and K. Hansen, <i>The patience of concurrent stochastic games with safety and reachability objectives</i>. IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Kristoffer Hansen. <i>The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">https://doi.org/10.15479/AT:IST-2015-322-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic games with safety and reachability objectives, IST Austria, 25p.","mla":"Chatterjee, Krishnendu, et al. <i>The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">10.15479/AT:IST-2015-322-v1-1</a>.","ama":"Chatterjee K, Ibsen-Jensen R, Hansen K. <i>The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">10.15479/AT:IST-2015-322-v1-1</a>","short":"K. Chatterjee, R. Ibsen-Jensen, K. Hansen, The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives, IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Hansen, K. (2015). <i>The patience of concurrent stochastic games with safety and reachability objectives</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">https://doi.org/10.15479/AT:IST-2015-322-v1-1</a>"},"date_created":"2018-12-12T11:39:17Z","abstract":[{"lang":"eng","text":"We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target set is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed.\r\n\r\n Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience is needed in general for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, then the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential."}],"file":[{"file_id":"5491","access_level":"open_access","checksum":"bfb858262c30445b8e472c40069178a2","date_created":"2018-12-12T11:53:31Z","date_updated":"2020-07-14T12:46:53Z","creator":"system","content_type":"application/pdf","file_size":661015,"file_name":"IST-2015-322-v1+1_safetygames.pdf","relation":"main_file"}],"date_published":"2015-02-19T00:00:00Z","_id":"5431","page":"25","oa":1,"publication_identifier":{"issn":["2664-1690"]},"title":"The patience of concurrent stochastic games with safety and reachability objectives","fulldoi":"https://doi.org/10.15479/AT:IST-2015-322-v1-1","status":"public","file_date_updated":"2020-07-14T12:46:53Z"},{"month":"02","department":[{"_id":"KrCh"}],"pubrep_id":"323","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","year":"2015","oa_version":"Published Version","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus"},{"first_name":"Martin","full_name":"Nowak, Martin","last_name":"Nowak"}],"date_updated":"2023-02-23T12:26:33Z","ddc":["005","576"],"file_date_updated":"2020-07-14T12:46:53Z","status":"public","oa":1,"title":"The complexity of evolutionary games on graphs","_id":"5432","citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2015). <i>The complexity of evolutionary games on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">https://doi.org/10.15479/AT:IST-2015-323-v1-1</a>","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015.","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">10.15479/AT:IST-2015-323-v1-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">10.15479/AT:IST-2015-323-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 29p.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">https://doi.org/10.15479/AT:IST-2015-323-v1-1</a>.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. IST Austria, 2015."},"date_created":"2018-12-12T11:39:18Z","publisher":"IST Austria","publication_status":"published","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.15479/AT:IST-2015-323-v1-1","related_material":{"record":[{"id":"5421","relation":"earlier_version","status":"public"},{"relation":"later_version","id":"5440","status":"public"}]},"language":[{"iso":"eng"}],"fulldoi":"https://doi.org/10.15479/AT:IST-2015-323-v1-1","publication_identifier":{"issn":["2664-1690"]},"page":"29","file":[{"access_level":"open_access","file_id":"5519","checksum":"546c1b291d545e7b24aaaf4199dac671","date_updated":"2020-07-14T12:46:53Z","date_created":"2018-12-12T11:53:57Z","creator":"system","file_size":576347,"content_type":"application/pdf","file_name":"IST-2015-323-v1+1_main.pdf","relation":"main_file"}],"date_published":"2015-02-19T00:00:00Z","abstract":[{"text":"Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution.The replacement graph specifies who competes with whom for reproduction. \r\nThe vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. 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. \r\nOur main results are:\r\n(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).\r\n(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.\r\n","lang":"eng"}],"day":"19"},{"date_updated":"2025-09-23T08:47:23Z","ddc":["000"],"oa_version":"Published Version","year":"2015","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","orcid":"0000-0003-4783-0389"},{"first_name":"Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas"}],"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"month":"04","pubrep_id":"333","department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:19Z","citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2015). <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">https://doi.org/10.15479/AT:IST-2015-330-v2-1</a>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p.","mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">10.15479/AT:IST-2015-330-v2-1</a>.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">10.15479/AT:IST-2015-330-v2-1</a>","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">https://doi.org/10.15479/AT:IST-2015-330-v2-1</a>.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria, 2015."},"publisher":"IST Austria","_id":"5437","title":"Faster algorithms for quantitative verification in constant treewidth graphs","oa":1,"file_date_updated":"2020-07-14T12:46:54Z","status":"public","language":[{"iso":"eng"}],"related_material":{"record":[{"id":"5430","relation":"earlier_version","status":"public"},{"relation":"later_version","id":"1607","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.15479/AT:IST-2015-330-v2-1","type":"technical_report","publication_status":"published","abstract":[{"text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. \r\nThe algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let $n$ denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth graphs $m=O(n)$) and $W$ the largest absolute value of the weights.\r\nOur main theoretical results are as follows.\r\nFirst, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $\\epsilon$ in time $O(n \\cdot \\log (n/\\epsilon))$ and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time $O(n \\cdot \\log (|a\\cdot b|))=O(n\\cdot\\log (n\\cdot W))$, when the output is $\\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \\cdot \\log (n\\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\\cdot m)$ time and the associated decision problem can be solved in $O(n\\cdot m)$ time, improving the previous known $O(n^3\\cdot m\\cdot \\log (n\\cdot W))$ and $O(n^2 \\cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\\cdot \\log n)$ time, improving the previous known $O(n^4 \\cdot \\log (n \\cdot W))$ bound.\r\nWe have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks. ","lang":"eng"}],"day":"27","page":"27","date_published":"2015-04-27T00:00:00Z","file":[{"file_size":1072137,"content_type":"application/pdf","file_name":"IST-2015-330-v2+1_main.pdf","relation":"main_file","creator":"system","date_updated":"2020-07-14T12:46:54Z","date_created":"2018-12-12T11:53:12Z","access_level":"open_access","file_id":"5473","checksum":"f5917c20f84018b362d385c000a2e123"}],"publication_identifier":{"issn":["2664-1690"]},"fulldoi":"https://doi.org/10.15479/AT:IST-2015-330-v2-1"},{"publication_status":"published","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.15479/AT:IST-2015-335-v1-1","language":[{"iso":"eng"}],"related_material":{"record":[{"id":"1659","relation":"later_version","status":"public"}]},"fulldoi":"https://doi.org/10.15479/AT:IST-2015-335-v1-1","publication_identifier":{"issn":["2664-1690"]},"page":"20","file":[{"content_type":"application/pdf","file_size":589619,"file_name":"IST-2015-335-v1+1_report.pdf","relation":"main_file","creator":"system","date_created":"2018-12-12T11:53:55Z","date_updated":"2020-07-14T12:46:55Z","file_id":"5517","access_level":"open_access","checksum":"40405907aa012acece1bc26cf0be554d"}],"date_published":"2015-05-18T00:00:00Z","abstract":[{"lang":"eng","text":"The target discounted-sum problem is the following: Given a rational discount factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata. "}],"day":"18","month":"05","department":[{"_id":"ToHe"}],"pubrep_id":"335","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","oa_version":"Published Version","year":"2015","author":[{"first_name":"Udi","full_name":"Boker, Udi","id":"31E297B6-F248-11E8-B48F-1D18A9856A87","last_name":"Boker"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A","orcid":"0000−0002−2985−7724"},{"first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","last_name":"Otop","full_name":"Otop, Jan"}],"date_updated":"2025-04-15T08:11:50Z","ddc":["004","512","513"],"file_date_updated":"2020-07-14T12:46:55Z","status":"public","oa":1,"title":"The target discounted-sum problem","_id":"5439","date_created":"2018-12-12T11:39:20Z","citation":{"ieee":"U. Boker, T. A. Henzinger, and J. Otop, <i>The target discounted-sum problem</i>. IST Austria, 2015.","chicago":"Boker, Udi, Thomas A Henzinger, and Jan Otop. <i>The Target Discounted-Sum Problem</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">https://doi.org/10.15479/AT:IST-2015-335-v1-1</a>.","ista":"Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem, IST Austria, 20p.","mla":"Boker, Udi, et al. <i>The Target Discounted-Sum Problem</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">10.15479/AT:IST-2015-335-v1-1</a>.","ama":"Boker U, Henzinger TA, Otop J. <i>The Target Discounted-Sum Problem</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">10.15479/AT:IST-2015-335-v1-1</a>","apa":"Boker, U., Henzinger, T. A., &#38; Otop, J. (2015). <i>The target discounted-sum problem</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">https://doi.org/10.15479/AT:IST-2015-335-v1-1</a>","short":"U. Boker, T.A. Henzinger, J. Otop, The Target Discounted-Sum Problem, IST Austria, 2015."},"publisher":"IST Austria"},{"publication_identifier":{"issn":["2664-1690"]},"fulldoi":"https://doi.org/10.15479/AT:IST-2015-323-v2-2","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 for payoff 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 of the population. The fitness (or the reproductive rate) is a non-negative number, and depends on the payoff. 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 as follows: First, we consider a special case of the general problem, where the residents do not reproduce. We show that the qualitative question is NP-complete, and the quantitative approximation question is #P-complete, and the hardness results hold even in the special case where the interaction and the replacement graphs coincide. Second, we show that in general both the qualitative and the quantitative approximation questions are PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds even when the fitness is always positive."}],"day":"16","page":"18","file":[{"creator":"system","file_name":"IST-2015-323-v2+2_main.pdf","relation":"main_file","file_size":466161,"content_type":"application/pdf","checksum":"66aace7d367032af97c15e35c9be9636","access_level":"open_access","file_id":"5484","date_updated":"2020-07-14T12:46:56Z","date_created":"2018-12-12T11:53:23Z"}],"date_published":"2015-06-16T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.15479/AT:IST-2015-323-v2-2","publication_status":"published","type":"technical_report","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"earlier_version","id":"5421","status":"public"},{"id":"5432","relation":"earlier_version","status":"public"}]},"oa":1,"title":"The complexity of evolutionary games on graphs","file_date_updated":"2020-07-14T12:46:56Z","status":"public","date_created":"2018-12-12T11:39:21Z","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">https://doi.org/10.15479/AT:IST-2015-323-v2-2</a>.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">10.15479/AT:IST-2015-323-v2-2</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 18p.","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">10.15479/AT:IST-2015-323-v2-2</a>","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2015). <i>The complexity of evolutionary games on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">https://doi.org/10.15479/AT:IST-2015-323-v2-2</a>","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015."},"publisher":"IST Austria","_id":"5440","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","month":"06","department":[{"_id":"KrCh"}],"pubrep_id":"338","date_updated":"2023-02-23T12:26:10Z","ddc":["005","576"],"oa_version":"Published Version","year":"2015","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","orcid":"0000-0003-4783-0389"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}]},{"fulldoi":"https://doi.org/10.15479/AT:IST-2015-340-v1-1","publication_identifier":{"issn":["2664-1690"]},"page":"24","file":[{"file_size":861396,"content_type":"application/pdf","file_name":"IST-2015-340-v1+1_main.pdf","relation":"main_file","creator":"system","date_updated":"2020-07-14T12:46:56Z","date_created":"2018-12-12T11:54:09Z","access_level":"open_access","file_id":"5531","checksum":"df383dc62c94d7b2ea639aba088a76c6"}],"date_published":"2015-07-11T00:00:00Z","abstract":[{"lang":"eng","text":"We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks."}],"day":"11","type":"technical_report","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.15479/AT:IST-2015-340-v1-1","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"earlier_version","id":"5442","status":"public"},{"id":"6009","relation":"later_version","status":"public"},{"status":"public","id":"1437","relation":"later_version"}]},"file_date_updated":"2020-07-14T12:46:56Z","status":"public","title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","oa":1,"_id":"5441","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, A. K. Goharshady, and A. Pavlogiannis, <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Amir Kafshdar Goharshady, and Andreas Pavlogiannis. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">https://doi.org/10.15479/AT:IST-2015-340-v1-1</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">10.15479/AT:IST-2015-340-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 24p.","ama":"Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">10.15479/AT:IST-2015-340-v1-1</a>","short":"K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., Goharshady, A. K., &#38; Pavlogiannis, A. (2015). <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">https://doi.org/10.15479/AT:IST-2015-340-v1-1</a>"},"date_created":"2018-12-12T11:39:21Z","publisher":"IST Austria","month":"07","pubrep_id":"340","department":[{"_id":"KrCh"}],"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"year":"2015","oa_version":"Published Version","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389"},{"last_name":"Goharshady","id":"391365CE-F248-11E8-B48F-1D18A9856A87","full_name":"Goharshady, Amir","first_name":"Amir","orcid":"0000-0003-1702-6584"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas","first_name":"Andreas","orcid":"0000-0002-8943-0722"}],"date_updated":"2025-04-15T08:11:48Z","ddc":["000"]},{"year":"2015","oa_version":"Published Version","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","full_name":"Chmelik, Martin","first_name":"Martin"},{"last_name":"Davies","id":"378E0060-F248-11E8-B48F-1D18A9856A87","full_name":"Davies, Jessica","first_name":"Jessica"}],"date_updated":"2025-06-25T11:52:13Z","ddc":["000"],"month":"11","department":[{"_id":"KrCh"}],"pubrep_id":"362","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","_id":"5443","citation":{"ista":"Chatterjee K, Chmelik M, Davies J. 2015. A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs, IST Austria, 23p.","mla":"Chatterjee, Krishnendu, et al. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">10.15479/AT:IST-2015-325-v2-1</a>.","ama":"Chatterjee K, Chmelik M, Davies J. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">10.15479/AT:IST-2015-325-v2-1</a>","apa":"Chatterjee, K., Chmelik, M., &#38; Davies, J. (2015). <i>A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">https://doi.org/10.15479/AT:IST-2015-325-v2-1</a>","short":"K. Chatterjee, M. Chmelik, J. Davies, A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs, IST Austria, 2015.","ieee":"K. Chatterjee, M. Chmelik, and J. Davies, <i>A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs</i>. IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Jessica Davies. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">https://doi.org/10.15479/AT:IST-2015-325-v2-1</a>."},"date_created":"2018-12-12T11:39:22Z","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:57Z","status":"public","oa":1,"title":"A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs","related_material":{"record":[{"id":"1166","relation":"later_version","status":"public"}]},"language":[{"iso":"eng"}],"publication_status":"published","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.15479/AT:IST-2015-325-v2-1","page":"23","file":[{"checksum":"f0fa31ad8161ed655137e94012123ef9","access_level":"open_access","file_id":"5466","date_updated":"2020-07-14T12:46:57Z","date_created":"2018-12-12T11:53:05Z","creator":"system","relation":"main_file","file_name":"IST-2015-325-v2+1_main.pdf","file_size":412379,"content_type":"application/pdf"}],"date_published":"2015-11-06T00:00:00Z","abstract":[{"lang":"eng","text":"POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach."}],"day":"06","fulldoi":"https://doi.org/10.15479/AT:IST-2015-325-v2-1","publication_identifier":{"issn":["2664-1690"]}},{"author":[{"id":"4A918E98-F248-11E8-B48F-1D18A9856A87","last_name":"Reiter","full_name":"Reiter, Johannes","orcid":"0000-0002-0170-7353","first_name":"Johannes"},{"first_name":"Alvin","full_name":"Makohon-Moore, Alvin","last_name":"Makohon-Moore"},{"first_name":"Jeffrey","last_name":"Gerold","full_name":"Gerold, Jeffrey"},{"first_name":"Ivana","last_name":"Bozic","full_name":"Bozic, Ivana"},{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"first_name":"Christine","last_name":"Iacobuzio-Donahue","full_name":"Iacobuzio-Donahue, Christine"},{"first_name":"Bert","last_name":"Vogelstein","full_name":"Vogelstein, Bert"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"}],"year":"2015","oa_version":"Published Version","language":[{"iso":"eng"}],"ddc":["000","576"],"date_updated":"2020-07-14T23:05:07Z","department":[{"_id":"KrCh"}],"pubrep_id":"399","publication_status":"published","type":"technical_report","month":"12","doi":"10.15479/AT:IST-2015-399-v1-1","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2015-12-30T00:00:00Z","file":[{"date_updated":"2020-07-14T12:46:58Z","date_created":"2018-12-12T11:53:24Z","access_level":"open_access","file_id":"5485","checksum":"c47d33bdda06181753c0af36f16e7b5d","file_size":3533200,"content_type":"application/pdf","file_name":"IST-2015-399-v1+1_treeomics.pdf","relation":"main_file","creator":"system"}],"_id":"5444","page":"25","day":"30","publisher":"IST Austria","citation":{"apa":"Reiter, J., Makohon-Moore, A., Gerold, J., Bozic, I., Chatterjee, K., Iacobuzio-Donahue, C., … Nowak, M. (2015). <i>Reconstructing robust phylogenies of metastatic cancers</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">https://doi.org/10.15479/AT:IST-2015-399-v1-1</a>","short":"J. Reiter, A. Makohon-Moore, J. Gerold, I. Bozic, K. Chatterjee, C. Iacobuzio-Donahue, B. Vogelstein, M. Nowak, Reconstructing Robust Phylogenies of Metastatic Cancers, IST Austria, 2015.","ama":"Reiter J, Makohon-Moore A, Gerold J, et al. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">10.15479/AT:IST-2015-399-v1-1</a>","mla":"Reiter, Johannes, et al. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">10.15479/AT:IST-2015-399-v1-1</a>.","ista":"Reiter J, Makohon-Moore A, Gerold J, Bozic I, Chatterjee K, Iacobuzio-Donahue C, Vogelstein B, Nowak M. 2015. Reconstructing robust phylogenies of metastatic cancers, IST Austria, 25p.","chicago":"Reiter, Johannes, Alvin Makohon-Moore, Jeffrey Gerold, Ivana Bozic, Krishnendu Chatterjee, Christine Iacobuzio-Donahue, Bert Vogelstein, and Martin Nowak. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">https://doi.org/10.15479/AT:IST-2015-399-v1-1</a>.","ieee":"J. Reiter <i>et al.</i>, <i>Reconstructing robust phylogenies of metastatic cancers</i>. IST Austria, 2015."},"date_created":"2018-12-12T11:39:22Z","abstract":[{"text":"A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal.","lang":"eng"}],"fulldoi":"https://doi.org/10.15479/AT:IST-2015-399-v1-1","status":"public","file_date_updated":"2020-07-14T12:46:58Z","oa":1,"publication_identifier":{"issn":["2664-1690"]},"title":"Reconstructing robust phylogenies of metastatic cancers"},{"month":"08","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"has_accepted_license":"1","oa_version":"Published Version","year":"2015","author":[{"last_name":"Fellner","id":"42BABFB4-F248-11E8-B48F-1D18A9856A87","full_name":"Fellner, Andreas","first_name":"Andreas"}],"date_updated":"2025-09-23T08:23:15Z","publist_id":"5564","ddc":["004"],"file_date_updated":"2020-07-14T12:47:00Z","status":"public","datarep_id":"28","title":"Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes","oa":1,"_id":"5549","article_processing_charge":"No","date_created":"2018-12-12T12:31:29Z","citation":{"apa":"Fellner, A. (2015). Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:28\">https://doi.org/10.15479/AT:ISTA:28</a>","short":"A. Fellner, (2015).","ista":"Fellner A. 2015. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes, Institute of Science and Technology Austria, <a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>.","mla":"Fellner, Andreas. <i>Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes</i>. Institute of Science and Technology Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>.","ama":"Fellner A. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. 2015. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>","chicago":"Fellner, Andreas. “Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015. <a href=\"https://doi.org/10.15479/AT:ISTA:28\">https://doi.org/10.15479/AT:ISTA:28</a>.","ieee":"A. Fellner, “Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015."},"publisher":"Institute of Science and Technology Austria","type":"research_data","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","contributor":[{"last_name":"Kretinsky","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"}],"doi":"10.15479/AT:ISTA:28","related_material":{"record":[{"relation":"popular_science","id":"1603","status":"public"}]},"tmp":{"image":"/images/cc_0.png","name":"Creative Commons Public Domain Dedication (CC0 1.0)","short":"CC0 (1.0)","legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode"},"fulldoi":"https://doi.org/10.15479/AT:ISTA:28","ec_funded":1,"keyword":["Markov Decision Process","Decision Tree","Probabilistic Verification","Counterexample Explanation"],"project":[{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF"}],"license":"https://creativecommons.org/publicdomain/zero/1.0/","file":[{"checksum":"b8bcb43c0893023cda66c1b69c16ac62","access_level":"open_access","file_id":"5597","date_updated":"2020-07-14T12:47:00Z","date_created":"2018-12-12T13:02:31Z","creator":"system","file_name":"IST-2015-28-v1+2_Fellner_DataRep.zip","relation":"main_file","file_size":49557109,"content_type":"application/zip"}],"date_published":"2015-08-13T00:00:00Z","abstract":[{"lang":"eng","text":"This repository contains the experimental part of the CAV 2015 publication Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.\r\nWe extended the probabilistic model checker PRISM to represent strategies of Markov Decision Processes as Decision Trees.\r\nThe archive contains a java executable version of the extended tool (prism_dectree.jar) together with a few examples of the PRISM benchmark library.\r\nTo execute the program, please have a look at the README.txt, which provides instructions and further information on the archive.\r\nThe archive contains scripts that (if run often enough) reproduces the data presented in the publication."}],"day":"13"},{"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.1145/2676726.2677008","scopus_import":"1","quality_controlled":"1","type":"conference","publication_status":"published","abstract":[{"lang":"eng","text":"We present a method and a tool for generating succinct representations of sets of concurrent traces. We focus on trace sets that contain all correct or all incorrect permutations of events from a given trace. We represent trace sets as HB-Formulas that are Boolean combinations of happens-before constraints between events. To generate a representation of incorrect interleavings, our method iteratively explores interleavings that violate the specification and gathers generalizations of the discovered interleavings into an HB-Formula; its complement yields a representation of correct interleavings.\r\n\r\nWe claim that our trace set representations can drive diverse verification, fault localization, repair, and synthesis techniques for concurrent programs. We demonstrate this by using our tool in three case studies involving synchronization synthesis, bug summarization, and abstraction refinement based verification. In each case study, our initial experimental results have been promising.\r\n\r\nIn the first case study, we present an algorithm for inferring missing synchronization from an HB-Formula representing correct interleavings of a given trace. The algorithm applies rules to rewrite specific patterns in the HB-Formula into locks, barriers, and wait-notify constructs. In the second case study, we use an HB-Formula representing incorrect interleavings for bug summarization. While the HB-Formula itself is a concise counterexample summary, we present additional inference rules to help identify specific concurrency bugs such as data races, define-use order violations, and two-stage access bugs. In the final case study, we present a novel predicate learning procedure that uses HB-Formulas representing abstract counterexamples to accelerate counterexample-guided abstraction refinement (CEGAR). In each iteration of the CEGAR loop, the procedure refines the abstraction to eliminate multiple spurious abstract counterexamples drawn from the HB-Formula."}],"day":"15","conference":{"end_date":"2015-01-17","name":"POPL: Principles of Programming Languages","start_date":"2015-01-15","location":"Mumbai, India"},"page":"433 - 444","file":[{"creator":"system","file_name":"IST-2015-317-v1+1_author_version.pdf","relation":"main_file","content_type":"application/pdf","file_size":399462,"checksum":"f0d4395b600f410a191256ac0b73af32","file_id":"5314","access_level":"open_access","date_created":"2018-12-12T10:17:56Z","date_updated":"2020-07-14T12:45:22Z"}],"date_published":"2015-01-15T00:00:00Z","publication_identifier":{"isbn":["978-1-4503-3300-9"]},"fulldoi":"https://doi.org/10.1145/2676726.2677008","date_updated":"2025-03-07T08:44:29Z","publist_id":"5091","ddc":["005"],"year":"2015","oa_version":"Submitted Version","author":[{"first_name":"Ashutosh","last_name":"Gupta","id":"335E5684-F248-11E8-B48F-1D18A9856A87","full_name":"Gupta, Ashutosh"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A"},{"first_name":"Arjun","full_name":"Radhakrishna, Arjun","last_name":"Radhakrishna","id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Roopsha","full_name":"Samanta, Roopsha","last_name":"Samanta","id":"3D2AAC08-F248-11E8-B48F-1D18A9856A87"},{"id":"3D6E8F2C-F248-11E8-B48F-1D18A9856A87","last_name":"Tarrach","full_name":"Tarrach, Thorsten","orcid":"0000-0003-4409-8487","first_name":"Thorsten"}],"has_accepted_license":"1","month":"01","pubrep_id":"317","department":[{"_id":"ToHe"}],"citation":{"chicago":"Gupta, Ashutosh, Thomas A Henzinger, Arjun Radhakrishna, Roopsha Samanta, and Thorsten Tarrach. “Succinct Representation of Concurrent Trace Sets,” 433–44. ACM, 2015. <a href=\"https://doi.org/10.1145/2676726.2677008\">https://doi.org/10.1145/2676726.2677008</a>.","ieee":"A. Gupta, T. A. Henzinger, A. Radhakrishna, R. Samanta, and T. Tarrach, “Succinct representation of concurrent trace sets,” presented at the POPL: Principles of Programming Languages, Mumbai, India, 2015, pp. 433–444.","apa":"Gupta, A., Henzinger, T. A., Radhakrishna, A., Samanta, R., &#38; Tarrach, T. (2015). Succinct representation of concurrent trace sets (pp. 433–444). Presented at the POPL: Principles of Programming Languages, Mumbai, India: ACM. <a href=\"https://doi.org/10.1145/2676726.2677008\">https://doi.org/10.1145/2676726.2677008</a>","short":"A. Gupta, T.A. Henzinger, A. Radhakrishna, R. Samanta, T. Tarrach, in:, ACM, 2015, pp. 433–444.","mla":"Gupta, Ashutosh, et al. <i>Succinct Representation of Concurrent Trace Sets</i>. ACM, 2015, pp. 433–44, doi:<a href=\"https://doi.org/10.1145/2676726.2677008\">10.1145/2676726.2677008</a>.","ista":"Gupta A, Henzinger TA, Radhakrishna A, Samanta R, Tarrach T. 2015. Succinct representation of concurrent trace sets. POPL: Principles of Programming Languages, 433–444.","ama":"Gupta A, Henzinger TA, Radhakrishna A, Samanta R, Tarrach T. Succinct representation of concurrent trace sets. In: ACM; 2015:433-444. doi:<a href=\"https://doi.org/10.1145/2676726.2677008\">10.1145/2676726.2677008</a>"},"article_processing_charge":"No","date_created":"2018-12-11T11:55:05Z","publisher":"ACM","_id":"1992","title":"Succinct representation of concurrent trace sets","oa":1,"file_date_updated":"2020-07-14T12:45:22Z","status":"public"},{"date_published":"2015-01-22T00:00:00Z","day":"22","abstract":[{"text":"The fitness effects of symbionts on their hosts can be context-dependent, with usually benign symbionts causing detrimental effects when their hosts are stressed, or typically parasitic symbionts providing protection towards their hosts (e.g. against pathogen infection). Here, we studied the novel association between the invasive garden ant Lasius neglectus and its fungal ectosymbiont Laboulbenia formicarum for potential costs and benefits. We tested ants with different Laboulbenia levels for their survival and immunity under resource limitation and exposure to the obligate killing entomopathogen Metarhizium brunneum. While survival of L. neglectus workers under starvation was significantly decreased with increasing Laboulbenia levels, host survival under Metarhizium exposure increased with higher levels of the ectosymbiont, suggesting a symbiont-mediated anti-pathogen protection, which seems to be driven mechanistically by both improved sanitary behaviours and an upregulated immune system. Ants with high Laboulbenia levels showed significantly longer self-grooming and elevated expression of immune genes relevant for wound repair and antifungal responses (β-1,3-glucan binding protein, Prophenoloxidase), compared with ants carrying low Laboulbenia levels. This suggests that the ectosymbiont Laboulbenia formicarum weakens its ant host by either direct resource exploitation or the costs of an upregulated behavioural and immunological response, which, however, provides a prophylactic protection upon later exposure to pathogens. ","lang":"eng"}],"acknowledged_ssus":[{"_id":"EM-Fac"}],"corr_author":"1","fulldoi":"https://doi.org/10.1098/rspb.2014.1976","ec_funded":1,"publication_identifier":{"eissn":["1471-2954"],"issn":["0962-8452"]},"project":[{"_id":"25DC711C-B435-11E9-9278-68D0E5697425","name":"Social Vaccination in Ant Colonies: from Individual Mechanisms to Society Effects","grant_number":"243071","call_identifier":"FP7"},{"grant_number":"CR-118/3-1","name":"Host-Parasite Coevolution","_id":"25DAF0B2-B435-11E9-9278-68D0E5697425"}],"publication":"Proceedings of the Royal Society of London Series B Biological Sciences","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","relation":"research_data","id":"9740"}]},"quality_controlled":"1","type":"journal_article","publication_status":"published","doi":"10.1098/rspb.2014.1976","scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","external_id":{"isi":["000345624600008"],"pmid":["25473011"]},"article_type":"original","_id":"1993","publisher":"The Royal Society","citation":{"ieee":"M. Konrad, A. V. Grasse, S. Tragust, and S. Cremer, “Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host,” <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>, vol. 282, no. 1799. The Royal Society, 2015.","chicago":"Konrad, Matthias, Anna V Grasse, Simon Tragust, and Sylvia Cremer. “Anti-Pathogen Protection versus Survival Costs Mediated by an Ectosymbiont in an Ant Host.” <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>. The Royal Society, 2015. <a href=\"https://doi.org/10.1098/rspb.2014.1976\">https://doi.org/10.1098/rspb.2014.1976</a>.","mla":"Konrad, Matthias, et al. “Anti-Pathogen Protection versus Survival Costs Mediated by an Ectosymbiont in an Ant Host.” <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>, vol. 282, no. 1799, 20141976, The Royal Society, 2015, doi:<a href=\"https://doi.org/10.1098/rspb.2014.1976\">10.1098/rspb.2014.1976</a>.","ista":"Konrad M, Grasse AV, Tragust S, Cremer S. 2015. Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host. Proceedings of the Royal Society of London Series B Biological Sciences. 282(1799), 20141976.","ama":"Konrad M, Grasse AV, Tragust S, Cremer S. Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host. <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>. 2015;282(1799). doi:<a href=\"https://doi.org/10.1098/rspb.2014.1976\">10.1098/rspb.2014.1976</a>","apa":"Konrad, M., Grasse, A. V., Tragust, S., &#38; Cremer, S. (2015). Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host. <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>. The Royal Society. <a href=\"https://doi.org/10.1098/rspb.2014.1976\">https://doi.org/10.1098/rspb.2014.1976</a>","short":"M. Konrad, A.V. Grasse, S. Tragust, S. Cremer, Proceedings of the Royal Society of London Series B Biological Sciences 282 (2015)."},"volume":282,"article_processing_charge":"No","date_created":"2018-12-11T11:55:06Z","status":"public","pmid":1,"title":"Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host","intvolume":"       282","oa":1,"author":[{"full_name":"Konrad, Matthias","last_name":"Konrad","id":"46528076-F248-11E8-B48F-1D18A9856A87","first_name":"Matthias"},{"first_name":"Anna V","full_name":"Grasse, Anna V","id":"406F989C-F248-11E8-B48F-1D18A9856A87","last_name":"Grasse"},{"full_name":"Tragust, Simon","last_name":"Tragust","id":"35A7A418-F248-11E8-B48F-1D18A9856A87","first_name":"Simon"},{"orcid":"0000-0002-2193-3868","first_name":"Sylvia","last_name":"Cremer","id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87","full_name":"Cremer, Sylvia"}],"acknowledgement":"Funding was obtained by the German Research Foundation (CR 118–2) and an ERC StG (243071) by the European Research Council (both to S.C.).\r\nWe thank Line V. Ugelvig for help with ant collection and statistical discussion, Xavier Espadaler for detailed information on the ant collection site, Birgit Lautenschläger for the electron microscopy images and Eva Sixt for ant drawings. We further thank Jørgen Eilenberg for the fungal strain, Meghan L. Vyleta for genetic strain characterization and immune gene primer development, Paul Schmid-Hempel for discussion, and Line V. Ugelvig, Xavier Espadaler and Christopher D. Pull for comments on the manuscript. S.C., M.K. and S.T. conceived the study; M.K. and A.V.G. performed the experiments; M.K. performed the statistical analysis; S.C. and M.K. wrote the manuscript with intense contributions of A.V.G. and S.T.; all authors approved the manuscript.","year":"2015","oa_version":"Submitted Version","date_updated":"2025-09-23T07:55:03Z","article_number":"20141976","publist_id":"5090","department":[{"_id":"SyCr"}],"month":"01","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4286035/","open_access":"1"}],"isi":1,"issue":"1799"},{"publisher":"Elsevier","article_processing_charge":"No","volume":"68/Part 2","date_created":"2018-12-11T11:55:07Z","citation":{"chicago":"Noren, Patrik. “The Three-State Toric Homogeneous Markov Chain Model Has Markov Degree Two.” <i>Journal of Symbolic Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.jsc.2014.09.014\">https://doi.org/10.1016/j.jsc.2014.09.014</a>.","ieee":"P. Noren, “The three-state toric homogeneous Markov chain model has Markov degree two,” <i>Journal of Symbolic Computation</i>, vol. 68/Part 2, no. May-June. Elsevier, pp. 285–296, 2015.","short":"P. Noren, Journal of Symbolic Computation 68/Part 2 (2015) 285–296.","apa":"Noren, P. (2015). The three-state toric homogeneous Markov chain model has Markov degree two. <i>Journal of Symbolic Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jsc.2014.09.014\">https://doi.org/10.1016/j.jsc.2014.09.014</a>","mla":"Noren, Patrik. “The Three-State Toric Homogeneous Markov Chain Model Has Markov Degree Two.” <i>Journal of Symbolic Computation</i>, vol. 68/Part 2, no. May-June, Elsevier, 2015, pp. 285–96, doi:<a href=\"https://doi.org/10.1016/j.jsc.2014.09.014\">10.1016/j.jsc.2014.09.014</a>.","ista":"Noren P. 2015. The three-state toric homogeneous Markov chain model has Markov degree two. Journal of Symbolic Computation. 68/Part 2(May-June), 285–296.","ama":"Noren P. The three-state toric homogeneous Markov chain model has Markov degree two. <i>Journal of Symbolic Computation</i>. 2015;68/Part 2(May-June):285-296. doi:<a href=\"https://doi.org/10.1016/j.jsc.2014.09.014\">10.1016/j.jsc.2014.09.014</a>"},"external_id":{"isi":["000347767600016"],"arxiv":["1207.0077"]},"_id":"1997","title":"The three-state toric homogeneous Markov chain model has Markov degree two","oa":1,"status":"public","arxiv":1,"date_updated":"2025-09-23T14:17:34Z","publist_id":"5082","author":[{"first_name":"Patrik","id":"46870C74-F248-11E8-B48F-1D18A9856A87","last_name":"Noren","full_name":"Noren, Patrik"}],"oa_version":"Preprint","year":"2015","issue":"May-June","department":[{"_id":"CaUh"}],"month":"05","main_file_link":[{"url":"http://arxiv.org/abs/1207.0077","open_access":"1"}],"isi":1,"day":"01","abstract":[{"lang":"eng","text":"We prove that the three-state toric homogeneous Markov chain model has Markov degree two. In algebraic terminology this means, that a certain class of toric ideals is generated by quadratic binomials. This was conjectured by Haws, Martin del Campo, Takemura and Yoshida, who proved that they are generated by degree six binomials."}],"date_published":"2015-05-01T00:00:00Z","page":"285 - 296","corr_author":"1","fulldoi":"https://doi.org/10.1016/j.jsc.2014.09.014","language":[{"iso":"eng"}],"publication":"Journal of Symbolic Computation","doi":"10.1016/j.jsc.2014.09.014","scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","type":"journal_article","publication_status":"published"},{"day":"23","abstract":[{"text":"The monotone secant conjecture posits a rich class of polynomial systems, all of whose solutions are real. These systems come from the Schubert calculus on flag manifolds, and the monotone secant conjecture is a compelling generalization of the Shapiro conjecture for Grassmannians (Theorem of Mukhin, Tarasov, and Varchenko). We present some theoretical evidence for this conjecture, as well as computational evidence obtained by 1.9 teraHertz-years of computing, and we discuss some of the phenomena we observed in our data. ","lang":"eng"}],"date_published":"2015-06-23T00:00:00Z","page":"261 - 269","fulldoi":"https://doi.org/10.1080/10586458.2014.980044","language":[{"iso":"eng"}],"publication":"Experimental Mathematics","scopus_import":"1","doi":"10.1080/10586458.2014.980044","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published","quality_controlled":"1","type":"journal_article","publisher":"Taylor & Francis","citation":{"mla":"Hein, Nicolas, et al. “The Monotone Secant Conjecture in the Real Schubert Calculus.” <i>Experimental Mathematics</i>, vol. 24, no. 3, Taylor &#38; Francis, 2015, pp. 261–69, doi:<a href=\"https://doi.org/10.1080/10586458.2014.980044\">10.1080/10586458.2014.980044</a>.","ista":"Hein N, Hillar C, Martin del Campo Sanchez A, Sottile F, Teitler Z. 2015. The monotone secant conjecture in the real Schubert calculus. Experimental Mathematics. 24(3), 261–269.","ama":"Hein N, Hillar C, Martin del Campo Sanchez A, Sottile F, Teitler Z. The monotone secant conjecture in the real Schubert calculus. <i>Experimental Mathematics</i>. 2015;24(3):261-269. doi:<a href=\"https://doi.org/10.1080/10586458.2014.980044\">10.1080/10586458.2014.980044</a>","short":"N. Hein, C. Hillar, A. Martin del Campo Sanchez, F. Sottile, Z. Teitler, Experimental Mathematics 24 (2015) 261–269.","apa":"Hein, N., Hillar, C., Martin del Campo Sanchez, A., Sottile, F., &#38; Teitler, Z. (2015). The monotone secant conjecture in the real Schubert calculus. <i>Experimental Mathematics</i>. Taylor &#38; Francis. <a href=\"https://doi.org/10.1080/10586458.2014.980044\">https://doi.org/10.1080/10586458.2014.980044</a>","ieee":"N. Hein, C. Hillar, A. Martin del Campo Sanchez, F. Sottile, and Z. Teitler, “The monotone secant conjecture in the real Schubert calculus,” <i>Experimental Mathematics</i>, vol. 24, no. 3. Taylor &#38; Francis, pp. 261–269, 2015.","chicago":"Hein, Nicolas, Christopher Hillar, Abraham Martin del Campo Sanchez, Frank Sottile, and Zach Teitler. “The Monotone Secant Conjecture in the Real Schubert Calculus.” <i>Experimental Mathematics</i>. Taylor &#38; Francis, 2015. <a href=\"https://doi.org/10.1080/10586458.2014.980044\">https://doi.org/10.1080/10586458.2014.980044</a>."},"volume":24,"article_processing_charge":"No","date_created":"2018-12-11T11:55:10Z","external_id":{"arxiv":["1109.3436"],"isi":["000356873900001"]},"_id":"2006","oa":1,"title":"The monotone secant conjecture in the real Schubert calculus","intvolume":"        24","arxiv":1,"status":"public","publist_id":"5070","date_updated":"2025-09-23T14:07:49Z","author":[{"last_name":"Hein","full_name":"Hein, Nicolas","first_name":"Nicolas"},{"full_name":"Hillar, Christopher","last_name":"Hillar","first_name":"Christopher"},{"first_name":"Abraham","full_name":"Martin Del Campo Sanchez, Abraham","id":"4CF47F6A-F248-11E8-B48F-1D18A9856A87","last_name":"Martin Del Campo Sanchez"},{"last_name":"Sottile","full_name":"Sottile, Frank","first_name":"Frank"},{"full_name":"Teitler, Zach","last_name":"Teitler","first_name":"Zach"}],"oa_version":"Preprint","year":"2015","issue":"3","department":[{"_id":"CaUh"}],"isi":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1109.3436"}],"month":"06"},{"issue":"3","isi":1,"main_file_link":[{"url":"http://arxiv.org/abs/1307.3282","open_access":"1"}],"month":"09","department":[{"_id":"CaUh"}],"publist_id":"5068","date_updated":"2025-09-23T09:25:01Z","year":"2015","oa_version":"Preprint","author":[{"full_name":"Klimova, Anna","id":"31934120-F248-11E8-B48F-1D18A9856A87","last_name":"Klimova","first_name":"Anna"},{"first_name":"Tamás","last_name":"Rudas","full_name":"Rudas, Tamás"}],"acknowledgement":"Part of the material presented here was contained in the PhD thesis of the first author to which the second author and Thomas Richardson were advisers. The authors wish to thank him for several comments and suggestions. We also thank the reviewers and the Associate Editor for helpful comments. The proof of Proposition 1 uses the idea of Olga Klimova, to whom the authors are also indebted. The second author was supported in part by Grant K-106154 from the Hungarian National Scientific Research Fund (OTKA).","oa":1,"title":"Iterative scaling in curved exponential families","intvolume":"        42","arxiv":1,"status":"public","article_processing_charge":"No","citation":{"ama":"Klimova A, Rudas T. Iterative scaling in curved exponential families. <i>Scandinavian Journal of Statistics</i>. 2015;42(3):832-847. doi:<a href=\"https://doi.org/10.1111/sjos.12139\">10.1111/sjos.12139</a>","mla":"Klimova, Anna, and Tamás Rudas. “Iterative Scaling in Curved Exponential Families.” <i>Scandinavian Journal of Statistics</i>, vol. 42, no. 3, Wiley, 2015, pp. 832–47, doi:<a href=\"https://doi.org/10.1111/sjos.12139\">10.1111/sjos.12139</a>.","ista":"Klimova A, Rudas T. 2015. Iterative scaling in curved exponential families. Scandinavian Journal of Statistics. 42(3), 832–847.","apa":"Klimova, A., &#38; Rudas, T. (2015). Iterative scaling in curved exponential families. <i>Scandinavian Journal of Statistics</i>. Wiley. <a href=\"https://doi.org/10.1111/sjos.12139\">https://doi.org/10.1111/sjos.12139</a>","short":"A. Klimova, T. Rudas, Scandinavian Journal of Statistics 42 (2015) 832–847.","ieee":"A. Klimova and T. Rudas, “Iterative scaling in curved exponential families,” <i>Scandinavian Journal of Statistics</i>, vol. 42, no. 3. Wiley, pp. 832–847, 2015.","chicago":"Klimova, Anna, and Tamás Rudas. “Iterative Scaling in Curved Exponential Families.” <i>Scandinavian Journal of Statistics</i>. Wiley, 2015. <a href=\"https://doi.org/10.1111/sjos.12139\">https://doi.org/10.1111/sjos.12139</a>."},"volume":42,"date_created":"2018-12-11T11:55:11Z","publisher":"Wiley","_id":"2008","external_id":{"arxiv":["1307.3282"],"isi":["000360077100012"]},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","scopus_import":"1","doi":"10.1111/sjos.12139","publication_status":"published","quality_controlled":"1","type":"journal_article","language":[{"iso":"eng"}],"publication":"Scandinavian Journal of Statistics","fulldoi":"https://doi.org/10.1111/sjos.12139","abstract":[{"text":"The paper describes a generalized iterative proportional fitting procedure that can be used for maximum likelihood estimation in a special class of the general log-linear model. The models in this class, called relational, apply to multivariate discrete sample spaces that do not necessarily have a Cartesian product structure and may not contain an overall effect. When applied to the cell probabilities, the models without the overall effect are curved exponential families and the values of the sufficient statistics are reproduced by the MLE only up to a constant of proportionality. The paper shows that Iterative Proportional Fitting, Generalized Iterative Scaling, and Improved Iterative Scaling fail to work for such models. The algorithm proposed here is based on iterated Bregman projections. As a by-product, estimates of the multiplicative parameters are also obtained. An implementation of the algorithm is available as an R-package.","lang":"eng"}],"day":"01","page":"832 - 847","date_published":"2015-09-01T00:00:00Z"},{"publication":"Computational Statistics & Data Analysis","language":[{"iso":"eng"}],"quality_controlled":"1","type":"journal_article","publication_status":"published","doi":"10.1016/j.csda.2015.01.017","scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_published":"2015-07-01T00:00:00Z","page":"57 - 72","day":"01","abstract":[{"text":"The concepts of faithfulness and strong-faithfulness are important for statistical learning of graphical models. Graphs are not sufficient for describing the association structure of a discrete distribution. Hypergraphs representing hierarchical log-linear models are considered instead, and the concept of parametric (strong-) faithfulness with respect to a hypergraph is introduced. Strong-faithfulness ensures the existence of uniformly consistent parameter estimators and enables building uniformly consistent procedures for a hypergraph search. The strength of association in a discrete distribution can be quantified with various measures, leading to different concepts of strong-faithfulness. Lower and upper bounds for the proportions of distributions that do not satisfy strong-faithfulness are computed for different parameterizations and measures of association.","lang":"eng"}],"fulldoi":"https://doi.org/10.1016/j.csda.2015.01.017","corr_author":"1","author":[{"last_name":"Klimova","id":"31934120-F248-11E8-B48F-1D18A9856A87","full_name":"Klimova, Anna","first_name":"Anna"},{"first_name":"Caroline","orcid":"0000-0002-7008-0216","id":"49ADD78E-F248-11E8-B48F-1D18A9856A87","last_name":"Uhler","full_name":"Uhler, Caroline"},{"full_name":"Rudas, Tamás","last_name":"Rudas","first_name":"Tamás"}],"year":"2015","oa_version":"Preprint","date_updated":"2025-09-23T08:45:54Z","publist_id":"5062","department":[{"_id":"CaUh"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1404.6617"}],"month":"07","isi":1,"issue":"7","external_id":{"isi":["000352661000005"],"arxiv":["1404.6617"]},"_id":"2014","publisher":"Elsevier","volume":87,"article_processing_charge":"No","date_created":"2018-12-11T11:55:13Z","citation":{"ista":"Klimova A, Uhler C, Rudas T. 2015. Faithfulness and learning hypergraphs from discrete distributions. Computational Statistics &#38; Data Analysis. 87(7), 57–72.","ama":"Klimova A, Uhler C, Rudas T. Faithfulness and learning hypergraphs from discrete distributions. <i>Computational Statistics &#38; Data Analysis</i>. 2015;87(7):57-72. doi:<a href=\"https://doi.org/10.1016/j.csda.2015.01.017\">10.1016/j.csda.2015.01.017</a>","mla":"Klimova, Anna, et al. “Faithfulness and Learning Hypergraphs from Discrete Distributions.” <i>Computational Statistics &#38; Data Analysis</i>, vol. 87, no. 7, Elsevier, 2015, pp. 57–72, doi:<a href=\"https://doi.org/10.1016/j.csda.2015.01.017\">10.1016/j.csda.2015.01.017</a>.","apa":"Klimova, A., Uhler, C., &#38; Rudas, T. (2015). Faithfulness and learning hypergraphs from discrete distributions. <i>Computational Statistics &#38; Data Analysis</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.csda.2015.01.017\">https://doi.org/10.1016/j.csda.2015.01.017</a>","short":"A. Klimova, C. Uhler, T. Rudas, Computational Statistics &#38; Data Analysis 87 (2015) 57–72.","ieee":"A. Klimova, C. Uhler, and T. Rudas, “Faithfulness and learning hypergraphs from discrete distributions,” <i>Computational Statistics &#38; Data Analysis</i>, vol. 87, no. 7. Elsevier, pp. 57–72, 2015.","chicago":"Klimova, Anna, Caroline Uhler, and Tamás Rudas. “Faithfulness and Learning Hypergraphs from Discrete Distributions.” <i>Computational Statistics &#38; Data Analysis</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.csda.2015.01.017\">https://doi.org/10.1016/j.csda.2015.01.017</a>."},"status":"public","arxiv":1,"title":"Faithfulness and learning hypergraphs from discrete distributions","intvolume":"        87","oa":1}]