[{"publication":"PLoS Computational Biology","language":[{"iso":"eng"}],"year":"2014","day":"02","author":[{"full_name":"Tkacik, Gasper","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","first_name":"Gasper","last_name":"Tkacik","orcid":"0000-0002-6699-1455"},{"full_name":"Marre, Olivier","last_name":"Marre","first_name":"Olivier"},{"full_name":"Amodei, Dario","last_name":"Amodei","first_name":"Dario"},{"full_name":"Schneidman, Elad","last_name":"Schneidman","first_name":"Elad"},{"full_name":"Bialek, William","last_name":"Bialek","first_name":"William"},{"last_name":"Berry","first_name":"Michael","full_name":"Berry, Michael"}],"date_published":"2014-01-02T00:00:00Z","volume":10,"abstract":[{"text":"Maximum entropy models are the least structured probability distributions that exactly reproduce a chosen set of statistics measured in an interacting network. Here we use this principle to construct probabilistic models which describe the correlated spiking activity of populations of up to 120 neurons in the salamander retina as it responds to natural movies. Already in groups as small as 10 neurons, interactions between spikes can no longer be regarded as small perturbations in an otherwise independent system; for 40 or more neurons pairwise interactions need to be supplemented by a global interaction that controls the distribution of synchrony in the population. Here we show that such “K-pairwise” models—being systematic extensions of the previously used pairwise Ising models—provide an excellent account of the data. We explore the properties of the neural vocabulary by: 1) estimating its entropy, which constrains the population's capacity to represent visual information; 2) classifying activity patterns into a small set of metastable collective modes; 3) showing that the neural codeword ensembles are extremely inhomogenous; 4) demonstrating that the state of individual neurons is highly predictable from the rest of the population, allowing the capacity for error correction.","lang":"eng"}],"file_date_updated":"2020-07-14T12:45:35Z","issue":"1","date_created":"2018-12-11T11:56:36Z","scopus_import":1,"main_file_link":[{"url":"http://repository.ist.ac.at/id/eprint/436","open_access":"1"}],"publisher":"Public Library of Science","file":[{"file_id":"4965","date_created":"2018-12-12T10:12:46Z","creator":"system","relation":"main_file","checksum":"c720222c5e924a4acb17f23b9381a6ca","date_updated":"2020-07-14T12:45:35Z","content_type":"application/pdf","file_name":"IST-2016-436-v1+1_journal.pcbi.1003408.pdf","access_level":"open_access","file_size":2194790}],"oa":1,"publication_status":"published","publication_identifier":{"issn":["1553734X"]},"date_updated":"2024-02-21T13:46:14Z","ddc":["570"],"oa_version":"Published Version","month":"01","related_material":{"record":[{"id":"5562","relation":"popular_science","status":"public"}]},"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publist_id":"4689","article_number":"e1003408","has_accepted_license":"1","quality_controlled":"1","acknowledgement":"\r\n\r\n\r\n\r\nThis work was funded by NSF grant IIS-0613435, NSF grant PHY-0957573, NSF grant CCF-0939370, NIH grant R01 EY14196, NIH grant P50 GM071508, the Fannie and John Hertz Foundation, the Swartz Foundation, the WM Keck Foundation, ANR Optima and the French State program “Investissements d'Avenir” [LIFESENSES: ANR-10-LABX-65], and the Austrian Research Foundation FWF P25651.","department":[{"_id":"GaTk"}],"doi":"10.1371/journal.pcbi.1003408","intvolume":"        10","_id":"2257","license":"https://creativecommons.org/licenses/by/4.0/","title":"Searching for collective behavior in a large network of sensory neurons","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"pubrep_id":"436","type":"journal_article","status":"public","citation":{"short":"G. Tkačik, O. Marre, D. Amodei, E. Schneidman, W. Bialek, M. Berry, PLoS Computational Biology 10 (2014).","ama":"Tkačik G, Marre O, Amodei D, Schneidman E, Bialek W, Berry M. Searching for collective behavior in a large network of sensory neurons. <i>PLoS Computational Biology</i>. 2014;10(1). doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1003408\">10.1371/journal.pcbi.1003408</a>","chicago":"Tkačik, Gašper, Olivier Marre, Dario Amodei, Elad Schneidman, William Bialek, and Michael Berry. “Searching for Collective Behavior in a Large Network of Sensory Neurons.” <i>PLoS Computational Biology</i>. Public Library of Science, 2014. <a href=\"https://doi.org/10.1371/journal.pcbi.1003408\">https://doi.org/10.1371/journal.pcbi.1003408</a>.","mla":"Tkačik, Gašper, et al. “Searching for Collective Behavior in a Large Network of Sensory Neurons.” <i>PLoS Computational Biology</i>, vol. 10, no. 1, e1003408, Public Library of Science, 2014, doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1003408\">10.1371/journal.pcbi.1003408</a>.","apa":"Tkačik, G., Marre, O., Amodei, D., Schneidman, E., Bialek, W., &#38; Berry, M. (2014). Searching for collective behavior in a large network of sensory neurons. <i>PLoS Computational Biology</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pcbi.1003408\">https://doi.org/10.1371/journal.pcbi.1003408</a>","ieee":"G. Tkačik, O. Marre, D. Amodei, E. Schneidman, W. Bialek, and M. Berry, “Searching for collective behavior in a large network of sensory neurons,” <i>PLoS Computational Biology</i>, vol. 10, no. 1. Public Library of Science, 2014.","ista":"Tkačik G, Marre O, Amodei D, Schneidman E, Bialek W, Berry M. 2014. Searching for collective behavior in a large network of sensory neurons. PLoS Computational Biology. 10(1), e1003408."}},{"citation":{"mla":"Zhu, Fangfang, et al. “DICE, an Efficient System for Iterative Genomic Editing in Human Pluripotent Stem Cells.” <i>Nucleic Acids Research</i>, vol. 42, no. 5, e34, Oxford University Press, 2014, doi:<a href=\"https://doi.org/10.1093/nar/gkt1290\">10.1093/nar/gkt1290</a>.","apa":"Zhu, F., Gamboa, M., Farruggio, A., Hippenmeyer, S., Tasic, B., Schüle, B., … Calos, M. (2014). DICE, an efficient system for iterative genomic editing in human pluripotent stem cells. <i>Nucleic Acids Research</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/nar/gkt1290\">https://doi.org/10.1093/nar/gkt1290</a>","ama":"Zhu F, Gamboa M, Farruggio A, et al. DICE, an efficient system for iterative genomic editing in human pluripotent stem cells. <i>Nucleic Acids Research</i>. 2014;42(5). doi:<a href=\"https://doi.org/10.1093/nar/gkt1290\">10.1093/nar/gkt1290</a>","chicago":"Zhu, Fangfang, Matthew Gamboa, Alfonso Farruggio, Simon Hippenmeyer, Bosiljka Tasic, Birgitt Schüle, Yanru Chen Tsai, and Michele Calos. “DICE, an Efficient System for Iterative Genomic Editing in Human Pluripotent Stem Cells.” <i>Nucleic Acids Research</i>. Oxford University Press, 2014. <a href=\"https://doi.org/10.1093/nar/gkt1290\">https://doi.org/10.1093/nar/gkt1290</a>.","short":"F. Zhu, M. Gamboa, A. Farruggio, S. Hippenmeyer, B. Tasic, B. Schüle, Y. Chen Tsai, M. Calos, Nucleic Acids Research 42 (2014).","ista":"Zhu F, Gamboa M, Farruggio A, Hippenmeyer S, Tasic B, Schüle B, Chen Tsai Y, Calos M. 2014. DICE, an efficient system for iterative genomic editing in human pluripotent stem cells. Nucleic Acids Research. 42(5), e34.","ieee":"F. Zhu <i>et al.</i>, “DICE, an efficient system for iterative genomic editing in human pluripotent stem cells,” <i>Nucleic Acids Research</i>, vol. 42, no. 5. Oxford University Press, 2014."},"pubrep_id":"961","status":"public","type":"journal_article","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"title":"DICE, an efficient system for iterative genomic editing in human pluripotent stem cells","intvolume":"        42","_id":"2261","doi":"10.1093/nar/gkt1290","department":[{"_id":"SiHi"}],"quality_controlled":"1","acknowledgement":"California Institute for Regenerative Medicine [RT2-01880 and TR2-01756]. Funding for open access charge: California Institute for Regenerative Medicine [RT2-01880 and TR2-01756]\r\nCC BY 3,0","has_accepted_license":"1","article_number":"e34","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"4684","month":"03","oa_version":"Preprint","ddc":["571","610"],"date_updated":"2021-01-12T06:56:22Z","publication_status":"published","oa":1,"publisher":"Oxford University Press","file":[{"file_name":"IST-2018-961-v1+1_2014_Hippenmeyer_DICE.pdf","file_size":11044478,"access_level":"open_access","date_updated":"2020-07-14T12:45:35Z","content_type":"application/pdf","date_created":"2018-12-12T10:09:15Z","creator":"system","checksum":"e9268f5f96a820f04d7ebbf85927c3cb","relation":"main_file","file_id":"4738"}],"scopus_import":1,"date_created":"2018-12-11T11:56:38Z","issue":"5","file_date_updated":"2020-07-14T12:45:35Z","date_published":"2014-03-05T00:00:00Z","volume":42,"abstract":[{"text":"To reveal the full potential of human pluripotent stem cells, new methods for rapid, site-specific genomic engineering are needed. Here, we describe a system for precise genetic modification of human embryonic stem cells (ESCs) and induced pluripotent stem cells (iPSCs). We identified a novel human locus, H11, located in a safe, intergenic, transcriptionally active region of chromosome 22, as the recipient site, to provide robust, ubiquitous expression of inserted genes. Recipient cell lines were established by site-specific placement of a ‘landing pad’ cassette carrying attP sites for phiC31 and Bxb1 integrases at the H11 locus by spontaneous or TALEN-assisted homologous recombination. Dual integrase cassette exchange (DICE) mediated by phiC31 and Bxb1 integrases was used to insert genes of interest flanked by phiC31 and Bxb1 attB sites at the H11 locus, replacing the landing pad. This system provided complete control over content, direction and copy number of inserted genes, with a specificity of 100%. A series of genes, including mCherry and various combinations of the neural transcription factors LMX1a, FOXA2 and OTX2, were inserted in recipient cell lines derived from H9 ESC, as well as iPSC lines derived from a Parkinson’s disease patient and a normal sibling control. The DICE system offers rapid, efficient and precise gene insertion in ESC and iPSC and is particularly well suited for repeated modifications of the same locus.","lang":"eng"}],"author":[{"full_name":"Zhu, Fangfang","last_name":"Zhu","first_name":"Fangfang"},{"full_name":"Gamboa, Matthew","last_name":"Gamboa","first_name":"Matthew"},{"first_name":"Alfonso","last_name":"Farruggio","full_name":"Farruggio, Alfonso"},{"orcid":"0000-0003-2279-1061","last_name":"Hippenmeyer","first_name":"Simon","id":"37B36620-F248-11E8-B48F-1D18A9856A87","full_name":"Hippenmeyer, Simon"},{"first_name":"Bosiljka","last_name":"Tasic","full_name":"Tasic, Bosiljka"},{"first_name":"Birgitt","last_name":"Schüle","full_name":"Schüle, Birgitt"},{"first_name":"Yanru","last_name":"Chen Tsai","full_name":"Chen Tsai, Yanru"},{"last_name":"Calos","first_name":"Michele","full_name":"Calos, Michele"}],"language":[{"iso":"eng"}],"year":"2014","day":"05","publication":"Nucleic Acids Research"},{"intvolume":"       800","_id":"2265","page":"1 - 24","date_created":"2018-12-11T11:56:39Z","doi":"10.1007/978-94-007-7687-6_1","editor":[{"full_name":"Nguyen, Laurent","first_name":"Laurent","last_name":"Nguyen"}],"department":[{"_id":"SiHi"}],"quality_controlled":"1","citation":{"short":"S. Hippenmeyer, in:, L. Nguyen (Ed.),  Cellular and Molecular Control of Neuronal Migration, Springer, 2014, pp. 1–24.","ama":"Hippenmeyer S. Molecular pathways controlling the sequential steps of cortical projection neuron migration. In: Nguyen L, ed. <i> Cellular and Molecular Control of Neuronal Migration</i>. Vol 800. Springer; 2014:1-24. doi:<a href=\"https://doi.org/10.1007/978-94-007-7687-6_1\">10.1007/978-94-007-7687-6_1</a>","chicago":"Hippenmeyer, Simon. “Molecular Pathways Controlling the Sequential Steps of Cortical Projection Neuron Migration.” In <i> Cellular and Molecular Control of Neuronal Migration</i>, edited by Laurent Nguyen, 800:1–24. Springer, 2014. <a href=\"https://doi.org/10.1007/978-94-007-7687-6_1\">https://doi.org/10.1007/978-94-007-7687-6_1</a>.","apa":"Hippenmeyer, S. (2014). Molecular pathways controlling the sequential steps of cortical projection neuron migration. In L. Nguyen (Ed.), <i> Cellular and Molecular Control of Neuronal Migration</i> (Vol. 800, pp. 1–24). Springer. <a href=\"https://doi.org/10.1007/978-94-007-7687-6_1\">https://doi.org/10.1007/978-94-007-7687-6_1</a>","mla":"Hippenmeyer, Simon. “Molecular Pathways Controlling the Sequential Steps of Cortical Projection Neuron Migration.” <i> Cellular and Molecular Control of Neuronal Migration</i>, edited by Laurent Nguyen, vol. 800, Springer, 2014, pp. 1–24, doi:<a href=\"https://doi.org/10.1007/978-94-007-7687-6_1\">10.1007/978-94-007-7687-6_1</a>.","ieee":"S. Hippenmeyer, “Molecular pathways controlling the sequential steps of cortical projection neuron migration,” in <i> Cellular and Molecular Control of Neuronal Migration</i>, vol. 800, L. Nguyen, Ed. Springer, 2014, pp. 1–24.","ista":"Hippenmeyer S. 2014.Molecular pathways controlling the sequential steps of cortical projection neuron migration. In:  Cellular and Molecular Control of Neuronal Migration. Advances in Experimental Medicine and Biology, vol. 800, 1–24."},"publisher":"Springer","type":"book_chapter","status":"public","scopus_import":1,"title":"Molecular pathways controlling the sequential steps of cortical projection neuron migration","language":[{"iso":"eng"}],"year":"2014","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"4679","day":"01","oa_version":"None","publication":" Cellular and Molecular Control of Neuronal Migration","month":"01","date_updated":"2021-01-12T06:56:23Z","publication_status":"published","alternative_title":["Advances in Experimental Medicine and Biology"],"date_published":"2014-01-01T00:00:00Z","volume":800,"abstract":[{"lang":"eng","text":"Coordinated migration of newly-born neurons to their target territories is essential for correct neuronal circuit assembly in the developing brain. Although a cohort of signaling pathways has been implicated in the regulation of cortical projection neuron migration, the precise molecular mechanisms and how a balanced interplay of cell-autonomous and non-autonomous functions of candidate signaling molecules controls the discrete steps in the migration process, are just being revealed. In this chapter, I will focally review recent advances that improved our understanding of the cell-autonomous and possible cell-nonautonomous functions of the evolutionarily conserved LIS1/NDEL1-complex in regulating the sequential steps of cortical projection neuron migration. I will then elaborate on the emerging concept that the Reelin signaling pathway, acts exactly at precise stages in the course of cortical projection neuron migration. Lastly, I will discuss how finely tuned transcriptional programs and downstream effectors govern particular aspects in driving radial migration at discrete stages and how they regulate the precise positioning of cortical projection neurons in the developing cerebral cortex."}],"author":[{"id":"37B36620-F248-11E8-B48F-1D18A9856A87","full_name":"Hippenmeyer, Simon","last_name":"Hippenmeyer","first_name":"Simon","orcid":"0000-0003-2279-1061"}]},{"pubrep_id":"566","status":"public","type":"conference","title":"Partial enumeration and curvature regularization","citation":{"apa":"Olsson, C., Ulen, J., Boykov, Y., &#38; Kolmogorov, V. (2014). Partial enumeration and curvature regularization (pp. 2936–2943). Presented at the ICCV: International Conference on Computer Vision, Sydney, Australia: IEEE. <a href=\"https://doi.org/10.1109/ICCV.2013.365\">https://doi.org/10.1109/ICCV.2013.365</a>","mla":"Olsson, Carl, et al. <i>Partial Enumeration and Curvature Regularization</i>. IEEE, 2014, pp. 2936–43, doi:<a href=\"https://doi.org/10.1109/ICCV.2013.365\">10.1109/ICCV.2013.365</a>.","chicago":"Olsson, Carl, Johannes Ulen, Yuri Boykov, and Vladimir Kolmogorov. “Partial Enumeration and Curvature Regularization,” 2936–43. IEEE, 2014. <a href=\"https://doi.org/10.1109/ICCV.2013.365\">https://doi.org/10.1109/ICCV.2013.365</a>.","short":"C. Olsson, J. Ulen, Y. Boykov, V. Kolmogorov, in:, IEEE, 2014, pp. 2936–2943.","ama":"Olsson C, Ulen J, Boykov Y, Kolmogorov V. Partial enumeration and curvature regularization. In: IEEE; 2014:2936-2943. doi:<a href=\"https://doi.org/10.1109/ICCV.2013.365\">10.1109/ICCV.2013.365</a>","ista":"Olsson C, Ulen J, Boykov Y, Kolmogorov V. 2014. Partial enumeration and curvature regularization. ICCV: International Conference on Computer Vision, 2936–2943.","ieee":"C. Olsson, J. Ulen, Y. Boykov, and V. Kolmogorov, “Partial enumeration and curvature regularization,” presented at the ICCV: International Conference on Computer Vision, Sydney, Australia, 2014, pp. 2936–2943."},"department":[{"_id":"VlKo"}],"quality_controlled":"1","_id":"2275","page":"2936 - 2943","doi":"10.1109/ICCV.2013.365","has_accepted_license":"1","date_updated":"2021-01-12T06:56:28Z","ddc":["000"],"conference":{"location":"Sydney, Australia","name":"ICCV: International Conference on Computer Vision","start_date":"2013-12-01","end_date":"2013-12-08"},"oa":1,"publication_status":"published","publist_id":"4669","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"03","oa_version":"Submitted Version","scopus_import":1,"file":[{"date_created":"2018-12-12T10:09:30Z","creator":"system","relation":"main_file","checksum":"4a74b5c92d6dcd2348c2c10ec8dd18bf","file_id":"4754","file_name":"IST-2016-566-v1+1_iccv13_part_enumeration.pdf","access_level":"open_access","file_size":378601,"date_updated":"2020-07-14T12:45:36Z","content_type":"application/pdf"}],"publisher":"IEEE","date_created":"2018-12-11T11:56:42Z","date_published":"2014-03-03T00:00:00Z","abstract":[{"text":"Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. \r\nThis partial enumeration technique reduces complex high-order energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. \r\nOur main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach.\r\n","lang":"eng"}],"author":[{"last_name":"Olsson","first_name":"Carl","full_name":"Olsson, Carl"},{"first_name":"Johannes","last_name":"Ulen","full_name":"Ulen, Johannes"},{"full_name":"Boykov, Yuri","last_name":"Boykov","first_name":"Yuri"},{"first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"}],"file_date_updated":"2020-07-14T12:45:36Z","year":"2014","language":[{"iso":"eng"}],"day":"03"},{"day":"01","language":[{"iso":"eng"}],"year":"2014","publication":"Letters in Mathematical Physics","volume":104,"abstract":[{"text":"We consider two-dimensional Bose-Einstein condensates with attractive interaction, described by the Gross-Pitaevskii functional. Minimizers of this functional exist only if the interaction strength a satisfies {Mathematical expression}, where Q is the unique positive radial solution of {Mathematical expression} in {Mathematical expression}. We present a detailed analysis of the behavior of minimizers as a approaches a*, where all the mass concentrates at a global minimum of the trapping potential.","lang":"eng"}],"date_published":"2014-02-01T00:00:00Z","author":[{"full_name":"Guo, Yujin","first_name":"Yujin","last_name":"Guo"},{"full_name":"Seiringer, Robert","id":"4AFD0470-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6781-0521","last_name":"Seiringer","first_name":"Robert"}],"issue":"2","date_created":"2018-12-11T11:56:44Z","article_type":"original","scopus_import":"1","publisher":"Springer","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1301.5682"}],"date_updated":"2024-02-14T12:19:42Z","publication_status":"published","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"4653","month":"02","oa_version":"Preprint","arxiv":1,"department":[{"_id":"RoSe"}],"quality_controlled":"1","_id":"2281","page":"141 - 156","intvolume":"       104","doi":"10.1007/s11005-013-0667-9","external_id":{"arxiv":["1301.5682"]},"status":"public","type":"journal_article","title":"On the mass concentration for Bose-Einstein condensates with attractive interactions","citation":{"apa":"Guo, Y., &#38; Seiringer, R. (2014). On the mass concentration for Bose-Einstein condensates with attractive interactions. <i>Letters in Mathematical Physics</i>. Springer. <a href=\"https://doi.org/10.1007/s11005-013-0667-9\">https://doi.org/10.1007/s11005-013-0667-9</a>","mla":"Guo, Yujin, and Robert Seiringer. “On the Mass Concentration for Bose-Einstein Condensates with Attractive Interactions.” <i>Letters in Mathematical Physics</i>, vol. 104, no. 2, Springer, 2014, pp. 141–56, doi:<a href=\"https://doi.org/10.1007/s11005-013-0667-9\">10.1007/s11005-013-0667-9</a>.","chicago":"Guo, Yujin, and Robert Seiringer. “On the Mass Concentration for Bose-Einstein Condensates with Attractive Interactions.” <i>Letters in Mathematical Physics</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s11005-013-0667-9\">https://doi.org/10.1007/s11005-013-0667-9</a>.","short":"Y. Guo, R. Seiringer, Letters in Mathematical Physics 104 (2014) 141–156.","ama":"Guo Y, Seiringer R. On the mass concentration for Bose-Einstein condensates with attractive interactions. <i>Letters in Mathematical Physics</i>. 2014;104(2):141-156. doi:<a href=\"https://doi.org/10.1007/s11005-013-0667-9\">10.1007/s11005-013-0667-9</a>","ieee":"Y. Guo and R. Seiringer, “On the mass concentration for Bose-Einstein condensates with attractive interactions,” <i>Letters in Mathematical Physics</i>, vol. 104, no. 2. Springer, pp. 141–156, 2014.","ista":"Guo Y, Seiringer R. 2014. On the mass concentration for Bose-Einstein condensates with attractive interactions. Letters in Mathematical Physics. 104(2), 141–156."},"article_processing_charge":"No"},{"title":"Morpho-physiological criteria divide dentate gyrus interneurons into classes","tmp":{"image":"/images/cc_by_nc.png","short":"CC BY-NC (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)"},"pubrep_id":"461","type":"journal_article","status":"public","citation":{"short":"J. Hosp, M. Strüber, Y. Yanagawa, K. Obata, I. Vida, P.M. Jonas, M. Bartos, Hippocampus 23 (2014) 189–203.","chicago":"Hosp, Jonas, Michael Strüber, Yuchio Yanagawa, Kunihiko Obata, Imre Vida, Peter M Jonas, and Marlene Bartos. “Morpho-Physiological Criteria Divide Dentate Gyrus Interneurons into Classes.” <i>Hippocampus</i>. Wiley-Blackwell, 2014. <a href=\"https://doi.org/10.1002/hipo.22214\">https://doi.org/10.1002/hipo.22214</a>.","ama":"Hosp J, Strüber M, Yanagawa Y, et al. Morpho-physiological criteria divide dentate gyrus interneurons into classes. <i>Hippocampus</i>. 2014;23(2):189-203. doi:<a href=\"https://doi.org/10.1002/hipo.22214\">10.1002/hipo.22214</a>","apa":"Hosp, J., Strüber, M., Yanagawa, Y., Obata, K., Vida, I., Jonas, P. M., &#38; Bartos, M. (2014). Morpho-physiological criteria divide dentate gyrus interneurons into classes. <i>Hippocampus</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1002/hipo.22214\">https://doi.org/10.1002/hipo.22214</a>","mla":"Hosp, Jonas, et al. “Morpho-Physiological Criteria Divide Dentate Gyrus Interneurons into Classes.” <i>Hippocampus</i>, vol. 23, no. 2, Wiley-Blackwell, 2014, pp. 189–203, doi:<a href=\"https://doi.org/10.1002/hipo.22214\">10.1002/hipo.22214</a>.","ieee":"J. Hosp <i>et al.</i>, “Morpho-physiological criteria divide dentate gyrus interneurons into classes,” <i>Hippocampus</i>, vol. 23, no. 2. Wiley-Blackwell, pp. 189–203, 2014.","ista":"Hosp J, Strüber M, Yanagawa Y, Obata K, Vida I, Jonas PM, Bartos M. 2014. Morpho-physiological criteria divide dentate gyrus interneurons into classes. Hippocampus. 23(2), 189–203."},"quality_controlled":"1","acknowledgement":"Funded by Deutsche Forschungsgemeinschaft. Grant Numbers: SFB 505, SFB 780, BA1582/2-1 Excellence Initiative of the German Research Foundation (Spemann Graduate School). Grant Number: GSC-4 Lichtenberg Professorship-Award (VW-Foundation); Schram-Foundation; Excellence Initiative Brain Links-Brain Tools. The authors thank Drs. Jonas-Frederic Sauer and Claudio Elgueta for critically reading the manuscript. They also thank Karin Winterhalter, Margit Northemann and Ulrich Nöller for technical assistance.","department":[{"_id":"PeJo"}],"doi":"10.1002/hipo.22214","intvolume":"        23","license":"https://creativecommons.org/licenses/by-nc/4.0/","_id":"2285","page":"189 - 203","has_accepted_license":"1","publication_status":"published","oa":1,"ddc":["570"],"date_updated":"2021-01-12T06:56:32Z","oa_version":"Published Version","month":"02","user_id":"3FFCCD3A-F248-11E8-B48F-1D18A9856A87","publist_id":"4646","scopus_import":1,"file":[{"checksum":"ff6bc75a79dbc985a2e31b79253e6444","relation":"main_file","date_created":"2018-12-12T10:15:54Z","creator":"system","file_id":"5178","access_level":"open_access","file_size":801589,"file_name":"IST-2016-461-v1+1_Hosp_et_al-2014-Hippocampus.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:45:37Z"}],"publisher":"Wiley-Blackwell","date_created":"2018-12-11T11:56:46Z","author":[{"last_name":"Hosp","first_name":"Jonas","full_name":"Hosp, Jonas"},{"last_name":"Strüber","first_name":"Michael","full_name":"Strüber, Michael"},{"full_name":"Yanagawa, Yuchio","last_name":"Yanagawa","first_name":"Yuchio"},{"full_name":"Obata, Kunihiko","last_name":"Obata","first_name":"Kunihiko"},{"last_name":"Vida","first_name":"Imre","full_name":"Vida, Imre"},{"full_name":"Jonas, Peter M","id":"353C1B58-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5001-4804","last_name":"Jonas","first_name":"Peter M"},{"last_name":"Bartos","first_name":"Marlene","full_name":"Bartos, Marlene"}],"date_published":"2014-02-01T00:00:00Z","abstract":[{"text":"GABAergic inhibitory interneurons control fundamental aspects of neuronal network function. Their functional roles are assumed to be defined by the identity of their input synapses, the architecture of their dendritic tree, the passive and active membrane properties and finally the nature of their postsynaptic targets. Indeed, interneurons display a high degree of morphological and physiological heterogeneity. However, whether their morphological and physiological characteristics are correlated and whether interneuron diversity can be described by a continuum of GABAergic cell types or by distinct classes has remained unclear. Here we perform a detailed morphological and physiological characterization of GABAergic cells in the dentate gyrus, the input region of the hippocampus. To achieve an unbiased and efficient sampling and classification we used knock-in mice expressing the enhanced green fluorescent protein (eGFP) in glutamate decarboxylase 67 (GAD67)-positive neurons and performed cluster analysis. We identified five interneuron classes, each of them characterized by a distinct set of anatomical and physiological parameters. Cross-correlation analysis further revealed a direct relation between morphological and physiological properties indicating that dentate gyrus interneurons fall into functionally distinct classes which may differentially control neuronal network activity.","lang":"eng"}],"volume":23,"file_date_updated":"2020-07-14T12:45:37Z","issue":"2","publication":"Hippocampus","year":"2014","language":[{"iso":"eng"}],"day":"01"},{"publication_identifier":{"eissn":["2191-5318"],"isbn":["9-783-3190-5956-3"],"issn":["2191-530X"],"eisbn":["9-783-3190-5957-0"]},"date_updated":"2022-03-04T07:47:54Z","publication_status":"published","language":[{"iso":"eng"}],"year":"2014","day":"01","related_material":{"link":[{"url":"https://koha.app.ist.ac.at/cgi-bin/koha/opac-detail.pl?biblionumber=356106","relation":"other","description":"available as eBook via catalog IST BookList"},{"description":"available via catalog IST BookList","relation":"other","url":"https://koha.app.ist.ac.at/cgi-bin/koha/opac-detail.pl?biblionumber=373842"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"None","month":"01","edition":"1","date_published":"2014-01-01T00:00:00Z","abstract":[{"text":"This monograph presents a short course in computational geometry and topology. In the first part the book covers Voronoi diagrams and Delaunay triangulations, then it presents the theory of alpha complexes which play a crucial role in biology. The central part of the book is the homology theory and their computation, including the theory of persistence which is indispensable for applications, e.g. shape reconstruction. The target audience comprises researchers and practitioners in mathematics, biology, neuroscience and computer science, but the book may also be beneficial to graduate students of these fields.","lang":"eng"}],"author":[{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"}],"alternative_title":["SpringerBriefs in Applied Sciences and Technology"],"place":"Cham","department":[{"_id":"HeEd"}],"quality_controlled":"1","page":"IX, 110","_id":"6853","date_created":"2019-09-06T09:22:33Z","doi":"10.1007/978-3-319-05957-0","type":"book","status":"public","series_title":"SpringerBriefs in Applied Sciences and Technology","title":"A Short Course in Computational Geometry and Topology","scopus_import":"1","article_processing_charge":"No","citation":{"ieee":"H. Edelsbrunner, <i>A Short Course in Computational Geometry and Topology</i>, 1st ed. Cham: Springer Nature, 2014.","ista":"Edelsbrunner H. 2014. A Short Course in Computational Geometry and Topology 1st ed., Cham: Springer Nature, IX, 110p.","short":"H. Edelsbrunner, A Short Course in Computational Geometry and Topology, 1st ed., Springer Nature, Cham, 2014.","ama":"Edelsbrunner H. <i>A Short Course in Computational Geometry and Topology</i>. 1st ed. Cham: Springer Nature; 2014. doi:<a href=\"https://doi.org/10.1007/978-3-319-05957-0\">10.1007/978-3-319-05957-0</a>","chicago":"Edelsbrunner, Herbert. <i>A Short Course in Computational Geometry and Topology</i>. 1st ed. SpringerBriefs in Applied Sciences and Technology. Cham: Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-319-05957-0\">https://doi.org/10.1007/978-3-319-05957-0</a>.","mla":"Edelsbrunner, Herbert. <i>A Short Course in Computational Geometry and Topology</i>. 1st ed., Springer Nature, 2014, doi:<a href=\"https://doi.org/10.1007/978-3-319-05957-0\">10.1007/978-3-319-05957-0</a>.","apa":"Edelsbrunner, H. (2014). <i>A Short Course in Computational Geometry and Topology</i> (1st ed.). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-319-05957-0\">https://doi.org/10.1007/978-3-319-05957-0</a>"},"publisher":"Springer Nature"},{"date_published":"2014-06-30T00:00:00Z","author":[{"first_name":"Kristóf","last_name":"Huszár","orcid":"0000-0002-5445-5057","full_name":"Huszár, Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal","first_name":"Michal","last_name":"Rolinek"}],"has_accepted_license":"1","file_date_updated":"2020-07-14T12:47:48Z","date_updated":"2020-07-14T23:11:45Z","ddc":["510"],"publication_status":"draft","oa":1,"day":"30","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2014","language":[{"iso":"eng"}],"month":"06","oa_version":"Published Version","type":"working_paper","status":"public","title":"Playful Math - An introduction to mathematical games","publisher":"IST Austria","file":[{"date_updated":"2020-07-14T12:47:48Z","content_type":"application/pdf","file_name":"2014_Playful_Math_Huszar.pdf","access_level":"open_access","file_size":511233,"file_id":"7039","creator":"dernst","date_created":"2019-11-18T15:57:51Z","checksum":"2b94e5e1f4c3fe8ab89b12806276fb09","relation":"main_file"}],"citation":{"ieee":"K. Huszár and M. Rolinek, <i>Playful Math - An introduction to mathematical games</i>. IST Austria.","ista":"Huszár K, Rolinek M. Playful Math - An introduction to mathematical games, IST Austria, 5p.","chicago":"Huszár, Kristóf, and Michal Rolinek. <i>Playful Math - An Introduction to Mathematical Games</i>. IST Austria, n.d.","short":"K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games, IST Austria, n.d.","ama":"Huszár K, Rolinek M. <i>Playful Math - An Introduction to Mathematical Games</i>. IST Austria","apa":"Huszár, K., &#38; Rolinek, M. (n.d.). <i>Playful Math - An introduction to mathematical games</i>. IST Austria.","mla":"Huszár, Kristóf, and Michal Rolinek. <i>Playful Math - An Introduction to Mathematical Games</i>. IST Austria."},"article_processing_charge":"No","department":[{"_id":"VlKo"},{"_id":"UlWa"}],"page":"5","_id":"7038","date_created":"2019-11-18T15:57:05Z"},{"month":"09","oa_version":"Published Version","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publist_id":"7352","oa":1,"publication_status":"published","date_updated":"2021-01-12T08:00:48Z","ddc":["576"],"has_accepted_license":"1","article_number":"0107518","doi":"10.1371/journal.pone.0107518","intvolume":"         9","_id":"468","quality_controlled":"1","acknowledgement":"The study was funded by the University of Vienna (Focus of Excellence grant), the Galápagos Conservation Trust, and the Ethologische Gesellschaft e.V.","department":[{"_id":"CampIT"}],"citation":{"mla":"Cimadom, Arno, et al. “Invasive Parasites Habitat Change and Heavy Rainfall Reduce Breeding Success in Darwin’s Finches.” <i>PLoS One</i>, vol. 9, no. 9, 0107518, Public Library of Science, 2014, doi:<a href=\"https://doi.org/10.1371/journal.pone.0107518\">10.1371/journal.pone.0107518</a>.","apa":"Cimadom, A., Ulloa, A., Meidl, P., Zöttl, M., Zöttl, E., Fessl, B., … Tebbich, S. (2014). Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin’s finches. <i>PLoS One</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0107518\">https://doi.org/10.1371/journal.pone.0107518</a>","ama":"Cimadom A, Ulloa A, Meidl P, et al. Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin’s finches. <i>PLoS One</i>. 2014;9(9). doi:<a href=\"https://doi.org/10.1371/journal.pone.0107518\">10.1371/journal.pone.0107518</a>","chicago":"Cimadom, Arno, Angel Ulloa, Patrick Meidl, Markus Zöttl, Elisabet Zöttl, Birgit Fessl, Erwin Nemeth, Michael Dvorak, Francesca Cunninghame, and Sabine Tebbich. “Invasive Parasites Habitat Change and Heavy Rainfall Reduce Breeding Success in Darwin’s Finches.” <i>PLoS One</i>. Public Library of Science, 2014. <a href=\"https://doi.org/10.1371/journal.pone.0107518\">https://doi.org/10.1371/journal.pone.0107518</a>.","short":"A. Cimadom, A. Ulloa, P. Meidl, M. Zöttl, E. Zöttl, B. Fessl, E. Nemeth, M. Dvorak, F. Cunninghame, S. Tebbich, PLoS One 9 (2014).","ieee":"A. Cimadom <i>et al.</i>, “Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin’s finches,” <i>PLoS One</i>, vol. 9, no. 9. Public Library of Science, 2014.","ista":"Cimadom A, Ulloa A, Meidl P, Zöttl M, Zöttl E, Fessl B, Nemeth E, Dvorak M, Cunninghame F, Tebbich S. 2014. Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin’s finches. PLoS One. 9(9), 0107518."},"title":"Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin's finches","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"pubrep_id":"954","status":"public","type":"journal_article","publication":"PLoS One","year":"2014","language":[{"iso":"eng"}],"day":"23","file_date_updated":"2020-07-14T12:46:34Z","issue":"9","author":[{"full_name":"Cimadom, Arno","first_name":"Arno","last_name":"Cimadom"},{"last_name":"Ulloa","first_name":"Angel","full_name":"Ulloa, Angel"},{"first_name":"Patrick","last_name":"Meidl","id":"4709BCE6-F248-11E8-B48F-1D18A9856A87","full_name":"Meidl, Patrick"},{"full_name":"Zöttl, Markus","last_name":"Zöttl","first_name":"Markus"},{"first_name":"Elisabet","last_name":"Zöttl","full_name":"Zöttl, Elisabet"},{"full_name":"Fessl, Birgit","last_name":"Fessl","first_name":"Birgit"},{"full_name":"Nemeth, Erwin","last_name":"Nemeth","first_name":"Erwin"},{"last_name":"Dvorak","first_name":"Michael","full_name":"Dvorak, Michael"},{"full_name":"Cunninghame, Francesca","last_name":"Cunninghame","first_name":"Francesca"},{"last_name":"Tebbich","first_name":"Sabine","full_name":"Tebbich, Sabine"}],"date_published":"2014-09-23T00:00:00Z","abstract":[{"lang":"eng","text":"Invasive alien parasites and pathogens are a growing threat to biodiversity worldwide, which can contribute to the extinction of endemic species. On the Galápagos Islands, the invasive parasitic fly Philornis downsi poses a major threat to the endemic avifauna. Here, we investigated the influence of this parasite on the breeding success of two Darwin's finch species, the warbler finch (Certhidea olivacea) and the sympatric small tree finch (Camarhynchus parvulus), on Santa Cruz Island in 2010 and 2012. While the population of the small tree finch appeared to be stable, the warbler finch has experienced a dramatic decline in population size on Santa Cruz Island since 1997. We aimed to identify whether warbler finches are particularly vulnerable during different stages of the breeding cycle. Contrary to our prediction, breeding success was lower in the small tree finch than in the warbler finch. In both species P. downsi had a strong negative impact on breeding success and our data suggest that heavy rain events also lowered the fledging success. On the one hand parents might be less efficient in compensating their chicks' energy loss due to parasitism as they might be less efficient in foraging on days of heavy rain. On the other hand, intense rainfalls might lead to increased humidity and more rapid cooling of the nests. In the case of the warbler finch we found that the control of invasive plant species with herbicides had a significant additive negative impact on the breeding success. It is very likely that the availability of insects (i.e. food abundance) is lower in such controlled areas, as herbicide usage led to the removal of the entire understory. Predation seems to be a minor factor in brood loss."}],"volume":9,"date_created":"2018-12-11T11:46:38Z","file":[{"date_updated":"2020-07-14T12:46:34Z","content_type":"application/pdf","file_name":"IST-2018-954-v1+1_2014_Meidl_Invasive_parasites.PDF","access_level":"open_access","file_size":489387,"file_id":"5103","date_created":"2018-12-12T10:14:48Z","creator":"system","checksum":"b24e7518ccd41effed0d7d9e2498f67f","relation":"main_file"}],"publisher":"Public Library of Science","scopus_import":1},{"citation":{"ista":"Aminof B, Rubin S. 2014. First cycle games. Electronic Proceedings in Theoretical Computer Science, EPTCS. SR: Strategic Reasoning, EPTCS, vol. 146, 83–90.","ieee":"B. Aminof and S. Rubin, “First cycle games,” in <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, Grenoble, France, 2014, vol. 146, pp. 83–90.","chicago":"Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” In <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, 146:83–90. Open Publishing Association, 2014. <a href=\"https://doi.org/10.4204/EPTCS.146.11\">https://doi.org/10.4204/EPTCS.146.11</a>.","ama":"Aminof B, Rubin S. First cycle games. In: <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>. Vol 146. Open Publishing Association; 2014:83-90. doi:<a href=\"https://doi.org/10.4204/EPTCS.146.11\">10.4204/EPTCS.146.11</a>","short":"B. Aminof, S. Rubin, in:, Electronic Proceedings in Theoretical Computer Science, EPTCS, Open Publishing Association, 2014, pp. 83–90.","apa":"Aminof, B., &#38; Rubin, S. (2014). First cycle games. In <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i> (Vol. 146, pp. 83–90). Grenoble, France: Open Publishing Association. <a href=\"https://doi.org/10.4204/EPTCS.146.11\">https://doi.org/10.4204/EPTCS.146.11</a>","mla":"Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, vol. 146, Open Publishing Association, 2014, pp. 83–90, doi:<a href=\"https://doi.org/10.4204/EPTCS.146.11\">10.4204/EPTCS.146.11</a>."},"pubrep_id":"952","status":"public","type":"conference","title":"First cycle games","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"intvolume":"       146","_id":"475","page":"83 - 90","doi":"10.4204/EPTCS.146.11","department":[{"_id":"KrCh"}],"quality_controlled":"1","alternative_title":["EPTCS"],"has_accepted_license":"1","publist_id":"7345","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","month":"04","date_updated":"2021-01-12T08:00:53Z","ddc":["004"],"conference":{"start_date":"2014-04-05","name":"SR: Strategic Reasoning","end_date":"2014-04-06","location":"Grenoble, France"},"publication_status":"published","oa":1,"publisher":"Open Publishing Association","file":[{"file_id":"5260","relation":"main_file","checksum":"4d7b4ab82980cca2b96ac7703992a8c8","date_created":"2018-12-12T10:17:08Z","creator":"system","content_type":"application/pdf","date_updated":"2020-07-14T12:46:35Z","access_level":"open_access","file_size":100115,"file_name":"IST-2018-952-v1+1_2014_Rubin_First_cycle.pdf"}],"scopus_import":1,"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF"},{"grant_number":"S11402-N23","call_identifier":"FWF","name":"Moderne Concurrency Paradigms","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"}],"date_created":"2018-12-11T11:46:41Z","file_date_updated":"2020-07-14T12:46:35Z","date_published":"2014-04-01T00:00:00Z","volume":146,"abstract":[{"lang":"eng","text":"First cycle games (FCG) are played on a finite graph by two players who push a token along the edges until a vertex is repeated, and a simple cycle is formed. The winner is determined by some fixed property Y of the sequence of labels of the edges (or nodes) forming this cycle. These games are traditionally of interest because of their connection with infinite-duration games such as parity and mean-payoff games. We study the memory requirements for winning strategies of FCGs and certain associated infinite duration games. We exhibit a simple FCG that is not memoryless determined (this corrects a mistake in Memoryless determinacy of parity and mean payoff games: a simple proof by Bj⋯orklund, Sandberg, Vorobyov (2004) that claims that FCGs for which Y is closed under cyclic permutations are memoryless determined). We show that θ (n)! memory (where n is the number of nodes in the graph), which is always sufficient, may be necessary to win some FCGs. On the other hand, we identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations, and both Y and its complement are closed under concatenation) that are sufficient to ensure that the corresponding FCGs and their associated infinite duration games are memoryless determined. We demonstrate that many games considered in the literature, such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE, solving some families of FCGs is PSPACE-hard. "}],"author":[{"full_name":"Aminof, Benjamin","id":"4A55BD00-F248-11E8-B48F-1D18A9856A87","first_name":"Benjamin","last_name":"Aminof"},{"last_name":"Rubin","first_name":"Sasha","full_name":"Rubin, Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87"}],"year":"2014","language":[{"iso":"eng"}],"day":"01","publication":"Electronic Proceedings in Theoretical Computer Science, EPTCS","ec_funded":1},{"issue":"3","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H"},{"full_name":"Krinninger, Sebastian","last_name":"Krinninger","first_name":"Sebastian"},{"last_name":"Nanongkai","first_name":"Danupon","full_name":"Nanongkai, Danupon"}],"abstract":[{"text":"Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP∩co-NP, but are not known to be in P. The existence of polynomial-time algorithms has been a major open problem for decades and apart from pseudopolynomial algorithms there is no algorithm that solves any non-trivial subclass in polynomial time. In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several worst-case instances on which previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting the graph structure does not necessarily help.","lang":"eng"}],"volume":70,"date_published":"2014-11-01T00:00:00Z","publication":"Algorithmica","day":"01","year":"2014","language":[{"iso":"eng"}],"ec_funded":1,"publisher":"Springer","main_file_link":[{"url":"https://arxiv.org/abs/1604.08234","open_access":"1"}],"scopus_import":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23"},{"name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407"},{"grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"article_type":"original","date_created":"2018-12-11T11:47:01Z","arxiv":1,"month":"11","oa_version":"Preprint","user_id":"72615eeb-f1f3-11ec-aa25-d4573ddc34fd","publist_id":"7282","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"10905"}]},"publication_status":"published","oa":1,"date_updated":"2023-09-05T14:09:29Z","citation":{"ieee":"K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” <i>Algorithmica</i>, vol. 70, no. 3. Springer, pp. 457–492, 2014.","ista":"Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. 2014. Polynomial-time algorithms for energy games with special weight structures. Algorithmica. 70(3), 457–492.","apa":"Chatterjee, K., Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2014). Polynomial-time algorithms for energy games with special weight structures. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/s00453-013-9843-7\">https://doi.org/10.1007/s00453-013-9843-7</a>","mla":"Chatterjee, Krishnendu, et al. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” <i>Algorithmica</i>, vol. 70, no. 3, Springer, 2014, pp. 457–92, doi:<a href=\"https://doi.org/10.1007/s00453-013-9843-7\">10.1007/s00453-013-9843-7</a>.","ama":"Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. <i>Algorithmica</i>. 2014;70(3):457-492. doi:<a href=\"https://doi.org/10.1007/s00453-013-9843-7\">10.1007/s00453-013-9843-7</a>","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” <i>Algorithmica</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s00453-013-9843-7\">https://doi.org/10.1007/s00453-013-9843-7</a>.","short":"K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, Algorithmica 70 (2014) 457–492."},"article_processing_charge":"No","title":"Polynomial-time algorithms for energy games with special weight structures","type":"journal_article","status":"public","doi":"10.1007/s00453-013-9843-7","external_id":{"arxiv":["1604.08234"]},"_id":"535","page":"457 - 492","intvolume":"        70","quality_controlled":"1","department":[{"_id":"KrCh"}]},{"tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"title":"Fitness consequences of maternal and grandmaternal effects","type":"journal_article","status":"public","pubrep_id":"934","citation":{"mla":"Prizak, Roshan, et al. “Fitness Consequences of Maternal and Grandmaternal Effects.” <i>Ecology and Evolution</i>, vol. 4, no. 15, Wiley-Blackwell, 2014, pp. 3139–45, doi:<a href=\"https://doi.org/10.1002/ece3.1150\">10.1002/ece3.1150</a>.","apa":"Prizak, R., Ezard, T., &#38; Hoyle, R. (2014). Fitness consequences of maternal and grandmaternal effects. <i>Ecology and Evolution</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1002/ece3.1150\">https://doi.org/10.1002/ece3.1150</a>","chicago":"Prizak, Roshan, Thomas Ezard, and Rebecca Hoyle. “Fitness Consequences of Maternal and Grandmaternal Effects.” <i>Ecology and Evolution</i>. Wiley-Blackwell, 2014. <a href=\"https://doi.org/10.1002/ece3.1150\">https://doi.org/10.1002/ece3.1150</a>.","short":"R. Prizak, T. Ezard, R. Hoyle, Ecology and Evolution 4 (2014) 3139–3145.","ama":"Prizak R, Ezard T, Hoyle R. Fitness consequences of maternal and grandmaternal effects. <i>Ecology and Evolution</i>. 2014;4(15):3139-3145. doi:<a href=\"https://doi.org/10.1002/ece3.1150\">10.1002/ece3.1150</a>","ieee":"R. Prizak, T. Ezard, and R. Hoyle, “Fitness consequences of maternal and grandmaternal effects,” <i>Ecology and Evolution</i>, vol. 4, no. 15. Wiley-Blackwell, pp. 3139–3145, 2014.","ista":"Prizak R, Ezard T, Hoyle R. 2014. Fitness consequences of maternal and grandmaternal effects. Ecology and Evolution. 4(15), 3139–3145."},"department":[{"_id":"NiBa"},{"_id":"GaTk"}],"doi":"10.1002/ece3.1150","_id":"537","page":"3139 - 3145","intvolume":"         4","has_accepted_license":"1","oa":1,"publication_status":"published","ddc":["530","571"],"date_updated":"2021-01-12T08:01:30Z","month":"07","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"7280","scopus_import":1,"file":[{"date_created":"2018-12-12T10:11:31Z","creator":"system","relation":"main_file","checksum":"e32abf75a248e7a11811fd7f60858769","file_id":"4886","file_name":"IST-2018-934-v1+1_Prizak_et_al-2014-Ecology_and_Evolution.pdf","access_level":"open_access","file_size":621582,"date_updated":"2020-07-14T12:46:38Z","content_type":"application/pdf"}],"publisher":"Wiley-Blackwell","date_created":"2018-12-11T11:47:02Z","author":[{"full_name":"Prizak, Roshan","id":"4456104E-F248-11E8-B48F-1D18A9856A87","first_name":"Roshan","last_name":"Prizak"},{"full_name":"Ezard, Thomas","first_name":"Thomas","last_name":"Ezard"},{"full_name":"Hoyle, Rebecca","first_name":"Rebecca","last_name":"Hoyle"}],"volume":4,"abstract":[{"text":"Transgenerational effects are broader than only parental relationships. Despite mounting evidence that multigenerational effects alter phenotypic and life-history traits, our understanding of how they combine to determine fitness is not well developed because of the added complexity necessary to study them. Here, we derive a quantitative genetic model of adaptation to an extraordinary new environment by an additive genetic component, phenotypic plasticity, maternal and grandmaternal effects. We show how, at equilibrium, negative maternal and negative grandmaternal effects maximize expected population mean fitness. We define negative transgenerational effects as those that have a negative effect on trait expression in the subsequent generation, that is, they slow, or potentially reverse, the expected evolutionary dynamic. When maternal effects are positive, negative grandmaternal effects are preferred. As expected under Mendelian inheritance, the grandmaternal effects have a lower impact on fitness than the maternal effects, but this dual inheritance model predicts a more complex relationship between maternal and grandmaternal effects to constrain phenotypic variance and so maximize expected population mean fitness in the offspring.","lang":"eng"}],"date_published":"2014-07-19T00:00:00Z","file_date_updated":"2020-07-14T12:46:38Z","issue":"15","publication":"Ecology and Evolution","day":"19","language":[{"iso":"eng"}],"year":"2014"},{"file_date_updated":"2020-07-14T12:46:46Z","has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"author":[{"full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87","first_name":"Przemyslaw","last_name":"Daca"},{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"},{"full_name":"Krenn, Willibald","first_name":"Willibald","last_name":"Krenn"},{"first_name":"Dejan","last_name":"Nickovic","full_name":"Nickovic, Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87"}],"date_published":"2014-01-28T00:00:00Z","abstract":[{"lang":"eng","text":"Model-based testing is a promising technology for black-box software and hardware testing, in which test cases are generated automatically from high-level specifications. Nowadays, systems typically consist of multiple interacting components and, due to their complexity, testing presents a considerable portion of the effort and cost in the design process. Exploiting the compositional structure of system specifications can considerably reduce the effort in model-based testing. Moreover, inferring properties about the system from testing its individual components allows the designer to reduce the amount of integration testing.\r\nIn this paper, we study compositional properties of the IOCO-testing theory. We propose a new approach to composition and hiding operations, inspired by contract-based design and interface theories. These operations preserve behaviors that are compatible under composition and hiding, and prune away incompatible ones. The resulting specification characterizes the input sequences for which the unit testing of components is sufficient to infer the correctness of component integration without the need for further tests. We provide a methodology that uses these results to minimize integration testing effort, but also to detect potential weaknesses in specifications. While we focus on asynchronous models and the IOCO conformance relation, the resulting methodology can be applied to a broader class of systems."}],"oa_version":"Published Version","month":"01","language":[{"iso":"eng"}],"year":"2014","related_material":{"record":[{"relation":"later_version","id":"2167","status":"public"}]},"day":"28","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","oa":1,"publication_identifier":{"issn":["2664-1690"]},"ddc":["000"],"date_updated":"2023-02-23T10:31:07Z","citation":{"apa":"Daca, P., Henzinger, T. A., Krenn, W., &#38; Nickovic, D. (2014). <i>Compositional specifications for IOCO testing</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">https://doi.org/10.15479/AT:IST-2014-148-v2-1</a>","mla":"Daca, Przemyslaw, et al. <i>Compositional Specifications for IOCO Testing</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">10.15479/AT:IST-2014-148-v2-1</a>.","chicago":"Daca, Przemyslaw, Thomas A Henzinger, Willibald Krenn, and Dejan Nickovic. <i>Compositional Specifications for IOCO Testing</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">https://doi.org/10.15479/AT:IST-2014-148-v2-1</a>.","short":"P. Daca, T.A. Henzinger, W. Krenn, D. Nickovic, Compositional Specifications for IOCO Testing, IST Austria, 2014.","ama":"Daca P, Henzinger TA, Krenn W, Nickovic D. <i>Compositional Specifications for IOCO Testing</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">10.15479/AT:IST-2014-148-v2-1</a>","ista":"Daca P, Henzinger TA, Krenn W, Nickovic D. 2014. Compositional specifications for IOCO testing, IST Austria, 20p.","ieee":"P. Daca, T. A. Henzinger, W. Krenn, and D. Nickovic, <i>Compositional specifications for IOCO testing</i>. IST Austria, 2014."},"publisher":"IST Austria","file":[{"file_name":"IST-2014-148-v2+1_main_tr.pdf","access_level":"open_access","file_size":534732,"date_updated":"2020-07-14T12:46:46Z","content_type":"application/pdf","date_created":"2018-12-12T11:54:21Z","creator":"system","relation":"main_file","checksum":"0e03aba625cc334141a3148432aa5760","file_id":"5543"}],"title":"Compositional specifications for IOCO testing","pubrep_id":"152","status":"public","type":"technical_report","date_created":"2018-12-12T11:39:11Z","doi":"10.15479/AT:IST-2014-148-v2-1","_id":"5411","page":"20","department":[{"_id":"ToHe"}]},{"citation":{"ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 31p.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">https://doi.org/10.15479/AT:IST-2014-153-v1-1</a>.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">10.15479/AT:IST-2014-153-v1-1</a>","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">10.15479/AT:IST-2014-153-v1-1</a>.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">https://doi.org/10.15479/AT:IST-2014-153-v1-1</a>"},"file":[{"file_id":"5500","checksum":"4d6cda4bebed970926403ad6ad8c745f","relation":"main_file","date_created":"2018-12-12T11:53:39Z","creator":"system","content_type":"application/pdf","date_updated":"2020-07-14T12:46:47Z","file_size":423322,"access_level":"open_access","file_name":"IST-2014-153-v1+1_main.pdf"}],"publisher":"IST Austria","pubrep_id":"153","status":"public","type":"technical_report","title":"CEGAR for qualitative analysis of probabilistic systems","page":"31","_id":"5412","date_created":"2018-12-12T11:39:11Z","doi":"10.15479/AT:IST-2014-153-v1-1","department":[{"_id":"KrCh"}],"alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:47Z","date_published":"2014-01-29T00:00:00Z","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}],"author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Przemyslaw","last_name":"Daca","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Chmelik","first_name":"Martin","full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"}],"language":[{"iso":"eng"}],"year":"2014","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"29","related_material":{"record":[{"id":"2063","relation":"later_version","status":"public"},{"status":"public","id":"5413","relation":"later_version"},{"status":"public","id":"5414","relation":"later_version"}]},"month":"01","oa_version":"Published Version","publication_identifier":{"issn":["2664-1690"]},"ddc":["000"],"date_updated":"2023-02-23T12:25:18Z","publication_status":"published","oa":1},{"_id":"5413","page":"33","date_created":"2018-12-12T11:39:11Z","doi":"10.15479/AT:IST-2014-153-v2-2","department":[{"_id":"KrCh"}],"citation":{"ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>."},"publisher":"IST Austria","file":[{"date_updated":"2020-07-14T12:46:47Z","content_type":"application/pdf","file_name":"IST-2014-153-v2+2_main.pdf","file_size":606049,"access_level":"open_access","file_id":"5539","creator":"system","date_created":"2018-12-12T11:54:17Z","checksum":"ce4967a184d84863eec76c66cbac1614","relation":"main_file"}],"pubrep_id":"164","status":"public","type":"technical_report","title":"CEGAR for qualitative analysis of probabilistic systems","year":"2014","language":[{"iso":"eng"}],"day":"06","related_material":{"record":[{"status":"public","relation":"later_version","id":"2063"},{"id":"5412","relation":"earlier_version","status":"public"},{"status":"public","id":"5414","relation":"later_version"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"02","oa_version":"Published Version","publication_identifier":{"issn":["2664-1690"]},"date_updated":"2023-02-23T12:25:18Z","ddc":["000"],"oa":1,"publication_status":"published","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:47Z","has_accepted_license":"1","date_published":"2014-02-06T00:00:00Z","abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Przemyslaw","last_name":"Daca","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","last_name":"Chmelik","full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"}]},{"month":"02","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"07","related_material":{"record":[{"id":"2063","relation":"later_version","status":"public"},{"status":"public","relation":"earlier_version","id":"5412"},{"relation":"earlier_version","id":"5413","status":"public"}]},"language":[{"iso":"eng"}],"year":"2014","oa":1,"publication_status":"published","date_updated":"2023-02-23T12:25:15Z","ddc":["000"],"publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:48Z","has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"first_name":"Przemyslaw","last_name":"Daca","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin"}],"abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. \r\nWe have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"date_published":"2014-02-07T00:00:00Z","date_created":"2018-12-12T11:39:12Z","doi":"10.15479/AT:IST-2014-153-v3-1","page":"33","_id":"5414","department":[{"_id":"KrCh"}],"file":[{"date_created":"2018-12-12T11:53:03Z","creator":"system","checksum":"87b93fe9af71fc5c94b0eb6151537e11","relation":"main_file","file_id":"5464","file_name":"IST-2014-153-v3+1_main.pdf","file_size":606227,"access_level":"open_access","date_updated":"2020-07-14T12:46:48Z","content_type":"application/pdf"}],"publisher":"IST Austria","citation":{"ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>"},"title":"CEGAR for qualitative analysis of probabilistic systems","status":"public","type":"technical_report","pubrep_id":"165"},{"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"page":"27","_id":"5415","date_created":"2018-12-12T11:39:12Z","doi":"10.15479/AT:IST-2014-170-v1-1","pubrep_id":"170","type":"technical_report","status":"public","title":"Nested weighted automata","citation":{"chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. <i>Nested Weighted Automata</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">https://doi.org/10.15479/AT:IST-2014-170-v1-1</a>.","ama":"Chatterjee K, Henzinger TA, Otop J. <i>Nested Weighted Automata</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2014.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2014). <i>Nested weighted automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">https://doi.org/10.15479/AT:IST-2014-170-v1-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>Nested Weighted Automata</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>.","ista":"Chatterjee K, Henzinger TA, Otop J. 2014. Nested weighted automata, IST Austria, 27p.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2014."},"publisher":"IST Austria","file":[{"relation":"main_file","checksum":"31f90dcf2cf899c3f8c6427cfcc2b3c7","creator":"system","date_created":"2018-12-12T11:53:36Z","file_id":"5497","file_size":573457,"access_level":"open_access","file_name":"IST-2014-170-v1+1_main.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:48Z"}],"publication_identifier":{"issn":["2664-1690"]},"ddc":["004"],"date_updated":"2023-02-23T12:26:19Z","oa":1,"publication_status":"published","language":[{"iso":"eng"}],"year":"2014","related_material":{"record":[{"relation":"later_version","id":"1656","status":"public"},{"id":"467","relation":"later_version","status":"public"},{"status":"public","relation":"later_version","id":"5436"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"19","month":"02","oa_version":"Published Version","date_published":"2014-02-19T00:00:00Z","abstract":[{"text":"Recently there has been a significant effort to add quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, several basic system properties such as average response time cannot be expressed with weighted automata. In this work, we introduce nested weighted automata as a new formalism for expressing important quantitative properties such as average response time. We establish an almost complete decidability picture for the basic decision problems for nested weighted automata, and illustrate its applicability in several domains.  ","lang":"eng"}],"author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"}],"alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:48Z","has_accepted_license":"1"},{"publisher":"IST Austria","file":[{"file_id":"5492","creator":"system","date_created":"2018-12-12T11:53:32Z","relation":"main_file","checksum":"445456d22371e4e49aad2b9a0c13bf80","date_updated":"2020-07-14T12:46:49Z","content_type":"application/pdf","file_name":"IST-2014-171-v1+1_report.pdf","file_size":712077,"access_level":"open_access"}],"citation":{"apa":"Henzinger, T. A., &#38; Otop, J. (2014). <i>Model measuring for hybrid systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">https://doi.org/10.15479/AT:IST-2014-171-v1-1</a>","mla":"Henzinger, Thomas A., and Jan Otop. <i>Model Measuring for Hybrid Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">10.15479/AT:IST-2014-171-v1-1</a>.","ama":"Henzinger TA, Otop J. <i>Model Measuring for Hybrid Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">10.15479/AT:IST-2014-171-v1-1</a>","chicago":"Henzinger, Thomas A, and Jan Otop. <i>Model Measuring for Hybrid Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">https://doi.org/10.15479/AT:IST-2014-171-v1-1</a>.","short":"T.A. Henzinger, J. Otop, Model Measuring for Hybrid Systems, IST Austria, 2014.","ieee":"T. A. Henzinger and J. Otop, <i>Model measuring for hybrid systems</i>. IST Austria, 2014.","ista":"Henzinger TA, Otop J. 2014. Model measuring for hybrid systems, IST Austria, 22p."},"title":"Model measuring for hybrid systems","status":"public","type":"technical_report","pubrep_id":"171","date_created":"2018-12-12T11:39:12Z","doi":"10.15479/AT:IST-2014-171-v1-1","_id":"5416","page":"22","department":[{"_id":"ToHe"}],"has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:49Z","alternative_title":["IST Austria Technical Report"],"author":[{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jan","last_name":"Otop","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"lang":"eng","text":"As hybrid systems involve continuous behaviors, they should be evaluated by quantitative methods, rather than qualitative methods. In this paper we adapt a quantitative framework, called model measuring, to the hybrid systems domain. The model-measuring problem asks, given a model M and a specification, what is the maximal distance such that all models within that distance from M satisfy (or violate) the specification. A distance function on models is given as part of the input of the problem. Distances, especially related to continuous behaviors are more natural in the hybrid case than the discrete case. We are interested in distances represented by monotonic hybrid automata, a hybrid counterpart of (discrete) weighted automata, whose recognized timed languages are monotone (w.r.t. inclusion) in the values of parameters.The contributions of this paper are twofold. First, we give sufficient conditions under which the model-measuring problem can be solved. Second, we discuss the modeling of distances and applications of the model-measuring problem."}],"date_published":"2014-02-19T00:00:00Z","month":"02","oa_version":"Published Version","day":"19","related_material":{"record":[{"status":"public","relation":"later_version","id":"2217"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2014","language":[{"iso":"eng"}],"publication_status":"published","oa":1,"date_updated":"2023-02-23T10:33:21Z","ddc":["005"],"publication_identifier":{"issn":["2664-1690"]}},{"citation":{"short":"T.A. Henzinger, J. Otop, From Model Checking to Model Measuring, IST Austria, 2014.","chicago":"Henzinger, Thomas A, and Jan Otop. <i>From Model Checking to Model Measuring</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">https://doi.org/10.15479/AT:IST-2014-172-v1-1</a>.","ama":"Henzinger TA, Otop J. <i>From Model Checking to Model Measuring</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">10.15479/AT:IST-2014-172-v1-1</a>","apa":"Henzinger, T. A., &#38; Otop, J. (2014). <i>From model checking to model measuring</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">https://doi.org/10.15479/AT:IST-2014-172-v1-1</a>","mla":"Henzinger, Thomas A., and Jan Otop. <i>From Model Checking to Model Measuring</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">10.15479/AT:IST-2014-172-v1-1</a>.","ieee":"T. A. Henzinger and J. Otop, <i>From model checking to model measuring</i>. IST Austria, 2014.","ista":"Henzinger TA, Otop J. 2014. From model checking to model measuring, IST Austria, 14p."},"file":[{"relation":"main_file","checksum":"fcc3eab903cfcd3778b338d2d0d44d18","creator":"system","date_created":"2018-12-12T11:53:20Z","file_id":"5481","access_level":"open_access","file_size":383052,"file_name":"IST-2014-172-v1+1_report.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:49Z"}],"publisher":"IST Austria","title":"From model checking to model measuring","pubrep_id":"175","status":"public","type":"technical_report","date_created":"2018-12-12T11:39:13Z","doi":"10.15479/AT:IST-2014-172-v1-1","_id":"5417","page":"14","department":[{"_id":"ToHe"}],"has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:49Z","alternative_title":["IST Austria Technical Report"],"author":[{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"last_name":"Otop","first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan"}],"date_published":"2014-02-19T00:00:00Z","abstract":[{"text":"We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M'within distance ρ from M satisfy (or violate)φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata.\r\nThe model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification.\r\nWe show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved.\r\nWe use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. \r\nWe give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications.","lang":"eng"}],"oa_version":"Published Version","month":"02","language":[{"iso":"eng"}],"year":"2014","day":"19","related_material":{"record":[{"id":"2327","relation":"later_version","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","oa":1,"publication_identifier":{"issn":["2664-1690"]},"ddc":["000"],"date_updated":"2023-02-23T10:38:10Z"},{"type":"technical_report","status":"public","pubrep_id":"176","title":"Games with a weak adversary","publisher":"IST Austria","file":[{"file_size":328253,"access_level":"open_access","file_name":"IST-2014-176-v1+1_icalp_14.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:49Z","relation":"main_file","checksum":"1d6958aa60050e1c3e932c6e5f34c39f","date_created":"2018-12-12T11:53:07Z","creator":"system","file_id":"5468"}],"citation":{"chicago":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>.","short":"K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014.","ama":"Chatterjee K, Doyen L. <i>Games with a Weak Adversary</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>","apa":"Chatterjee, K., &#38; Doyen, L. (2014). <i>Games with a weak adversary</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>.","ieee":"K. Chatterjee and L. Doyen, <i>Games with a weak adversary</i>. IST Austria, 2014.","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p."},"department":[{"_id":"KrCh"}],"page":"18","_id":"5418","date_created":"2018-12-12T11:39:13Z","doi":"10.15479/AT:IST-2014-176-v1-1","abstract":[{"text":"We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results.","lang":"eng"}],"date_published":"2014-03-22T00:00:00Z","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:49Z","ddc":["000","005"],"date_updated":"2023-02-23T10:30:58Z","publication_identifier":{"issn":["2664-1690"]},"oa":1,"publication_status":"published","related_material":{"record":[{"relation":"later_version","id":"2163","status":"public"}]},"day":"22","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"year":"2014","month":"03","oa_version":"Published Version"}]