[{"year":"2014","author":[{"full_name":"Rubio, Maía","last_name":"Rubio","first_name":"Maía"},{"full_name":"Fukazawa, Yugo","last_name":"Fukazawa","first_name":"Yugo"},{"full_name":"Kamasawa, Naomi","first_name":"Naomi","last_name":"Kamasawa"},{"full_name":"Clarkson, Cheryl","last_name":"Clarkson","first_name":"Cheryl"},{"last_name":"Molnár","first_name":"Elek","full_name":"Molnár, Elek"},{"last_name":"Shigemoto","first_name":"Ryuichi","full_name":"Shigemoto, Ryuichi","orcid":"0000-0001-8761-9444","id":"499F3ABC-F248-11E8-B48F-1D18A9856A87"}],"quality_controlled":"1","citation":{"mla":"Rubio, Maía, et al. “Target- and Input-Dependent Organization of AMPA and NMDA Receptors in Synaptic Connections of the Cochlear Nucleus.” <i>Journal of Comparative Neurology</i>, vol. 522, no. 18, Wiley-Blackwell, 2014, pp. 4023–42, doi:<a href=\"https://doi.org/10.1002/cne.23654\">10.1002/cne.23654</a>.","apa":"Rubio, M., Fukazawa, Y., Kamasawa, N., Clarkson, C., Molnár, E., &#38; Shigemoto, R. (2014). Target- and input-dependent organization of AMPA and NMDA receptors in synaptic connections of the cochlear nucleus. <i>Journal of Comparative Neurology</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1002/cne.23654\">https://doi.org/10.1002/cne.23654</a>","short":"M. Rubio, Y. Fukazawa, N. Kamasawa, C. Clarkson, E. Molnár, R. Shigemoto, Journal of Comparative Neurology 522 (2014) 4023–4042.","chicago":"Rubio, Maía, Yugo Fukazawa, Naomi Kamasawa, Cheryl Clarkson, Elek Molnár, and Ryuichi Shigemoto. “Target- and Input-Dependent Organization of AMPA and NMDA Receptors in Synaptic Connections of the Cochlear Nucleus.” <i>Journal of Comparative Neurology</i>. Wiley-Blackwell, 2014. <a href=\"https://doi.org/10.1002/cne.23654\">https://doi.org/10.1002/cne.23654</a>.","ista":"Rubio M, Fukazawa Y, Kamasawa N, Clarkson C, Molnár E, Shigemoto R. 2014. Target- and input-dependent organization of AMPA and NMDA receptors in synaptic connections of the cochlear nucleus. Journal of Comparative Neurology. 522(18), 4023–4042.","ieee":"M. Rubio, Y. Fukazawa, N. Kamasawa, C. Clarkson, E. Molnár, and R. Shigemoto, “Target- and input-dependent organization of AMPA and NMDA receptors in synaptic connections of the cochlear nucleus,” <i>Journal of Comparative Neurology</i>, vol. 522, no. 18. Wiley-Blackwell, pp. 4023–4042, 2014.","ama":"Rubio M, Fukazawa Y, Kamasawa N, Clarkson C, Molnár E, Shigemoto R. Target- and input-dependent organization of AMPA and NMDA receptors in synaptic connections of the cochlear nucleus. <i>Journal of Comparative Neurology</i>. 2014;522(18):4023-4042. doi:<a href=\"https://doi.org/10.1002/cne.23654\">10.1002/cne.23654</a>"},"main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4198489/"}],"abstract":[{"text":"We examined the synaptic structure, quantity, and distribution of α-amino-3-hydroxy-5-methylisoxazole-4-propionic acid (AMPA)- and N-methyl-D-aspartate (NMDA)-type glutamate receptors (AMPARs and NMDARs, respectively) in rat cochlear nuclei by a highly sensitive freeze-fracture replica labeling technique. Four excitatory synapses formed by two distinct inputs, auditory nerve (AN) and parallel fibers (PF), on different cell types were analyzed. These excitatory synapse types included AN synapses on bushy cells (AN-BC synapses) and fusiform cells (AN-FC synapses) and PF synapses on FC (PF-FC synapses) and cartwheel cell spines (PF-CwC synapses). Immunogold labeling revealed differences in synaptic structure as well as AMPAR and NMDAR number and/or density in both AN and PF synapses, indicating a target-dependent organization. The immunogold receptor labeling also identified differences in the synaptic organization of FCs based on AN or PF connections, indicating an input-dependent organization in FCs. Among the four excitatory synapse types, the AN-BC synapses were the smallest and had the most densely packed intramembrane particles (IMPs), whereas the PF-CwC synapses were the largest and had sparsely packed IMPs. All four synapse types showed positive correlations between the IMP-cluster area and the AMPAR number, indicating a common intrasynapse-type relationship for glutamatergic synapses. Immunogold particles for AMPARs were distributed over the entire area of individual AN synapses; PF synapses often showed synaptic areas devoid of labeling. The gold-labeling for NMDARs occurred in a mosaic fashion, with less positive correlations between the IMP-cluster area and the NMDAR number. Our observations reveal target- and input-dependent features in the structure, number, and organization of AMPARs and NMDARs in AN and PF synapses.","lang":"eng"}],"publication_status":"published","_id":"2064","oa":1,"publication":"Journal of Comparative Neurology","title":"Target- and input-dependent organization of AMPA and NMDA receptors in synaptic connections of the cochlear nucleus","publisher":"Wiley-Blackwell","volume":522,"issue":"18","status":"public","month":"07","date_created":"2018-12-11T11:55:30Z","publist_id":"4974","intvolume":"       522","day":"29","oa_version":"Submitted Version","date_updated":"2021-01-12T06:55:05Z","type":"journal_article","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","acknowledgement":"National Institutes of Health (NIH) Grant Number: 1R01DC013048‐0; Biotechnology and Biological Sciences Research Council, UK Grant Number: BB/J015938/1\r\n","department":[{"_id":"RySh"}],"doi":"10.1002/cne.23654","language":[{"iso":"eng"}],"page":"4023 - 4042","date_published":"2014-07-29T00:00:00Z","scopus_import":1},{"author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"},{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Krinninger, Sebastian","first_name":"Sebastian","last_name":"Krinninger"},{"last_name":"Loitzenbauer","first_name":"Veronika","full_name":"Loitzenbauer, Veronika"},{"full_name":"Raskin, Michael","last_name":"Raskin","first_name":"Michael"}],"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1307.4473"}],"citation":{"apa":"Chatterjee, K., Henzinger, M. H., Krinninger, S., Loitzenbauer, V., &#38; Raskin, M. (2014). Approximating the minimum cycle mean. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">https://doi.org/10.1016/j.tcs.2014.06.031</a>","mla":"Chatterjee, Krishnendu, et al. “Approximating the Minimum Cycle Mean.” <i>Theoretical Computer Science</i>, vol. 547, no. C, Elsevier, 2014, pp. 104–16, doi:<a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">10.1016/j.tcs.2014.06.031</a>.","ista":"Chatterjee K, Henzinger MH, Krinninger S, Loitzenbauer V, Raskin M. 2014. Approximating the minimum cycle mean. Theoretical Computer Science. 547(C), 104–116.","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, Veronika Loitzenbauer, and Michael Raskin. “Approximating the Minimum Cycle Mean.” <i>Theoretical Computer Science</i>. Elsevier, 2014. <a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">https://doi.org/10.1016/j.tcs.2014.06.031</a>.","short":"K. Chatterjee, M.H. Henzinger, S. Krinninger, V. Loitzenbauer, M. Raskin, Theoretical Computer Science 547 (2014) 104–116.","ieee":"K. Chatterjee, M. H. Henzinger, S. Krinninger, V. Loitzenbauer, and M. Raskin, “Approximating the minimum cycle mean,” <i>Theoretical Computer Science</i>, vol. 547, no. C. Elsevier, pp. 104–116, 2014.","ama":"Chatterjee K, Henzinger MH, Krinninger S, Loitzenbauer V, Raskin M. Approximating the minimum cycle mean. <i>Theoretical Computer Science</i>. 2014;547(C):104-116. doi:<a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">10.1016/j.tcs.2014.06.031</a>"},"year":"2014","oa":1,"_id":"1375","title":"Approximating the minimum cycle mean","publication":"Theoretical Computer Science","publication_status":"published","abstract":[{"lang":"eng","text":"We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible to the problem of a logarithmic number of min-plus matrix multiplications of n×n-matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1+ε)-approximation algorithm for the problem and the running time of our algorithm is Õ(nωlog3(nW/ε)/ε),1 where O(nω) is the time required for the classic n×n-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/ε)) factor in space a cycle with approximately optimal weight can be computed within the same time bound."}],"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"volume":547,"issue":"C","article_type":"original","publisher":"Elsevier","publist_id":"5836","intvolume":"       547","status":"public","date_created":"2018-12-11T11:51:40Z","month":"08","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","day":"28","date_updated":"2022-09-09T11:50:58Z","type":"journal_article","oa_version":"Preprint","doi":"10.1016/j.tcs.2014.06.031","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"ec_funded":1,"page":"104 - 116","date_published":"2014-08-28T00:00:00Z","external_id":{"arxiv":["1307.4473"]},"scopus_import":"1","arxiv":1},{"ddc":["000","005"],"oa":1,"_id":"1392","title":"A logic-based framework for verifying consensus algorithms","publication_status":"published","abstract":[{"text":"Fault-tolerant distributed algorithms play an important role in ensuring the reliability of many software applications. In this paper we consider distributed algorithms whose computations are organized in rounds. To verify the correctness of such algorithms, we reason about (i) properties (such as invariants) of the state, (ii) the transitions controlled by the algorithm, and (iii) the communication graph. We introduce a logic that addresses these points, and contains set comprehensions with cardinality constraints, function symbols to describe the local states of each process, and a limited form of quantifier alternation to express the verification conditions. We show its use in automating the verification of consensus algorithms. In particular, we give a semi-decision procedure for the unsatisfiability problem of the logic and identify a decidable fragment. We successfully applied our framework to verify the correctness of a variety of consensus algorithms tolerant to both benign faults (message loss, process crashes) and value faults (message corruption).","lang":"eng"}],"project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989"}],"quality_controlled":"1","author":[{"last_name":"Dragoi","first_name":"Cezara","id":"2B2B5ED0-F248-11E8-B48F-1D18A9856A87","full_name":"Dragoi, Cezara"},{"last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"full_name":"Veith, Helmut","last_name":"Veith","first_name":"Helmut"},{"full_name":"Widder, Josef","first_name":"Josef","last_name":"Widder"},{"last_name":"Zufferey","first_name":"Damien","id":"4397AC76-F248-11E8-B48F-1D18A9856A87","full_name":"Zufferey, Damien","orcid":"0000-0002-3197-8736"}],"citation":{"short":"C. Dragoi, T.A. Henzinger, H. Veith, J. Widder, D. Zufferey, in:, Springer, 2014, pp. 161–181.","chicago":"Dragoi, Cezara, Thomas A Henzinger, Helmut Veith, Josef Widder, and Damien Zufferey. “A Logic-Based Framework for Verifying Consensus Algorithms,” 8318:161–81. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-642-54013-4_10\">https://doi.org/10.1007/978-3-642-54013-4_10</a>.","ista":"Dragoi C, Henzinger TA, Veith H, Widder J, Zufferey D. 2014. A logic-based framework for verifying consensus algorithms. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 8318, 161–181.","ama":"Dragoi C, Henzinger TA, Veith H, Widder J, Zufferey D. A logic-based framework for verifying consensus algorithms. In: Vol 8318. Springer; 2014:161-181. doi:<a href=\"https://doi.org/10.1007/978-3-642-54013-4_10\">10.1007/978-3-642-54013-4_10</a>","ieee":"C. Dragoi, T. A. Henzinger, H. Veith, J. Widder, and D. Zufferey, “A logic-based framework for verifying consensus algorithms,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, San Diego, USA, 2014, vol. 8318, pp. 161–181.","apa":"Dragoi, C., Henzinger, T. A., Veith, H., Widder, J., &#38; Zufferey, D. (2014). A logic-based framework for verifying consensus algorithms (Vol. 8318, pp. 161–181). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, San Diego, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-54013-4_10\">https://doi.org/10.1007/978-3-642-54013-4_10</a>","mla":"Dragoi, Cezara, et al. <i>A Logic-Based Framework for Verifying Consensus Algorithms</i>. Vol. 8318, Springer, 2014, pp. 161–81, doi:<a href=\"https://doi.org/10.1007/978-3-642-54013-4_10\">10.1007/978-3-642-54013-4_10</a>."},"year":"2014","publist_id":"5817","intvolume":"      8318","status":"public","date_created":"2018-12-11T11:51:45Z","month":"01","conference":{"start_date":"2014-01-19","location":"San Diego, USA","name":"VMCAI: Verification, Model Checking and Abstract Interpretation","end_date":"2014-01-21"},"volume":8318,"pubrep_id":"179","publisher":"Springer","file_date_updated":"2020-07-14T12:44:48Z","doi":"10.1007/978-3-642-54013-4_10","language":[{"iso":"eng"}],"department":[{"_id":"ToHe"}],"has_accepted_license":"1","ec_funded":1,"acknowledgement":"Supported by the Vienna Science and Technology Fund (WWTF) through grant PROSEED.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","date_updated":"2021-01-12T06:50:22Z","type":"conference","oa_version":"Submitted Version","scopus_import":1,"alternative_title":["LNCS"],"page":"161 - 181","date_published":"2014-01-01T00:00:00Z","file":[{"date_created":"2018-12-12T10:11:06Z","relation":"main_file","file_size":444138,"content_type":"application/pdf","creator":"system","date_updated":"2020-07-14T12:44:48Z","file_id":"4859","access_level":"open_access","checksum":"bffa33d39be77df0da39defe97eabf84","file_name":"IST-2014-179-v1+1_vmcai14.pdf"}]},{"project":[{"name":"Quantitative Reactive Modeling","grant_number":"267989","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"}],"abstract":[{"text":"Probabilistic programs are usual functional or imperative programs with two added constructs: (1) the ability to draw values at random from distributions, and (2) the ability to condition values of variables in a program via observations. Models from diverse application areas such as computer vision, coding theory, cryptographic protocols, biology and reliability analysis can be written as probabilistic programs. Probabilistic inference is the problem of computing an explicit representation of the probability distribution implicitly specified by a probabilistic program. Depending on the application, the desired output from inference may vary-we may want to estimate the expected value of some function f with respect to the distribution, or the mode of the distribution, or simply a set of samples drawn from the distribution. In this paper, we describe connections this research area called \\Probabilistic Programming&quot; has with programming languages and software engineering, and this includes language design, and the static and dynamic analysis of programs. We survey current state of the art and speculate on promising directions for future research.","lang":"eng"}],"publication_status":"published","publication":"Proceedings of the on Future of Software Engineering","title":"Probabilistic programming","_id":"1393","oa":1,"year":"2014","citation":{"apa":"Gordon, A., Henzinger, T. A., Nori, A., &#38; Rajamani, S. (2014). Probabilistic programming. In <i>Proceedings of the on Future of Software Engineering</i> (pp. 167–181). Hyderabad, India: ACM. <a href=\"https://doi.org/10.1145/2593882.2593900\">https://doi.org/10.1145/2593882.2593900</a>","mla":"Gordon, Andrew, et al. “Probabilistic Programming.” <i>Proceedings of the on Future of Software Engineering</i>, ACM, 2014, pp. 167–81, doi:<a href=\"https://doi.org/10.1145/2593882.2593900\">10.1145/2593882.2593900</a>.","ama":"Gordon A, Henzinger TA, Nori A, Rajamani S. Probabilistic programming. In: <i>Proceedings of the on Future of Software Engineering</i>. ACM; 2014:167-181. doi:<a href=\"https://doi.org/10.1145/2593882.2593900\">10.1145/2593882.2593900</a>","ieee":"A. Gordon, T. A. Henzinger, A. Nori, and S. Rajamani, “Probabilistic programming,” in <i>Proceedings of the on Future of Software Engineering</i>, Hyderabad, India, 2014, pp. 167–181.","ista":"Gordon A, Henzinger TA, Nori A, Rajamani S. 2014. Probabilistic programming. Proceedings of the on Future of Software Engineering. FOSE: Future of Software Engineering, 167–181.","chicago":"Gordon, Andrew, Thomas A Henzinger, Aditya Nori, and Sriram Rajamani. “Probabilistic Programming.” In <i>Proceedings of the on Future of Software Engineering</i>, 167–81. ACM, 2014. <a href=\"https://doi.org/10.1145/2593882.2593900\">https://doi.org/10.1145/2593882.2593900</a>.","short":"A. Gordon, T.A. Henzinger, A. Nori, S. Rajamani, in:, Proceedings of the on Future of Software Engineering, ACM, 2014, pp. 167–181."},"main_file_link":[{"url":"https://doi.org/10.1145/2593882.2593900","open_access":"1"}],"quality_controlled":"1","author":[{"last_name":"Gordon","first_name":"Andrew","full_name":"Gordon, Andrew"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger"},{"first_name":"Aditya","last_name":"Nori","full_name":"Nori, Aditya"},{"first_name":"Sriram","last_name":"Rajamani","full_name":"Rajamani, Sriram"}],"conference":{"start_date":"2014-05-31","location":"Hyderabad, India","name":"FOSE: Future of Software Engineering","end_date":"2014-06-07"},"month":"05","date_created":"2018-12-11T11:51:45Z","status":"public","publist_id":"5816","publisher":"ACM","ec_funded":1,"department":[{"_id":"ToHe"}],"language":[{"iso":"eng"}],"doi":"10.1145/2593882.2593900","oa_version":"Published Version","type":"conference","date_updated":"2021-01-12T06:50:22Z","day":"31","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","scopus_import":1,"date_published":"2014-05-31T00:00:00Z","page":"167 - 181"},{"publication_status":"published","abstract":[{"text":"In this thesis I studied various individual and social immune defences employed by the invasive garden ant Lasius neglectus mostly against entomopathogenic fungi.  The first two chapters of this thesis address the phenomenon of 'social immunisation'. Social immunisation, that is the immunological protection of group members due to social contact to a pathogen-exposed nestmate, has been described in various social insect species against different types of pathogens. However, in the case of entomopathogenic fungi it has, so far, only been demonstrated that social immunisation exists at all. Its underlying mechanisms r any other properties were, however, unknown. In the first chapter of this thesis I identified the mechanistic basis of social immunisation in L. neglectus against the entomopathogenous fungus Metarhizium. I could show that nestmates of a pathogen-exposed individual contract low-level infections due to social interactions. These low-level infections are, however, non-lethal and cause an active stimulation of the immune system, which protects the nestmates upon subsequent pathogen encounters. In the second chapter of this thesis I investigated the specificity and colony level effects of social immunisation. I demonstrated that the protection conferred by social immunisation is highly specific, protecting ants only against the same pathogen strain. In addition, depending on the respective context, social immunisation may even cause fitness costs. I further showed that social immunisation crucially affects sanitary behaviour and disease dynamics within ant groups. In the third chapter of this thesis I studied the effects of the ectosymbiotic fungus Laboulbenia formicarum on its host L. neglectus. Although Laboulbeniales are the largest order of insect-parasitic fungi, research concerning host fitness consequence is sparse. I showed that highly Laboulbenia-infected ants sustain fitness costs under resource limitation, however, gain fitness benefits when exposed to an entomopathogenus fungus. These effects are probably cause by a prophylactic upregulation of behavioural as well as physiological immune defences in highly infected ants.","lang":"eng"}],"title":"Immune defences in ants: Effects of social immunisation and a fungal ectosymbiont in the ant Lasius neglectus","language":[{"iso":"eng"}],"department":[{"_id":"SyCr"}],"_id":"1395","date_updated":"2023-09-07T11:38:56Z","type":"dissertation","oa_version":"None","day":"01","supervisor":[{"id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87","full_name":"Cremer, Sylvia M","orcid":"0000-0002-2193-3868","last_name":"Cremer","first_name":"Sylvia M"}],"year":"2014","citation":{"ieee":"M. Konrad, “Immune defences in ants: Effects of social immunisation and a fungal ectosymbiont in the ant Lasius neglectus,” Institute of Science and Technology Austria, 2014.","ama":"Konrad M. Immune defences in ants: Effects of social immunisation and a fungal ectosymbiont in the ant Lasius neglectus. 2014.","ista":"Konrad M. 2014. Immune defences in ants: Effects of social immunisation and a fungal ectosymbiont in the ant Lasius neglectus. Institute of Science and Technology Austria.","short":"M. Konrad, Immune Defences in Ants: Effects of Social Immunisation and a Fungal Ectosymbiont in the Ant Lasius Neglectus, Institute of Science and Technology Austria, 2014.","chicago":"Konrad, Matthias. “Immune Defences in Ants: Effects of Social Immunisation and a Fungal Ectosymbiont in the Ant Lasius Neglectus.” Institute of Science and Technology Austria, 2014.","mla":"Konrad, Matthias. <i>Immune Defences in Ants: Effects of Social Immunisation and a Fungal Ectosymbiont in the Ant Lasius Neglectus</i>. Institute of Science and Technology Austria, 2014.","apa":"Konrad, M. (2014). <i>Immune defences in ants: Effects of social immunisation and a fungal ectosymbiont in the ant Lasius neglectus</i>. Institute of Science and Technology Austria."},"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"last_name":"Konrad","first_name":"Matthias","id":"46528076-F248-11E8-B48F-1D18A9856A87","full_name":"Konrad, Matthias"}],"date_created":"2018-12-11T11:51:46Z","month":"02","status":"public","alternative_title":["ISTA Thesis"],"publist_id":"5814","publication_identifier":{"issn":["2663-337X"]},"degree_awarded":"PhD","publisher":"Institute of Science and Technology Austria","date_published":"2014-02-01T00:00:00Z","page":"131"},{"citation":{"apa":"Marhavá, P. (2014). <i>Molecular mechanisms of patterning and subcellular trafficking in Arabidopsis thaliana</i>. Institute of Science and Technology Austria.","mla":"Marhavá, Petra. <i>Molecular Mechanisms of Patterning and Subcellular Trafficking in Arabidopsis Thaliana</i>. Institute of Science and Technology Austria, 2014.","chicago":"Marhavá, Petra. “Molecular Mechanisms of Patterning and Subcellular Trafficking in Arabidopsis Thaliana.” Institute of Science and Technology Austria, 2014.","short":"P. Marhavá, Molecular Mechanisms of Patterning and Subcellular Trafficking in Arabidopsis Thaliana, Institute of Science and Technology Austria, 2014.","ista":"Marhavá P. 2014. Molecular mechanisms of patterning and subcellular trafficking in Arabidopsis thaliana. Institute of Science and Technology Austria.","ama":"Marhavá P. Molecular mechanisms of patterning and subcellular trafficking in Arabidopsis thaliana. 2014.","ieee":"P. Marhavá, “Molecular mechanisms of patterning and subcellular trafficking in Arabidopsis thaliana,” Institute of Science and Technology Austria, 2014."},"author":[{"full_name":"Marhavá, Petra","id":"44E59624-F248-11E8-B48F-1D18A9856A87","last_name":"Marhavá","first_name":"Petra"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","oa_version":"None","date_updated":"2023-09-07T11:39:38Z","type":"dissertation","supervisor":[{"last_name":"Friml","first_name":"Jiří","full_name":"Friml, Jiří","orcid":"0000-0002-8302-7596","id":"4159519E-F248-11E8-B48F-1D18A9856A87"}],"year":"2014","day":"01","title":"Molecular mechanisms of patterning and subcellular trafficking in Arabidopsis thaliana","_id":"1402","department":[{"_id":"JiFr"}],"language":[{"iso":"eng"}],"abstract":[{"text":"Phosphatidylinositol (Ptdlns) is a structural phospholipid that can be phosphorylated into various lipid signaling molecules, designated polyphosphoinositides (PPIs). The reversible phosphorylation of PPIs on the 3, 4, or 5 position of inositol is performed by a set of organelle-specific kinases and phosphatases, and the characteristic head groups make these molecules ideal for regulating biological processes in time and space. In yeast and mammals, Ptdlns3P and Ptdlns(3,5)P2 play crucial roles in trafficking toward the lytic compartments, whereas the role in plants is not yet fully understood. Here we identified the role of a land plant-specific subgroup of PPI phosphatases, the suppressor of actin 2 (SAC2) to SAC5, during vauolar trafficking and morphogenesis in Arabidopsis thaliana. SAC2-SAC5 localize to the tonoplast along with Ptdlns3P, the presumable product of their activity. in SAC gain- and loss-of-function mutants, the levels of Ptdlns monophosphates and bisphosphates were changed, with opposite effects on the morphology of storage and lytic vacuoles, and the trafficking toward the vacuoles was defective. Moreover, multiple sac knockout mutants had an increased number of smaller storage and lytic vacuoles, whereas extralarge vacuoles were observed in the overexpression lines, correlating with various growth and developmental defects. The fragmented vacuolar phenotype of sac mutants could be mimicked by treating wild-type seedlings with Ptdlns(3,5)P2, corroborating that this PPI is important for vacuole morphology. Taken together, these results provide evidence that PPIs, together with their metabolic enzymes SAC2-SAC5, are crucial for vacuolar trafficking and for vacuolar morphology and function in plants.","lang":"eng"}],"publication_status":"published","date_published":"2014-12-01T00:00:00Z","page":"90","publisher":"Institute of Science and Technology Austria","alternative_title":["ISTA Thesis"],"degree_awarded":"PhD","publication_identifier":{"issn":["2663-337X"]},"publist_id":"5805","month":"12","date_created":"2018-12-11T11:51:49Z","status":"public"},{"supervisor":[{"first_name":"Carl-Philipp J","last_name":"Heisenberg","id":"39427864-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0912-4566","full_name":"Heisenberg, Carl-Philipp J"}],"year":"2014","day":"01","oa_version":"None","date_updated":"2023-10-17T12:16:58Z","type":"dissertation","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Behrndt","first_name":"Martin","id":"3ECECA3A-F248-11E8-B48F-1D18A9856A87","full_name":"Behrndt, Martin"}],"citation":{"ieee":"M. Behrndt, “Forces driving epithelial spreading in zebrafish epiboly,” IST Austria, 2014.","ama":"Behrndt M. Forces driving epithelial spreading in zebrafish epiboly. 2014.","short":"M. Behrndt, Forces Driving Epithelial Spreading in Zebrafish Epiboly, IST Austria, 2014.","chicago":"Behrndt, Martin. “Forces Driving Epithelial Spreading in Zebrafish Epiboly.” IST Austria, 2014.","ista":"Behrndt M. 2014. Forces driving epithelial spreading in zebrafish epiboly. IST Austria.","apa":"Behrndt, M. (2014). <i>Forces driving epithelial spreading in zebrafish epiboly</i>. IST Austria.","mla":"Behrndt, Martin. <i>Forces Driving Epithelial Spreading in Zebrafish Epiboly</i>. IST Austria, 2014."},"abstract":[{"text":"A variety of developmental and disease related processes depend on epithelial cell sheet spreading. In order to gain insight into the biophysical mechanism(s) underlying the tissue morphogenesis we studied the spreading of an epithelium during the early development of the zebrafish embryo. In zebrafish epiboly the enveloping cell layer (EVL), a simple squamous epithelium, spreads over the yolk cell to completely engulf it at the end of gastrulation. Previous studies have proposed that an actomyosin ring forming within the yolk syncytial layer (YSL) acts as purse string that through constriction along its circumference pulls on the margin of the EVL. Direct biophysical evidence for this hypothesis has however been missing. The aim of the thesis was to understand how the actomyosin ring may generate pulling forces onto the EVL and what cellular mechanism(s) may facilitate the spreading of the epithelium. Using laser ablation to measure cortical tension within the actomyosin ring we found an anisotropic tension distribution, which was highest along the circumference of the ring. However the low degree of anisotropy was incompatible with the actomyosin ring functioning as a purse string only. Additionally, we observed retrograde cortical flow from vegetal parts of the ring into the EVL margin. Interpreting the experimental data using a theoretical distribution that models  the tissues as active viscous gels led us to proposen that the actomyosin ring has a twofold contribution to EVL epiboly. It not only acts as a purse string through constriction along its circumference, but in addition constriction along the width of the ring generates pulling forces through friction-resisted cortical flow. Moreover, when rendering the purse string mechanism unproductive EVL epiboly proceeded normally indicating that the flow-friction mechanism is sufficient to drive the process. Aiming to understand what cellular mechanism(s) may facilitate the spreading of the epithelium we found that tension-oriented EVL cell divisions limit tissue anisotropy by releasing tension along the division axis and promote epithelial spreading. Notably, EVL cells undergo ectopic cell fusion in conditions in which oriented-cell division is impaired or the epithelium is mechanically challenged. Taken together our study of EVL epiboly suggests a novel mechanism of force generation for actomyosin rings through friction-resisted cortical flow and highlights the importance of tension-oriented cell divisions in epithelial morphogenesis.","lang":"eng"}],"publication_status":"published","department":[{"_id":"CaHe"}],"_id":"1403","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"2282"},{"relation":"part_of_dissertation","status":"public","id":"2950"},{"status":"public","relation":"part_of_dissertation","id":"3373"}]},"acknowledged_ssus":[{"_id":"SSU"}],"title":"Forces driving epithelial spreading in zebrafish epiboly","publisher":"IST Austria","page":"91","date_published":"2014-08-01T00:00:00Z","status":"public","month":"08","date_created":"2018-12-11T11:51:49Z","publist_id":"5804","alternative_title":["IST Austria Thesis"]},{"abstract":[{"text":"The co-evolution of hosts and pathogens is characterized by continuous adaptations of both parties. Pathogens of social insects need to adapt towards disease defences at two levels: 1) individual immunity of each colony member consisting of behavioural defence strategies as well as humoral and cellular immune responses and 2) social immunity that is collectively performed by all group members comprising behavioural, physiological and organisational defence strategies.\r\n\r\nTo disentangle the selection pressure on pathogens by the collective versus individual level of disease defence in social insects, we performed an evolution experiment using the Argentine Ant, Linepithema humile, as a host and a mixture of the general insect pathogenic fungus Metarhizium spp. (6 strains) as a pathogen. We allowed pathogen evolution over 10 serial host passages to two different evolution host treatments: (1) only individual host immunity in a single host treatment, and (2) simultaneously acting individual and social immunity in a social host treatment, in which an exposed ant was accompanied by two untreated nestmates.\r\n\r\nBefore starting the pathogen evolution experiment, the 6 Metarhizium spp. strains were characterised concerning conidiospore size killing rates in singly and socially reared ants, their competitiveness under coinfecting conditions and their influence on ant behaviour. We analysed how the ancestral atrain mixture changed in conidiospere size, killing rate and strain composition dependent on host treatment (single or social hosts) during 10 passages and found that killing rate and conidiospere size of the pathogen increased under both evolution regimes, but different depending on host treatment.\r\n\r\nTesting the evolved strain mixtures that evolved under either the single or social host treatment under both single and social current rearing conditions in a full factorial design experiment revealed that the additional collective defences in insect societies add new selection pressure for their coevolving pathogens that compromise their ability to adapt to its host at the group level. To our knowledge, this is the first study directly measuring the influence of social immunity on pathogen evolution.","lang":"eng"}],"publication_status":"published","acknowledgement":"This work was funded by the DFG and the ERC.","_id":"1404","department":[{"_id":"SyCr"}],"language":[{"iso":"eng"}],"title":"Evolution of a fungal pathogen towards individual versus social immunity in ants","year":"2014","supervisor":[{"id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87","full_name":"Cremer, Sylvia M","orcid":"0000-0002-2193-3868","last_name":"Cremer","first_name":"Sylvia M"}],"day":"01","oa_version":"None","date_updated":"2021-01-12T06:50:30Z","type":"dissertation","author":[{"full_name":"Stock, Miriam","id":"42462816-F248-11E8-B48F-1D18A9856A87","last_name":"Stock","first_name":"Miriam"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Stock, Miriam. <i>Evolution of a Fungal Pathogen towards Individual versus Social Immunity in Ants</i>. IST Austria, 2014.","apa":"Stock, M. (2014). <i>Evolution of a fungal pathogen towards individual versus social immunity in ants</i>. IST Austria.","chicago":"Stock, Miriam. “Evolution of a Fungal Pathogen towards Individual versus Social Immunity in Ants.” IST Austria, 2014.","short":"M. Stock, Evolution of a Fungal Pathogen towards Individual versus Social Immunity in Ants, IST Austria, 2014.","ista":"Stock M. 2014. Evolution of a fungal pathogen towards individual versus social immunity in ants. IST Austria.","ieee":"M. Stock, “Evolution of a fungal pathogen towards individual versus social immunity in ants,” IST Austria, 2014.","ama":"Stock M. Evolution of a fungal pathogen towards individual versus social immunity in ants. 2014."},"status":"public","month":"04","date_created":"2018-12-11T11:51:49Z","publist_id":"5803","alternative_title":["IST Austria Thesis"],"publisher":"IST Austria","page":"101","date_published":"2014-04-01T00:00:00Z"},{"has_accepted_license":"1","_id":"5411","department":[{"_id":"ToHe"}],"ddc":["000"],"oa":1,"doi":"10.15479/AT:IST-2014-148-v2-1","related_material":{"record":[{"id":"2167","relation":"later_version","status":"public"}]},"language":[{"iso":"eng"}],"title":"Compositional specifications for IOCO testing","abstract":[{"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.","lang":"eng"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw","last_name":"Daca","first_name":"Przemyslaw"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Krenn, Willibald","first_name":"Willibald","last_name":"Krenn"},{"id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","full_name":"Nickovic, Dejan","first_name":"Dejan","last_name":"Nickovic"}],"citation":{"ista":"Daca P, Henzinger TA, Krenn W, Nickovic D. 2014. Compositional specifications for IOCO testing, IST Austria, 20p.","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.","ieee":"P. Daca, T. A. Henzinger, W. Krenn, and D. Nickovic, <i>Compositional specifications for IOCO testing</i>. 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>","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>."},"year":"2014","day":"28","oa_version":"Published Version","date_updated":"2023-02-23T10:31:07Z","type":"technical_report","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"status":"public","month":"01","date_created":"2018-12-12T11:39:11Z","pubrep_id":"152","page":"20","file":[{"date_created":"2018-12-12T11:54:21Z","relation":"main_file","file_size":534732,"content_type":"application/pdf","creator":"system","file_id":"5543","date_updated":"2020-07-14T12:46:46Z","access_level":"open_access","file_name":"IST-2014-148-v2+1_main_tr.pdf","checksum":"0e03aba625cc334141a3148432aa5760"}],"date_published":"2014-01-28T00:00:00Z","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:46Z"},{"alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"month":"01","date_created":"2018-12-12T11:39:11Z","status":"public","file":[{"date_created":"2018-12-12T11:53:39Z","relation":"main_file","file_size":423322,"content_type":"application/pdf","creator":"system","date_updated":"2020-07-14T12:46:47Z","file_id":"5500","access_level":"open_access","checksum":"4d6cda4bebed970926403ad6ad8c745f","file_name":"IST-2014-153-v1+1_main.pdf"}],"date_published":"2014-01-29T00:00:00Z","pubrep_id":"153","page":"31","file_date_updated":"2020-07-14T12:46:47Z","publisher":"IST Austria","title":"CEGAR for qualitative analysis of probabilistic systems","_id":"5412","department":[{"_id":"KrCh"}],"has_accepted_license":"1","ddc":["000"],"oa":1,"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2014-153-v1-1","related_material":{"record":[{"id":"2063","relation":"later_version","status":"public"},{"id":"5413","relation":"later_version","status":"public"},{"status":"public","relation":"later_version","id":"5414"}]},"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"}],"publication_status":"published","citation":{"ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 31p.","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-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>","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-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>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Przemyslaw","last_name":"Daca","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik"}],"oa_version":"Published Version","date_updated":"2023-02-23T12:25:18Z","type":"technical_report","year":"2014","day":"29"},{"page":"33","pubrep_id":"164","date_published":"2014-02-06T00:00:00Z","file":[{"relation":"main_file","date_created":"2018-12-12T11:54:17Z","file_size":606049,"content_type":"application/pdf","creator":"system","file_id":"5539","date_updated":"2020-07-14T12:46:47Z","checksum":"ce4967a184d84863eec76c66cbac1614","file_name":"IST-2014-153-v2+2_main.pdf","access_level":"open_access"}],"publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:47Z","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"status":"public","date_created":"2018-12-12T11:39:11Z","month":"02","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87","last_name":"Daca","first_name":"Przemyslaw"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","first_name":"Martin"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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>.","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>","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","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>.","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p."},"day":"06","year":"2014","type":"technical_report","date_updated":"2023-02-23T12:25:18Z","oa_version":"Published Version","related_material":{"record":[{"relation":"later_version","status":"public","id":"2063"},{"status":"public","relation":"earlier_version","id":"5412"},{"id":"5414","relation":"later_version","status":"public"}]},"oa":1,"doi":"10.15479/AT:IST-2014-153-v2-2","ddc":["000"],"language":[{"iso":"eng"}],"has_accepted_license":"1","_id":"5413","department":[{"_id":"KrCh"}],"title":"CEGAR for qualitative analysis of probabilistic systems","publication_status":"published","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}]},{"date_updated":"2023-02-23T12:25:15Z","type":"technical_report","oa_version":"Published Version","day":"07","year":"2014","citation":{"ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>","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>.","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","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>","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>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Daca","first_name":"Przemyslaw","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik"}],"publication_status":"published","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. \r\nWe have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}],"title":"CEGAR for qualitative analysis of probabilistic systems","related_material":{"record":[{"id":"2063","status":"public","relation":"later_version"},{"id":"5412","status":"public","relation":"earlier_version"},{"status":"public","relation":"earlier_version","id":"5413"}]},"oa":1,"doi":"10.15479/AT:IST-2014-153-v3-1","ddc":["000"],"language":[{"iso":"eng"}],"_id":"5414","has_accepted_license":"1","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:48Z","publisher":"IST Austria","date_published":"2014-02-07T00:00:00Z","file":[{"file_id":"5464","date_updated":"2020-07-14T12:46:48Z","checksum":"87b93fe9af71fc5c94b0eb6151537e11","file_name":"IST-2014-153-v3+1_main.pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:53:03Z","file_size":606227,"content_type":"application/pdf","creator":"system"}],"page":"33","pubrep_id":"165","date_created":"2018-12-12T11:39:12Z","month":"02","status":"public","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]}},{"abstract":[{"lang":"eng","text":"Recently there has been a significant effort to add quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, several basic system properties such as average response time cannot be expressed with weighted automata. In this work, we introduce nested weighted automata as a new formalism for expressing important quantitative properties such as average response time. We establish an almost complete decidability picture for the basic decision problems for nested weighted automata, and illustrate its applicability in several domains.  "}],"publication_status":"published","title":"Nested weighted automata","_id":"5415","has_accepted_license":"1","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"doi":"10.15479/AT:IST-2014-170-v1-1","oa":1,"related_material":{"record":[{"relation":"later_version","status":"public","id":"1656"},{"id":"467","status":"public","relation":"later_version"},{"status":"public","relation":"later_version","id":"5436"}]},"language":[{"iso":"eng"}],"ddc":["004"],"oa_version":"Published Version","type":"technical_report","date_updated":"2023-02-23T12:26:19Z","year":"2014","day":"19","citation":{"ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2014.","ama":"Chatterjee K, Henzinger TA, Otop J. <i>Nested Weighted Automata</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>","ista":"Chatterjee K, Henzinger TA, Otop J. 2014. Nested weighted automata, IST Austria, 27p.","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>.","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>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"},{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","first_name":"Jan","last_name":"Otop"}],"month":"02","date_created":"2018-12-12T11:39:12Z","status":"public","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:48Z","publisher":"IST Austria","file":[{"date_created":"2018-12-12T11:53:36Z","relation":"main_file","content_type":"application/pdf","creator":"system","file_size":573457,"file_id":"5497","date_updated":"2020-07-14T12:46:48Z","access_level":"open_access","checksum":"31f90dcf2cf899c3f8c6427cfcc2b3c7","file_name":"IST-2014-170-v1+1_main.pdf"}],"date_published":"2014-02-19T00:00:00Z","pubrep_id":"170","page":"27"},{"alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:12Z","month":"02","status":"public","date_published":"2014-02-19T00:00:00Z","file":[{"date_updated":"2020-07-14T12:46:49Z","file_id":"5492","file_name":"IST-2014-171-v1+1_report.pdf","checksum":"445456d22371e4e49aad2b9a0c13bf80","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:53:32Z","file_size":712077,"content_type":"application/pdf","creator":"system"}],"page":"22","pubrep_id":"171","file_date_updated":"2020-07-14T12:46:49Z","publisher":"IST Austria","title":"Model measuring for hybrid systems","oa":1,"ddc":["005"],"language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"2217"}]},"doi":"10.15479/AT:IST-2014-171-v1-1","_id":"5416","has_accepted_license":"1","department":[{"_id":"ToHe"}],"publication_status":"published","abstract":[{"text":"As hybrid systems involve continuous behaviors, they should be evaluated by quantitative methods, rather than qualitative methods. In this paper we adapt a quantitative framework, called model measuring, to the hybrid systems domain. The model-measuring problem asks, given a model M and a specification, what is the maximal distance such that all models within that distance from M satisfy (or violate) the specification. A distance function on models is given as part of the input of the problem. Distances, especially related to continuous behaviors are more natural in the hybrid case than the discrete case. We are interested in distances represented by monotonic hybrid automata, a hybrid counterpart of (discrete) weighted automata, whose recognized timed languages are monotone (w.r.t. inclusion) in the values of parameters.The contributions of this paper are twofold. First, we give sufficient conditions under which the model-measuring problem can be solved. Second, we discuss the modeling of distances and applications of the model-measuring problem.","lang":"eng"}],"citation":{"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>.","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>","ieee":"T. A. Henzinger and J. Otop, <i>Model measuring for hybrid systems</i>. IST Austria, 2014.","ama":"Henzinger TA, Otop J. <i>Model Measuring for Hybrid Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">10.15479/AT:IST-2014-171-v1-1</a>","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.","ista":"Henzinger TA, Otop J. 2014. Model measuring for hybrid systems, IST Austria, 22p."},"author":[{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","date_updated":"2023-02-23T10:33:21Z","oa_version":"Published Version","day":"19","year":"2014"},{"title":"From model checking to model measuring","_id":"5417","department":[{"_id":"ToHe"}],"has_accepted_license":"1","language":[{"iso":"eng"}],"ddc":["000"],"oa":1,"doi":"10.15479/AT:IST-2014-172-v1-1","related_material":{"record":[{"id":"2327","status":"public","relation":"later_version"}]},"abstract":[{"lang":"eng","text":"We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M'within distance ρ from M satisfy (or violate)φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata.\r\nThe model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification.\r\nWe show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved.\r\nWe use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. \r\nWe give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications."}],"publication_status":"published","citation":{"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>.","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>","ama":"Henzinger TA, Otop J. <i>From Model Checking to Model Measuring</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">10.15479/AT:IST-2014-172-v1-1</a>","ieee":"T. A. Henzinger and J. Otop, <i>From model checking to model measuring</i>. IST Austria, 2014.","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>.","short":"T.A. Henzinger, J. Otop, From Model Checking to Model Measuring, IST Austria, 2014.","ista":"Henzinger TA, Otop J. 2014. From model checking to model measuring, IST Austria, 14p."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger"},{"first_name":"Jan","last_name":"Otop","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"oa_version":"Published Version","date_updated":"2023-02-23T10:38:10Z","type":"technical_report","year":"2014","day":"19","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"month":"02","date_created":"2018-12-12T11:39:13Z","status":"public","file":[{"file_size":383052,"content_type":"application/pdf","creator":"system","date_created":"2018-12-12T11:53:20Z","relation":"main_file","access_level":"open_access","file_name":"IST-2014-172-v1+1_report.pdf","checksum":"fcc3eab903cfcd3778b338d2d0d44d18","file_id":"5481","date_updated":"2020-07-14T12:46:49Z"}],"date_published":"2014-02-19T00:00:00Z","pubrep_id":"175","page":"14","file_date_updated":"2020-07-14T12:46:49Z","publisher":"IST Austria"},{"title":"Games with a weak adversary","_id":"5418","has_accepted_license":"1","department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"ddc":["000","005"],"doi":"10.15479/AT:IST-2014-176-v1-1","related_material":{"record":[{"id":"2163","status":"public","relation":"later_version"}]},"oa":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"}],"publication_status":"published","citation":{"mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>.","apa":"Chatterjee, K., &#38; Doyen, L. (2014). <i>Games with a weak adversary</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p.","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>","ieee":"K. Chatterjee and L. Doyen, <i>Games with a weak adversary</i>. IST Austria, 2014."},"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","date_updated":"2023-02-23T10:30:58Z","type":"technical_report","year":"2014","day":"22","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"month":"03","date_created":"2018-12-12T11:39:13Z","status":"public","file":[{"date_updated":"2020-07-14T12:46:49Z","file_id":"5468","file_name":"IST-2014-176-v1+1_icalp_14.pdf","checksum":"1d6958aa60050e1c3e932c6e5f34c39f","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:53:07Z","creator":"system","content_type":"application/pdf","file_size":328253}],"date_published":"2014-03-22T00:00:00Z","pubrep_id":"176","page":"18","file_date_updated":"2020-07-14T12:46:49Z","publisher":"IST Austria"},{"file":[{"file_name":"IST-2014-187-v1+1_main_full_tech.pdf","checksum":"c608e66030a4bf51d2d99b451f539b99","access_level":"open_access","date_updated":"2020-07-14T12:46:50Z","file_id":"5548","content_type":"application/pdf","creator":"system","file_size":670031,"relation":"main_file","date_created":"2018-12-12T11:54:25Z"}],"date_published":"2014-04-14T00:00:00Z","pubrep_id":"187","page":"34","file_date_updated":"2020-07-14T12:46:50Z","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"month":"04","date_created":"2018-12-12T11:39:13Z","status":"public","citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2014). <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>"},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus"},{"first_name":"Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","date_updated":"2021-01-12T08:02:03Z","type":"technical_report","year":"2014","day":"14","title":"Improved algorithms for reachability and shortest path on low tree-width graphs","department":[{"_id":"KrCh"}],"_id":"5419","has_accepted_license":"1","doi":"10.15479/AT:IST-2014-187-v1-1","ddc":["000"],"oa":1,"language":[{"iso":"eng"}],"abstract":[{"text":"We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold:\r\n1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing).\r\n2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries.\r\n3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries.\r\nOur algorithms improve all existing results, and use very simple data structures.","lang":"eng"}],"publication_status":"published"},{"page":"49","pubrep_id":"191","date_published":"2014-04-14T00:00:00Z","file":[{"relation":"main_file","date_created":"2018-12-12T11:53:58Z","creator":"system","content_type":"application/pdf","file_size":584368,"file_id":"5520","date_updated":"2020-07-14T12:46:50Z","checksum":"49e0fd3e62650346daf7dc04604f7a0a","file_name":"IST-2014-191-v1+1_main_full.pdf","access_level":"open_access"}],"publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:50Z","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"status":"public","date_created":"2018-12-12T11:39:14Z","month":"04","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen"}],"citation":{"mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2014). <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>","ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria, 2014.","ama":"Chatterjee K, Ibsen-Jensen R. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff Games, IST Austria, 2014.","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p."},"day":"14","year":"2014","type":"technical_report","date_updated":"2021-01-12T08:02:05Z","oa_version":"Published Version","doi":"10.15479/AT:IST-2014-191-v1-1","ddc":["000","005"],"language":[{"iso":"eng"}],"oa":1,"_id":"5420","has_accepted_license":"1","department":[{"_id":"KrCh"}],"title":"The value 1 problem for concurrent mean-payoff games","publication_status":"published","abstract":[{"text":"We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy).","lang":"eng"}]},{"file_date_updated":"2020-07-14T12:46:50Z","publisher":"IST Austria","date_published":"2014-04-18T00:00:00Z","file":[{"file_size":443529,"creator":"system","content_type":"application/pdf","date_created":"2018-12-12T11:54:16Z","relation":"main_file","access_level":"open_access","file_name":"IST-2014-190-v2+2_main_full.pdf","checksum":"42f3d8b563286eb0d903832bd9a848d3","file_id":"5538","date_updated":"2020-07-14T12:46:50Z"},{"content_type":"application/pdf","creator":"kschuh","file_size":440911,"date_created":"2019-09-06T07:30:20Z","relation":"main_file","access_level":"open_access","checksum":"0c9a2fd822309719634495a35957e34d","file_name":"IST-2014-190-v1+1_main_full.pdf","file_id":"6852","date_updated":"2020-07-14T12:46:50Z"}],"page":"27","pubrep_id":"190","date_created":"2018-12-12T11:39:14Z","month":"04","status":"public","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"type":"technical_report","date_updated":"2023-02-23T12:26:33Z","oa_version":"Published Version","day":"18","year":"2014","citation":{"chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolution on Graphs, IST Austria, 2014.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2014. The complexity of evolution on graphs, IST Austria, 27p.","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolution on Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolution on graphs</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2014). <i>The complexity of evolution on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>"},"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus"},{"full_name":"Nowak, Martin","first_name":"Martin","last_name":"Nowak"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"text":"Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time.","lang":"eng"}],"title":"The complexity of evolution on graphs","oa":1,"ddc":["000","005"],"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2014-190-v2-2","related_material":{"record":[{"relation":"later_version","status":"public","id":"5432"},{"relation":"later_version","status":"public","id":"5440"}]},"has_accepted_license":"1","_id":"5421","department":[{"_id":"KrCh"}]},{"citation":{"mla":"Porsche, Jana. <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none, 2014.","apa":"Porsche, J. (2014). <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none.","ista":"Porsche J. 2014. Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland, none,p.","short":"J. Porsche, Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland, none, 2014.","chicago":"Porsche, Jana. <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none, 2014.","ieee":"J. Porsche, <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none, 2014.","ama":"Porsche J. <i>Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland</i>. none; 2014."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Porsche, Jana","id":"3252EDC2-F248-11E8-B48F-1D18A9856A87","last_name":"Porsche","first_name":"Jana"}],"oa_version":"None","type":"report","date_updated":"2020-07-14T23:04:56Z","year":"2014","title":"Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland","_id":"5422","department":[{"_id":"E-Lib"}],"has_accepted_license":"1","oa":1,"ddc":["020"],"language":[{"iso":"eng"}],"abstract":[{"text":"Notes from the Third Plenary for the Research Data Alliance in Dublin, Ireland on March 26 to 28, 2014 with focus on starting an institutional research data repository.","lang":"eng"}],"file":[{"relation":"main_file","date_created":"2018-12-12T11:53:40Z","content_type":"application/pdf","creator":"system","file_size":648585,"file_id":"5501","date_updated":"2020-07-14T12:46:50Z","file_name":"IST-2014-254-v1+1_Dublin_Day_3.pdf","checksum":"3954896648ce8afa8f7c4425e71cff08","access_level":"open_access"},{"file_id":"5502","date_updated":"2020-07-14T12:46:50Z","access_level":"open_access","checksum":"9a0d42b0b832dfe7e4b22fb6816bcbba","file_name":"IST-2014-254-v1+2_Dublin_Day_1.pdf","date_created":"2018-12-12T11:53:41Z","relation":"main_file","file_size":221339,"content_type":"application/pdf","creator":"system"},{"relation":"main_file","date_created":"2018-12-12T11:53:42Z","file_size":187778,"creator":"system","content_type":"application/pdf","date_updated":"2020-07-14T12:46:50Z","file_id":"5503","file_name":"IST-2014-254-v1+3_Dublin_Day_2.pdf","checksum":"498b8d629fb1bd17bff1dc43700a93e6","access_level":"open_access"}],"date_published":"2014-01-01T00:00:00Z","pubrep_id":"254","file_date_updated":"2020-07-14T12:46:50Z","publisher":"none","date_created":"2018-12-12T11:39:14Z","status":"public"}]