[{"volume":4,"doi":"10.1126/scisignal.2002617","issue":"198","year":"2011","_id":"491","month":"11","author":[{"first_name":"Alexander","id":"4DFA52AE-F248-11E8-B48F-1D18A9856A87","last_name":"Eichner","full_name":"Eichner, Alexander"},{"first_name":"Michael K","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6620-9179","last_name":"Sixt","full_name":"Sixt, Michael K"}],"citation":{"apa":"Eichner, A., &#38; Sixt, M. K. (2011). Setting the clock for recirculating lymphocytes. <i>Science Signaling</i>. American Association for the Advancement of Science. <a href=\"https://doi.org/10.1126/scisignal.2002617\">https://doi.org/10.1126/scisignal.2002617</a>","ama":"Eichner A, Sixt MK. Setting the clock for recirculating lymphocytes. <i>Science Signaling</i>. 2011;4(198). doi:<a href=\"https://doi.org/10.1126/scisignal.2002617\">10.1126/scisignal.2002617</a>","ista":"Eichner A, Sixt MK. 2011. Setting the clock for recirculating lymphocytes. Science Signaling. 4(198), pe43.","chicago":"Eichner, Alexander, and Michael K Sixt. “Setting the Clock for Recirculating Lymphocytes.” <i>Science Signaling</i>. American Association for the Advancement of Science, 2011. <a href=\"https://doi.org/10.1126/scisignal.2002617\">https://doi.org/10.1126/scisignal.2002617</a>.","ieee":"A. Eichner and M. K. Sixt, “Setting the clock for recirculating lymphocytes,” <i>Science Signaling</i>, vol. 4, no. 198. American Association for the Advancement of Science, 2011.","short":"A. Eichner, M.K. Sixt, Science Signaling 4 (2011).","mla":"Eichner, Alexander, and Michael K. Sixt. “Setting the Clock for Recirculating Lymphocytes.” <i>Science Signaling</i>, vol. 4, no. 198, pe43, American Association for the Advancement of Science, 2011, doi:<a href=\"https://doi.org/10.1126/scisignal.2002617\">10.1126/scisignal.2002617</a>."},"date_updated":"2021-01-12T08:01:02Z","date_created":"2018-12-11T11:46:46Z","department":[{"_id":"MiSi"}],"oa_version":"None","publist_id":"7329","status":"public","intvolume":"         4","article_number":"pe43","publication_status":"published","scopus_import":1,"type":"journal_article","quality_controlled":"1","abstract":[{"text":"In their search for antigens, lymphocytes continuously shuttle among blood vessels, lymph vessels, and lymphatic tissues. Chemokines mediate entry of lymphocytes into lymphatic tissues, and sphingosine 1-phosphate (S1P) promotes localization of lymphocytes to the vasculature. Both signals are sensed through G protein-coupled receptors (GPCRs). Most GPCRs undergo ligand-dependent homologous receptor desensitization, a process that decreases their signaling output after previous exposure to high ligand concentration. Such desensitization can explain why lymphocytes do not take an intermediate position between two signals but rather oscillate between them. The desensitization of S1P receptor 1 (S1PR1) is mediated by GPCR kinase 2 (GRK2). Deletion of GRK2 in lymphocytes compromises desensitization by high vascular S1P concentrations, thereby reducing responsiveness to the chemokine signal and trapping the cells in the vascular compartment. The desensitization kinetics of S1PR1 allows lymphocytes to dynamically shuttle between vasculature and lymphatic tissue, although the positional information in both compartments is static.","lang":"eng"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"American Association for the Advancement of Science","date_published":"2011-11-08T00:00:00Z","title":"Setting the clock for recirculating lymphocytes","day":"08","language":[{"iso":"eng"}],"publication":"Science Signaling"},{"page":"4309 - 4322","author":[{"last_name":"Schraivogel","full_name":"Schraivogel, Daniel","first_name":"Daniel"},{"last_name":"Weinmann","full_name":"Weinmann, Lasse","first_name":"Lasse"},{"full_name":"Beier, Dagmar","last_name":"Beier","first_name":"Dagmar"},{"full_name":"Tabatabai, Ghazaleh","last_name":"Tabatabai","first_name":"Ghazaleh"},{"id":"4DFA52AE-F248-11E8-B48F-1D18A9856A87","first_name":"Alexander","full_name":"Eichner, Alexander","last_name":"Eichner"},{"last_name":"Zhu","full_name":"Zhu, Jia","first_name":"Jia"},{"first_name":"Martina","full_name":"Anton, Martina","last_name":"Anton"},{"orcid":"0000-0002-6620-9179","last_name":"Sixt","full_name":"Sixt, Michael K","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","first_name":"Michael K"},{"last_name":"Weller","full_name":"Weller, Michael","first_name":"Michael"},{"first_name":"Christoph","full_name":"Beier, Christoph","last_name":"Beier"},{"first_name":"Gunter","full_name":"Meister, Gunter","last_name":"Meister"}],"oa_version":"Submitted Version","status":"public","year":"2011","oa":1,"pmid":1,"language":[{"iso":"eng"}],"external_id":{"pmid":["21857646"]},"abstract":[{"text":"Cancer stem cells or cancer initiating cells are believed to contribute to cancer recurrence after therapy. MicroRNAs (miRNAs) are short RNA molecules with fundamental roles in gene regulation. The role of miRNAs in cancer stem cells is only poorly understood. Here, we report miRNA expression profiles of glioblastoma stem cell-containing CD133 + cell populations. We find that miR-9, miR-9 * (referred to as miR-9/9 *), miR-17 and miR-106b are highly abundant in CD133 + cells. Furthermore, inhibition of miR-9/9 * or miR-17 leads to reduced neurosphere formation and stimulates cell differentiation. Calmodulin-binding transcription activator 1 (CAMTA1) is a putative transcription factor, which induces the expression of the anti-proliferative cardiac hormone natriuretic peptide A (NPPA). We identify CAMTA1 as an miR-9/9 * and miR-17 target. CAMTA1 expression leads to reduced neurosphere formation and tumour growth in nude mice, suggesting that CAMTA1 can function as tumour suppressor. Consistently, CAMTA1 and NPPA expression correlate with patient survival. Our findings could provide a basis for novel strategies of glioblastoma therapy.","lang":"eng"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"10","article_type":"original","citation":{"ama":"Schraivogel D, Weinmann L, Beier D, et al. CAMTA1 is a novel tumour suppressor regulated by miR-9/9 * in glioblastoma stem cells. <i>EMBO Journal</i>. 2011;30(20):4309-4322. doi:<a href=\"https://doi.org/10.1038/emboj.2011.301\">10.1038/emboj.2011.301</a>","apa":"Schraivogel, D., Weinmann, L., Beier, D., Tabatabai, G., Eichner, A., Zhu, J., … Meister, G. (2011). CAMTA1 is a novel tumour suppressor regulated by miR-9/9 * in glioblastoma stem cells. <i>EMBO Journal</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1038/emboj.2011.301\">https://doi.org/10.1038/emboj.2011.301</a>","ista":"Schraivogel D, Weinmann L, Beier D, Tabatabai G, Eichner A, Zhu J, Anton M, Sixt MK, Weller M, Beier C, Meister G. 2011. CAMTA1 is a novel tumour suppressor regulated by miR-9/9 * in glioblastoma stem cells. EMBO Journal. 30(20), 4309–4322.","chicago":"Schraivogel, Daniel, Lasse Weinmann, Dagmar Beier, Ghazaleh Tabatabai, Alexander Eichner, Jia Zhu, Martina Anton, et al. “CAMTA1 Is a Novel Tumour Suppressor Regulated by MiR-9/9 * in Glioblastoma Stem Cells.” <i>EMBO Journal</i>. Wiley-Blackwell, 2011. <a href=\"https://doi.org/10.1038/emboj.2011.301\">https://doi.org/10.1038/emboj.2011.301</a>.","mla":"Schraivogel, Daniel, et al. “CAMTA1 Is a Novel Tumour Suppressor Regulated by MiR-9/9 * in Glioblastoma Stem Cells.” <i>EMBO Journal</i>, vol. 30, no. 20, Wiley-Blackwell, 2011, pp. 4309–22, doi:<a href=\"https://doi.org/10.1038/emboj.2011.301\">10.1038/emboj.2011.301</a>.","short":"D. Schraivogel, L. Weinmann, D. Beier, G. Tabatabai, A. Eichner, J. Zhu, M. Anton, M.K. Sixt, M. Weller, C. Beier, G. Meister, EMBO Journal 30 (2011) 4309–4322.","ieee":"D. Schraivogel <i>et al.</i>, “CAMTA1 is a novel tumour suppressor regulated by miR-9/9 * in glioblastoma stem cells,” <i>EMBO Journal</i>, vol. 30, no. 20. Wiley-Blackwell, pp. 4309–4322, 2011."},"date_updated":"2021-01-12T08:01:19Z","date_created":"2018-12-11T11:46:55Z","department":[{"_id":"MiSi"}],"publist_id":"7301","intvolume":"        30","volume":30,"main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3199389/","open_access":"1"}],"doi":"10.1038/emboj.2011.301","issue":"20","_id":"518","title":"CAMTA1 is a novel tumour suppressor regulated by miR-9/9 * in glioblastoma stem cells","date_published":"2011-10-19T00:00:00Z","day":"19","publication":"EMBO Journal","quality_controlled":"1","scopus_import":1,"publication_status":"published","type":"journal_article","publisher":"Wiley-Blackwell"},{"issue":"3","_id":"531","main_file_link":[{"open_access":"1","url":"https://infoscience.epfl.ch/record/178042/files/art3A10.10072Fs10703-011-0131-3.pdf"}],"volume":39,"doi":"10.1007/s10703-011-0131-3","publist_id":"7288","department":[{"_id":"ToHe"}],"date_updated":"2021-01-12T08:01:27Z","date_created":"2018-12-11T11:47:00Z","intvolume":"        39","month":"12","article_type":"original","citation":{"ama":"Guerraoui R, Henzinger TA, Singh V. Verification of STM on relaxed memory models. <i>Formal Methods in System Design</i>. 2011;39(3):297-331. doi:<a href=\"https://doi.org/10.1007/s10703-011-0131-3\">10.1007/s10703-011-0131-3</a>","apa":"Guerraoui, R., Henzinger, T. A., &#38; Singh, V. (2011). Verification of STM on relaxed memory models. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-011-0131-3\">https://doi.org/10.1007/s10703-011-0131-3</a>","ista":"Guerraoui R, Henzinger TA, Singh V. 2011. Verification of STM on relaxed memory models. Formal Methods in System Design. 39(3), 297–331.","chicago":"Guerraoui, Rachid, Thomas A Henzinger, and Vasu Singh. “Verification of STM on Relaxed Memory Models.” <i>Formal Methods in System Design</i>. Springer, 2011. <a href=\"https://doi.org/10.1007/s10703-011-0131-3\">https://doi.org/10.1007/s10703-011-0131-3</a>.","mla":"Guerraoui, Rachid, et al. “Verification of STM on Relaxed Memory Models.” <i>Formal Methods in System Design</i>, vol. 39, no. 3, Springer, 2011, pp. 297–331, doi:<a href=\"https://doi.org/10.1007/s10703-011-0131-3\">10.1007/s10703-011-0131-3</a>.","short":"R. Guerraoui, T.A. Henzinger, V. Singh, Formal Methods in System Design 39 (2011) 297–331.","ieee":"R. Guerraoui, T. A. Henzinger, and V. Singh, “Verification of STM on relaxed memory models,” <i>Formal Methods in System Design</i>, vol. 39, no. 3. Springer, pp. 297–331, 2011."},"quality_controlled":"1","publication_status":"published","type":"journal_article","scopus_import":1,"publisher":"Springer","day":"01","date_published":"2011-12-01T00:00:00Z","title":"Verification of STM on relaxed memory models","publication":"Formal Methods in System Design","year":"2011","oa_version":"Published Version","status":"public","author":[{"first_name":"Rachid","last_name":"Guerraoui","full_name":"Guerraoui, Rachid"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"},{"first_name":"Vasu","id":"4DAE2708-F248-11E8-B48F-1D18A9856A87","last_name":"Singh","full_name":"Singh, Vasu"}],"page":"297 - 331","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","abstract":[{"lang":"eng","text":"Software transactional memories (STM) are described in the literature with assumptions of sequentially consistent program execution and atomicity of high level operations like read, write, and abort. However, in a realistic setting, processors use relaxed memory models to optimize hardware performance. Moreover, the atomicity of operations depends on the underlying hardware. This paper presents the first approach to verify STMs under relaxed memory models with atomicity of 32 bit loads and stores, and read-modify-write operations. We describe RML, a simple language for expressing concurrent programs. We develop a semantics of RML parametrized by a relaxed memory model. We then present our tool, FOIL, which takes as input the RML description of an STM algorithm restricted to two threads and two variables, and the description of a memory model, and automatically determines the locations of fences, which if inserted, ensure the correctness of the restricted STM algorithm under the given memory model. We use FOIL to verify DSTM, TL2, and McRT STM under the memory models of sequential consistency, total store order, partial store order, and relaxed memory order for two threads and two variables. Finally, we extend the verification results for DSTM and TL2 to an arbitrary number of threads and variables by manually proving that the structural properties of STMs are satisfied at the hardware level of atomicity under the considered relaxed memory models."}],"language":[{"iso":"eng"}],"ddc":["000"],"oa":1},{"title":"An O(n2) time algorithm for alternating Büchi games","date_published":"2011-07-11T00:00:00Z","day":"11","publication_status":"published","type":"technical_report","publisher":"IST Austria","has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-23T11:15:12Z","date_created":"2018-12-12T11:38:59Z","department":[{"_id":"KrCh"}],"month":"07","citation":{"ieee":"K. Chatterjee and M. H. Henzinger, <i>An O(n2) time algorithm for alternating Büchi games</i>. IST Austria, 2011.","short":"K. Chatterjee, M.H. Henzinger, An O(N2) Time Algorithm for Alternating Büchi Games, IST Austria, 2011.","mla":"Chatterjee, Krishnendu, and Monika H. Henzinger. <i>An O(N2) Time Algorithm for Alternating Büchi Games</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0009\">10.15479/AT:IST-2011-0009</a>.","chicago":"Chatterjee, Krishnendu, and Monika H Henzinger. <i>An O(N2) Time Algorithm for Alternating Büchi Games</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0009\">https://doi.org/10.15479/AT:IST-2011-0009</a>.","ista":"Chatterjee K, Henzinger MH. 2011. An O(n2) time algorithm for alternating Büchi games, IST Austria, 20p.","apa":"Chatterjee, K., &#38; Henzinger, M. H. (2011). <i>An O(n2) time algorithm for alternating Büchi games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0009\">https://doi.org/10.15479/AT:IST-2011-0009</a>","ama":"Chatterjee K, Henzinger MH. <i>An O(N2) Time Algorithm for Alternating Büchi Games</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0009\">10.15479/AT:IST-2011-0009</a>"},"_id":"5379","file":[{"file_id":"5504","checksum":"0b354264229045d982332fd2cb5b9a26","date_updated":"2020-07-14T12:46:39Z","date_created":"2018-12-12T11:53:43Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","creator":"system","file_name":"IST-2011-0009_IST-2011-0009.pdf","file_size":388665}],"doi":"10.15479/AT:IST-2011-0009","language":[{"iso":"eng"}],"ddc":["000","004"],"oa":1,"abstract":[{"lang":"eng","text":"Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is ̃O(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the ̃O(n·m) boundary by presenting a new technique that reduces the running time to O(n2). This bound also leads to O(n2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n3)), and (3) in Markov decision processes (improving for m > n4/3 an earlier bound of O(min(m1.5, m·n2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n2), which is an improvement over earlier bounds for m > n4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem."}],"article_processing_charge":"No","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","file_date_updated":"2020-07-14T12:46:39Z","oa_version":"Published Version","status":"public","page":"20","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger"}],"related_material":{"record":[{"id":"3165","status":"public","relation":"later_version"}]},"pubrep_id":"15","year":"2011","publication_identifier":{"issn":["2664-1690"]}},{"ddc":["000"],"oa":1,"date_published":"2011-07-11T00:00:00Z","title":"Bounded rationality in concurrent parity games","day":"11","language":[{"iso":"eng"}],"alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:39Z","publication_status":"published","type":"technical_report","abstract":[{"text":"We consider 2-player games played on a finite state space for an infinite number of rounds.  The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine the successor state. We study concurrent games with ω-regular winning conditions specified as parity objectives.  We consider the qualitative analysis problems: the computation of the almost-sure and limit-sure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respectively. In general the almost-sure and limit-sure winning strategies require both infinite-memory as well as infinite-precision (to describe probabilities). We study the bounded-rationality problem for qualitative analysis of concurrent parity games, where the strategy set for player 1 is restricted to bounded-resource strategies.  In terms of precision, strategies can be deterministic, uniform, finite-precision or infinite-precision;  and in terms of memory, strategies can be memoryless, finite-memory or infinite-memory. We present a precise and complete characterization of the qualitative winning sets for all combinations of classes of strategies. In particular, we show that uniform memoryless strategies are as powerful as finite-precision infinite-memory strategies, and infinite-precision memoryless strategies are as powerful as infinite-precision finite-memory strategies.  We show that the winning sets can be computed in O(n2d+3) time, where n is the size of the game structure and 2d is the number of priorities (or colors), and our algorithms are symbolic. The membership problem of whether a state belongs to a winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of turn-based parity games, where in each state only one of the two players has a choice of moves, our algorithms,that are obtained by characterization of the winning sets as μ-calculus formulas, are considerably more involved than those for turn-based games.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","page":"53","month":"07","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"id":"3338","status":"public","relation":"later_version"}]},"citation":{"chicago":"Chatterjee, Krishnendu. <i>Bounded Rationality in Concurrent Parity Games</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0008\">https://doi.org/10.15479/AT:IST-2011-0008</a>.","short":"K. Chatterjee, Bounded Rationality in Concurrent Parity Games, IST Austria, 2011.","mla":"Chatterjee, Krishnendu. <i>Bounded Rationality in Concurrent Parity Games</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0008\">10.15479/AT:IST-2011-0008</a>.","ieee":"K. Chatterjee, <i>Bounded rationality in concurrent parity games</i>. IST Austria, 2011.","ama":"Chatterjee K. <i>Bounded Rationality in Concurrent Parity Games</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0008\">10.15479/AT:IST-2011-0008</a>","apa":"Chatterjee, K. (2011). <i>Bounded rationality in concurrent parity games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0008\">https://doi.org/10.15479/AT:IST-2011-0008</a>","ista":"Chatterjee K. 2011. Bounded rationality in concurrent parity games, IST Austria, 53p."},"date_updated":"2023-02-23T11:22:53Z","date_created":"2018-12-12T11:39:00Z","department":[{"_id":"KrCh"}],"oa_version":"Published Version","status":"public","file":[{"file_id":"5544","checksum":"0fd38186409be819a911c4990fa79d1f","date_updated":"2020-07-14T12:46:39Z","date_created":"2018-12-12T11:54:22Z","access_level":"open_access","relation":"main_file","content_type":"application/pdf","creator":"system","file_name":"IST-2011-0008_IST-2011-0008.pdf","file_size":500399}],"publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2011-0008","pubrep_id":"16","year":"2011","_id":"5380"},{"ddc":["000","005"],"oa":1,"day":"05","title":"Partial-observation stochastic games: How to win when belief fails","date_published":"2011-07-05T00:00:00Z","language":[{"iso":"eng"}],"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:39Z","publication_status":"published","type":"technical_report","publisher":"IST Austria","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"In two-player finite-state stochastic games of partial obser- vation on graphs, in every state of the graph, the players simultaneously choose an action, and their joint actions determine a probability distri- bution over the successor states. The game is played for infinitely many rounds and thus the players construct an infinite path in the graph. We consider reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1) or pos- itively (i.e., with positive probability), no matter the strategy of the second player.\r\n\r\nWe classify such games according to the information and to the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two- sided with (c) both players having partial observation. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization.\r\n\r\nOur main results for pure strategies are as follows: (1) For one-sided games with player 2 perfect observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strate- gies are not sufficient, and present an exponential upper bound on mem- ory both for almost-sure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete and present symbolic algo- rithms that avoid the explicit exponential construction. (2) For one-sided games with player 1 perfect observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and posi- tive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least non-elementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence re- sult exhibit serious flaws in previous results in the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed.","lang":"eng"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"}],"page":"43","month":"07","citation":{"ama":"Chatterjee K, Doyen L. <i>Partial-Observation Stochastic Games: How to Win When Belief Fails</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0007\">10.15479/AT:IST-2011-0007</a>","apa":"Chatterjee, K., &#38; Doyen, L. (2011). <i>Partial-observation stochastic games: How to win when belief fails</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0007\">https://doi.org/10.15479/AT:IST-2011-0007</a>","ista":"Chatterjee K, Doyen L. 2011. Partial-observation stochastic games: How to win when belief fails, IST Austria, 43p.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Partial-Observation Stochastic Games: How to Win When Belief Fails</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0007\">https://doi.org/10.15479/AT:IST-2011-0007</a>.","short":"K. Chatterjee, L. Doyen, Partial-Observation Stochastic Games: How to Win When Belief Fails, IST Austria, 2011.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Partial-Observation Stochastic Games: How to Win When Belief Fails</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0007\">10.15479/AT:IST-2011-0007</a>.","ieee":"K. Chatterjee and L. Doyen, <i>Partial-observation stochastic games: How to win when belief fails</i>. IST Austria, 2011."},"related_material":{"record":[{"id":"1903","status":"public","relation":"later_version"},{"id":"2211","relation":"later_version","status":"public"},{"id":"2955","relation":"later_version","status":"public"}]},"department":[{"_id":"KrCh"}],"oa_version":"Published Version","date_created":"2018-12-12T11:39:00Z","date_updated":"2023-02-23T11:05:48Z","status":"public","file":[{"file_size":574055,"file_name":"IST-2011-0007_IST-2011-0007.pdf","creator":"system","content_type":"application/pdf","relation":"main_file","date_created":"2018-12-12T11:53:27Z","date_updated":"2020-07-14T12:46:39Z","access_level":"open_access","checksum":"06bf6dfc97f6006e3fd0e9a3f31bc961","file_id":"5488"}],"doi":"10.15479/AT:IST-2011-0007","publication_identifier":{"issn":["2664-1690"]},"pubrep_id":"17","year":"2011","_id":"5381"},{"abstract":[{"text":"We consider two-player stochastic games played on a finite state space for an infinite num- ber of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with ω-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity games with respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition func- tion is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).","lang":"eng"}],"publisher":"IST Austria","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","type":"technical_report","file_date_updated":"2020-07-14T12:46:40Z","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","language":[{"iso":"eng"}],"title":"Robustness of structurally equivalent concurrent parity games","date_published":"2011-06-27T00:00:00Z","day":"27","oa":1,"ddc":["000","005"],"_id":"5382","year":"2011","pubrep_id":"18","publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2011-0006","file":[{"file_size":335997,"file_name":"IST-2011-0006_IST-2011-0006.pdf","creator":"system","content_type":"application/pdf","date_created":"2018-12-12T11:54:24Z","date_updated":"2020-07-14T12:46:40Z","relation":"main_file","access_level":"open_access","file_id":"5546","checksum":"1322b652d6ab07eb5248298a3f91c1cf"}],"status":"public","date_updated":"2023-02-23T11:23:01Z","date_created":"2018-12-12T11:39:00Z","oa_version":"Published Version","department":[{"_id":"KrCh"}],"related_material":{"record":[{"id":"3341","relation":"later_version","status":"public"}]},"citation":{"chicago":"Chatterjee, Krishnendu. <i>Robustness of Structurally Equivalent Concurrent Parity Games</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0006\">https://doi.org/10.15479/AT:IST-2011-0006</a>.","ieee":"K. Chatterjee, <i>Robustness of structurally equivalent concurrent parity games</i>. IST Austria, 2011.","mla":"Chatterjee, Krishnendu. <i>Robustness of Structurally Equivalent Concurrent Parity Games</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0006\">10.15479/AT:IST-2011-0006</a>.","short":"K. Chatterjee, Robustness of Structurally Equivalent Concurrent Parity Games, IST Austria, 2011.","apa":"Chatterjee, K. (2011). <i>Robustness of structurally equivalent concurrent parity games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0006\">https://doi.org/10.15479/AT:IST-2011-0006</a>","ama":"Chatterjee K. <i>Robustness of Structurally Equivalent Concurrent Parity Games</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0006\">10.15479/AT:IST-2011-0006</a>","ista":"Chatterjee K. 2011. Robustness of structurally equivalent concurrent parity games, IST Austria, 18p."},"page":"18","month":"06","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"}]},{"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:40Z","publication_status":"published","type":"technical_report","abstract":[{"text":"We present a new decidable logic called TREX for expressing constraints about imperative tree data structures. In particular, TREX supports a transitive closure operator that can express reachability constraints, which often appear in data structure invariants. We show that our logic is closed under weakest precondition computation, which enables its use for automated software verification. We further show that satisfiability of formulas in TREX is decidable in NP. The low complexity makes it an attractive alternative to more expensive logics such as monadic second-order logic (MSOL) over trees, which have been traditionally used for reasoning about tree data structures.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","ddc":["000","006"],"oa":1,"title":"On an efficient decision procedure for imperative tree data structures","date_published":"2011-04-26T00:00:00Z","day":"26","language":[{"iso":"eng"}],"file":[{"file_name":"IST-2011-0005_IST-2011-0005.pdf","file_size":619053,"creator":"system","content_type":"application/pdf","file_id":"5462","checksum":"b20029184c4a819c5f4466a4a3d238b5","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:53:01Z","date_updated":"2020-07-14T12:46:40Z"}],"publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2011-0005","pubrep_id":"19","_id":"5383","year":"2011","month":"04","page":"25","author":[{"id":"447BFB88-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas","last_name":"Wies","full_name":"Wies, Thomas"},{"first_name":"Marco","last_name":"Muñiz","full_name":"Muñiz, Marco"},{"full_name":"Kuncak, Viktor","last_name":"Kuncak","first_name":"Viktor"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"3323"}]},"citation":{"chicago":"Wies, Thomas, Marco Muñiz, and Viktor Kuncak. <i>On an Efficient Decision Procedure for Imperative Tree Data Structures</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0005\">https://doi.org/10.15479/AT:IST-2011-0005</a>.","ieee":"T. Wies, M. Muñiz, and V. Kuncak, <i>On an efficient decision procedure for imperative tree data structures</i>. IST Austria, 2011.","mla":"Wies, Thomas, et al. <i>On an Efficient Decision Procedure for Imperative Tree Data Structures</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0005\">10.15479/AT:IST-2011-0005</a>.","short":"T. Wies, M. Muñiz, V. Kuncak, On an Efficient Decision Procedure for Imperative Tree Data Structures, IST Austria, 2011.","apa":"Wies, T., Muñiz, M., &#38; Kuncak, V. (2011). <i>On an efficient decision procedure for imperative tree data structures</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0005\">https://doi.org/10.15479/AT:IST-2011-0005</a>","ama":"Wies T, Muñiz M, Kuncak V. <i>On an Efficient Decision Procedure for Imperative Tree Data Structures</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0005\">10.15479/AT:IST-2011-0005</a>","ista":"Wies T, Muñiz M, Kuncak V. 2011. On an efficient decision procedure for imperative tree data structures, IST Austria, 25p."},"date_updated":"2023-02-23T11:22:16Z","date_created":"2018-12-12T11:39:01Z","oa_version":"Published Version","department":[{"_id":"ToHe"}],"status":"public"},{"department":[{"_id":"KrCh"}],"oa_version":"Published Version","date_created":"2018-12-12T11:39:01Z","date_updated":"2023-02-23T11:05:53Z","status":"public","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"first_name":"Mathieu","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87","last_name":"Tracol","full_name":"Tracol, Mathieu"}],"month":"04","page":"30","citation":{"ieee":"K. Chatterjee and M. Tracol, <i>Decidable problems for probabilistic automata on infinite words</i>. IST Austria, 2011.","short":"K. Chatterjee, M. Tracol, Decidable Problems for Probabilistic Automata on Infinite Words, IST Austria, 2011.","mla":"Chatterjee, Krishnendu, and Mathieu Tracol. <i>Decidable Problems for Probabilistic Automata on Infinite Words</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0004\">10.15479/AT:IST-2011-0004</a>.","chicago":"Chatterjee, Krishnendu, and Mathieu Tracol. <i>Decidable Problems for Probabilistic Automata on Infinite Words</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0004\">https://doi.org/10.15479/AT:IST-2011-0004</a>.","ista":"Chatterjee K, Tracol M. 2011. Decidable problems for probabilistic automata on infinite words, IST Austria, 30p.","apa":"Chatterjee, K., &#38; Tracol, M. (2011). <i>Decidable problems for probabilistic automata on infinite words</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0004\">https://doi.org/10.15479/AT:IST-2011-0004</a>","ama":"Chatterjee K, Tracol M. <i>Decidable Problems for Probabilistic Automata on Infinite Words</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0004\">10.15479/AT:IST-2011-0004</a>"},"related_material":{"record":[{"id":"2957","relation":"later_version","status":"public"}]},"pubrep_id":"20","year":"2011","_id":"5384","file":[{"file_id":"5545","checksum":"f5a0f664fadc335990f5fcf138df19f1","date_updated":"2020-07-14T12:46:40Z","relation":"main_file","date_created":"2018-12-12T11:54:23Z","access_level":"open_access","content_type":"application/pdf","creator":"system","file_name":"IST-2011-004_IST-2011-0004.pdf","file_size":570827}],"doi":"10.15479/AT:IST-2011-0004","publication_identifier":{"issn":["2664-1690"]},"day":"11","title":"Decidable problems for probabilistic automata on infinite words","date_published":"2011-04-11T00:00:00Z","language":[{"iso":"eng"}],"ddc":["000","005"],"oa":1,"publication_status":"published","type":"technical_report","publisher":"IST Austria","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether for every ε > 0 there is a word that is accepted with probability at least 1 − ε. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions."}],"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:40Z"},{"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","publication_status":"published","type":"technical_report","day":"04","title":"Temporal specifications with accumulative values","date_published":"2011-04-04T00:00:00Z","doi":"10.15479/AT:IST-2011-0003","project":[{"call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"COMponent-Based Embedded Systems design Techniques","grant_number":"215543","call_identifier":"FP7","_id":"25EFB36C-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","grant_number":"267989","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","grant_number":"214373","name":"Design for Embedded Systems","_id":"25F1337C-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"file":[{"access_level":"open_access","date_updated":"2020-07-14T12:46:41Z","relation":"main_file","date_created":"2018-12-12T11:53:00Z","checksum":"8491d0d48c4911620ecd5350b413c11e","file_id":"5461","content_type":"application/pdf","creator":"system","file_size":366281,"file_name":"IST-2011-0003_IST-2011-0003.pdf"}],"_id":"5385","citation":{"apa":"Boker, U., Chatterjee, K., Henzinger, T. A., &#38; Kupferman, O. (2011). <i>Temporal specifications with accumulative values</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0003\">https://doi.org/10.15479/AT:IST-2011-0003</a>","ama":"Boker U, Chatterjee K, Henzinger TA, Kupferman O. <i>Temporal Specifications with Accumulative Values</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0003\">10.15479/AT:IST-2011-0003</a>","ista":"Boker U, Chatterjee K, Henzinger TA, Kupferman O. 2011. Temporal specifications with accumulative values, IST Austria, 14p.","chicago":"Boker, Udi, Krishnendu Chatterjee, Thomas A Henzinger, and Orna Kupferman. <i>Temporal Specifications with Accumulative Values</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0003\">https://doi.org/10.15479/AT:IST-2011-0003</a>.","ieee":"U. Boker, K. Chatterjee, T. A. Henzinger, and O. Kupferman, <i>Temporal specifications with accumulative values</i>. IST Austria, 2011.","mla":"Boker, Udi, et al. <i>Temporal Specifications with Accumulative Values</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0003\">10.15479/AT:IST-2011-0003</a>.","short":"U. Boker, K. Chatterjee, T.A. Henzinger, O. Kupferman, Temporal Specifications with Accumulative Values, IST Austria, 2011."},"month":"04","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:02Z","date_updated":"2023-02-23T11:23:41Z","file_date_updated":"2020-07-14T12:46:41Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"There is recently a significant effort to add quantitative objectives to formal verification and synthesis. We introduce and investigate the extension of temporal logics with quantitative atomic assertions, aiming for a general and flexible framework for quantitative-oriented specifications. In the heart of quantitative objectives lies the accumulation of values along a computation. It is either the accumulated summation, as with the energy objectives, or the accumulated average, as with the mean-payoff objectives. We investigate the extension of temporal logics with the prefix-accumulation assertions Sum(v) ≥ c and Avg(v) ≥ c, where v is a numeric variable of the system, c is a constant rational number, and Sum(v) and Avg(v) denote the accumulated sum and average of the values of v from the beginning of the computation up to the current point of time. We also allow the path-accumulation assertions LimInfAvg(v) ≥ c and LimSupAvg(v) ≥ c, referring to the average value along an entire computation. We study the border of decidability for extensions of various temporal logics. In particular, we show that extending the fragment of CTL that has only the EX, EF, AX, and AG temporal modalities by prefix-accumulation assertions and extending LTL with path-accumulation assertions, result in temporal logics whose model-checking problem is decidable. The extended logics allow to significantly extend the currently known energy and mean-payoff objectives. Moreover, the prefix-accumulation assertions may be refined with “controlled-accumulation”, allowing, for example, to specify constraints on the average waiting time between a request and a grant. On the negative side, we show that the fragment we point to is, in a sense, the maximal logic whose extension with prefix-accumulation assertions permits a decidable model-checking procedure. Extending a temporal logic that has the EG or EU modalities, and in particular CTL and LTL, makes the problem undecidable.","lang":"eng"}],"oa":1,"ddc":["000","004"],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"ec_funded":1,"year":"2011","pubrep_id":"21","related_material":{"record":[{"relation":"later_version","status":"public","id":"2038"},{"status":"public","relation":"later_version","id":"3356"}]},"author":[{"first_name":"Udi","id":"31E297B6-F248-11E8-B48F-1D18A9856A87","full_name":"Boker, Udi","last_name":"Boker"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"orcid":"0000−0002−2985−7724","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kupferman","full_name":"Kupferman, Orna","first_name":"Orna"}],"page":"14","status":"public","oa_version":"Published Version"},{"oa":1,"ddc":["000"],"language":[{"iso":"eng"}],"title":"Enforcing topological constraints in random field image segmentation","date_published":"2011-03-28T00:00:00Z","day":"28","file_date_updated":"2020-07-14T12:46:41Z","has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"abstract":[{"lang":"eng","text":"We introduce TopoCut: a new way to integrate knowledge about topological properties (TPs) into random field image segmentation model. Instead of including TPs as additional constraints during minimization of the energy function, we devise an efficient algorithm for modifying the unary potentials such that the resulting segmentation is guaranteed with the desired properties. Our method is more flexible in the sense that it handles more topology constraints than previous methods, which were only able to enforce pairwise or global connectivity. In particular, our method is very fast, making it for the first time possible to enforce global topological properties in practical image segmentation tasks."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","publication_status":"published","type":"technical_report","related_material":{"record":[{"status":"public","relation":"later_version","id":"3336"}]},"citation":{"ieee":"C. Chen, D. Freedman, and C. Lampert, <i>Enforcing topological constraints in random field image segmentation</i>. IST Austria, 2011.","short":"C. Chen, D. Freedman, C. Lampert, Enforcing Topological Constraints in Random Field Image Segmentation, IST Austria, 2011.","mla":"Chen, Chao, et al. <i>Enforcing Topological Constraints in Random Field Image Segmentation</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0002\">10.15479/AT:IST-2011-0002</a>.","chicago":"Chen, Chao, Daniel Freedman, and Christoph Lampert. <i>Enforcing Topological Constraints in Random Field Image Segmentation</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0002\">https://doi.org/10.15479/AT:IST-2011-0002</a>.","ista":"Chen C, Freedman D, Lampert C. 2011. Enforcing topological constraints in random field image segmentation, IST Austria, 69p.","apa":"Chen, C., Freedman, D., &#38; Lampert, C. (2011). <i>Enforcing topological constraints in random field image segmentation</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0002\">https://doi.org/10.15479/AT:IST-2011-0002</a>","ama":"Chen C, Freedman D, Lampert C. <i>Enforcing Topological Constraints in Random Field Image Segmentation</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0002\">10.15479/AT:IST-2011-0002</a>"},"page":"69","month":"03","author":[{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","last_name":"Chen","full_name":"Chen, Chao"},{"first_name":"Daniel","full_name":"Freedman, Daniel","last_name":"Freedman"},{"first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","last_name":"Lampert"}],"status":"public","date_updated":"2023-02-23T11:22:48Z","date_created":"2018-12-12T11:39:02Z","oa_version":"Published Version","department":[{"_id":"ChLa"}],"publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2011-0002","file":[{"file_name":"IST-2011-0002_IST-2011-0002.pdf","file_size":26390601,"creator":"system","content_type":"application/pdf","checksum":"ad64c2add5fe2ad10e9d5c669f3f9526","file_id":"5495","relation":"main_file","date_created":"2018-12-12T11:53:34Z","access_level":"open_access","date_updated":"2020-07-14T12:46:41Z"}],"_id":"5386","year":"2011","pubrep_id":"22"},{"citation":{"chicago":"Lampert, Christoph. “Maximum Margin Multi-Label Structured Prediction.” Neural Information Processing Systems, 2011.","ieee":"C. Lampert, “Maximum margin multi-label structured prediction,” presented at the NIPS: Neural Information Processing Systems, Granada, Spain, 2011.","mla":"Lampert, Christoph. <i>Maximum Margin Multi-Label Structured Prediction</i>. Neural Information Processing Systems, 2011.","short":"C. Lampert, in:, Neural Information Processing Systems, 2011.","apa":"Lampert, C. (2011). Maximum margin multi-label structured prediction. Presented at the NIPS: Neural Information Processing Systems, Granada, Spain: Neural Information Processing Systems.","ama":"Lampert C. Maximum margin multi-label structured prediction. In: Neural Information Processing Systems; 2011.","ista":"Lampert C. 2011. Maximum margin multi-label structured prediction. NIPS: Neural Information Processing Systems."},"related_material":{"record":[{"status":"public","relation":"later_version","id":"3322"}]},"author":[{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","last_name":"Lampert"}],"month":"12","status":"public","department":[{"_id":"ChLa"}],"publist_id":"3522","oa_version":"None","date_updated":"2023-10-17T11:47:35Z","date_created":"2018-12-11T12:01:45Z","conference":{"name":"NIPS: Neural Information Processing Systems","end_date":"2011-12-14","start_date":"2011-12-12","location":"Granada, Spain"},"year":"2011","_id":"3163","language":[{"iso":"eng"}],"day":"01","title":"Maximum margin multi-label structured prediction","date_published":"2011-12-01T00:00:00Z","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Neural Information Processing Systems","abstract":[{"text":"We study multi-label prediction for structured output sets, a problem that occurs, for example, in object detection in images, secondary structure prediction in computational biology, and graph matching with symmetries. Conventional multilabel classification techniques are typically not applicable in this situation, because they require explicit enumeration of the label set, which is infeasible in case of structured outputs. Relying on techniques originally designed for single-label structured prediction, in particular structured support vector machines, results in reduced prediction accuracy, or leads to infeasible optimization problems. In this work we derive a maximum-margin training formulation for multi-label structured prediction that remains computationally tractable while achieving high prediction accuracy. It also shares most beneficial properties with single-label maximum-margin approaches, in particular formulation as a convex optimization problem, efficient working set training, and PAC-Bayesian generalization bounds.","lang":"eng"}],"publication_status":"published","scopus_import":1,"quality_controlled":"1","type":"conference"},{"language":[{"iso":"eng"}],"day":"05","date_published":"2011-12-05T00:00:00Z","title":"Solving recursion-free Horn clauses over LI+UIF","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","abstract":[{"text":"Verification of programs with procedures, multi-threaded programs, and higher-order functional programs can be effectively au- tomated using abstraction and refinement schemes that rely on spurious counterexamples for abstraction discovery. The analysis of counterexam- ples can be automated by a series of interpolation queries, or, alterna- tively, as a constraint solving query expressed by a set of recursion free Horn clauses. (A set of interpolation queries can be formulated as a single constraint over Horn clauses with linear dependency structure between the unknown relations.) In this paper we present an algorithm for solving recursion free Horn clauses over a combined theory of linear real/rational arithmetic and uninterpreted functions. Our algorithm performs resolu- tion to deal with the clausal structure and relies on partial solutions to deal with (non-local) instances of functionality axioms.","lang":"eng"}],"quality_controlled":"1","publication_status":"published","type":"conference","alternative_title":["LNCS"],"intvolume":"      7078","status":"public","department":[{"_id":"ToHe"}],"oa_version":"None","publist_id":"3383","date_created":"2018-12-11T12:02:20Z","date_updated":"2021-01-12T07:42:15Z","editor":[{"first_name":"Hongseok","last_name":"Yang","full_name":"Yang, Hongseok"}],"citation":{"short":"A. Gupta, C. Popeea, A. Rybalchenko, in:, H. Yang (Ed.), Springer, 2011, pp. 188–203.","mla":"Gupta, Ashutosh, et al. <i>Solving Recursion-Free Horn Clauses over LI+UIF</i>. Edited by Hongseok Yang, vol. 7078, Springer, 2011, pp. 188–203, doi:<a href=\"https://doi.org/10.1007/978-3-642-25318-8_16\">10.1007/978-3-642-25318-8_16</a>.","ieee":"A. Gupta, C. Popeea, and A. Rybalchenko, “Solving recursion-free Horn clauses over LI+UIF,” presented at the APLAS: Asian Symposium on Programming Languages and Systems, Kenting, Taiwan, 2011, vol. 7078, pp. 188–203.","chicago":"Gupta, Ashutosh, Corneliu Popeea, and Andrey Rybalchenko. “Solving Recursion-Free Horn Clauses over LI+UIF.” edited by Hongseok Yang, 7078:188–203. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-25318-8_16\">https://doi.org/10.1007/978-3-642-25318-8_16</a>.","ista":"Gupta A, Popeea C, Rybalchenko A. 2011. Solving recursion-free Horn clauses over LI+UIF. APLAS: Asian Symposium on Programming Languages and Systems, LNCS, vol. 7078, 188–203.","ama":"Gupta A, Popeea C, Rybalchenko A. Solving recursion-free Horn clauses over LI+UIF. In: Yang H, ed. Vol 7078. Springer; 2011:188-203. doi:<a href=\"https://doi.org/10.1007/978-3-642-25318-8_16\">10.1007/978-3-642-25318-8_16</a>","apa":"Gupta, A., Popeea, C., &#38; Rybalchenko, A. (2011). Solving recursion-free Horn clauses over LI+UIF. In H. Yang (Ed.) (Vol. 7078, pp. 188–203). Presented at the APLAS: Asian Symposium on Programming Languages and Systems, Kenting, Taiwan: Springer. <a href=\"https://doi.org/10.1007/978-3-642-25318-8_16\">https://doi.org/10.1007/978-3-642-25318-8_16</a>"},"author":[{"id":"335E5684-F248-11E8-B48F-1D18A9856A87","first_name":"Ashutosh","last_name":"Gupta","full_name":"Gupta, Ashutosh"},{"first_name":"Corneliu","last_name":"Popeea","full_name":"Popeea, Corneliu"},{"full_name":"Rybalchenko, Andrey","last_name":"Rybalchenko","first_name":"Andrey"}],"page":"188 - 203","month":"12","conference":{"end_date":"2011-12-07","name":"APLAS: Asian Symposium on Programming Languages and Systems","start_date":"2011-12-05","location":"Kenting, Taiwan"},"year":"2011","_id":"3264","doi":"10.1007/978-3-642-25318-8_16","project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"267989","name":"Quantitative Reactive Modeling"}],"volume":7078,"ec_funded":1},{"volume":24,"year":"2011","_id":"3266","conference":{"start_date":"2011-12-12","location":"Granada, Spain","end_date":"2011-12-14","name":"NIPS: Neural Information Processing Systems"},"page":"1827 - 1835","month":"12","author":[{"last_name":"Ion","full_name":"Ion, Adrian","id":"29F89302-F248-11E8-B48F-1D18A9856A87","first_name":"Adrian"},{"last_name":"Carreira","full_name":"Carreira, Joao","first_name":"Joao"},{"first_name":"Cristian","last_name":"Sminchisescu","full_name":"Sminchisescu, Cristian"}],"citation":{"ama":"Ion A, Carreira J, Sminchisescu C. Probabilistic joint image segmentation and labeling. In: <i>NIPS Proceedings</i>. Vol 24. Neural Information Processing Systems Foundation; 2011:1827-1835.","apa":"Ion, A., Carreira, J., &#38; Sminchisescu, C. (2011). Probabilistic joint image segmentation and labeling. In <i>NIPS Proceedings</i> (Vol. 24, pp. 1827–1835). Granada, Spain: Neural Information Processing Systems Foundation.","ista":"Ion A, Carreira J, Sminchisescu C. 2011. Probabilistic joint image segmentation and labeling. NIPS Proceedings. NIPS: Neural Information Processing Systems vol. 24, 1827–1835.","chicago":"Ion, Adrian, Joao Carreira, and Cristian Sminchisescu. “Probabilistic Joint Image Segmentation and Labeling.” In <i>NIPS Proceedings</i>, 24:1827–35. Neural Information Processing Systems Foundation, 2011.","short":"A. Ion, J. Carreira, C. Sminchisescu, in:, NIPS Proceedings, Neural Information Processing Systems Foundation, 2011, pp. 1827–1835.","mla":"Ion, Adrian, et al. “Probabilistic Joint Image Segmentation and Labeling.” <i>NIPS Proceedings</i>, vol. 24, Neural Information Processing Systems Foundation, 2011, pp. 1827–35.","ieee":"A. Ion, J. Carreira, and C. Sminchisescu, “Probabilistic joint image segmentation and labeling,” in <i>NIPS Proceedings</i>, Granada, Spain, 2011, vol. 24, pp. 1827–1835."},"date_created":"2018-12-11T12:02:21Z","date_updated":"2021-01-12T07:42:15Z","oa_version":"None","publist_id":"3381","department":[{"_id":"HeEd"}],"status":"public","intvolume":"        24","quality_controlled":"1","type":"conference","scopus_import":1,"publication_status":"published","abstract":[{"lang":"eng","text":"We present a joint image segmentation and labeling model (JSL) which, given a bag of figure-ground segment hypotheses extracted at multiple image locations and scales, constructs a joint probability distribution over both the compatible image interpretations (tilings or image segmentations) composed from those segments, and over their labeling into categories. The process of drawing samples from the joint distribution can be interpreted as first sampling tilings, modeled as maximal cliques, from a graph connecting spatially non-overlapping segments in the bag [1], followed by sampling labels for those segments, conditioned on the choice of a particular tiling. We learn the segmentation and labeling parameters jointly, based on Maximum Likelihood with a novel Incremental Saddle Point estimation procedure. The partition function over tilings and labelings is increasingly more accurately approximated by including incorrect configurations that a not-yet-competent model rates probable during learning. We show that the proposed methodologymatches the current state of the art in the Stanford dataset [2], as well as in VOC2010, where 41.7% accuracy on the test set is achieved."}],"publisher":"Neural Information Processing Systems Foundation","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Probabilistic joint image segmentation and labeling","date_published":"2011-12-01T00:00:00Z","day":"01","language":[{"iso":"eng"}],"publication":"NIPS Proceedings"},{"year":"2011","_id":"3267","issue":"3","doi":"10.1007/s00454-010-9322-8","volume":45,"status":"public","intvolume":"        45","date_created":"2018-12-11T12:02:21Z","date_updated":"2023-02-21T16:07:10Z","publist_id":"3379","department":[{"_id":"HeEd"}],"oa_version":"None","related_material":{"record":[{"id":"10909","status":"public","relation":"earlier_version"}]},"citation":{"ieee":"C. Chen and D. Freedman, “Hardness results for homology localization,” <i>Discrete &#38; Computational Geometry</i>, vol. 45, no. 3. Springer, pp. 425–448, 2011.","mla":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” <i>Discrete &#38; Computational Geometry</i>, vol. 45, no. 3, Springer, 2011, pp. 425–48, doi:<a href=\"https://doi.org/10.1007/s00454-010-9322-8\">10.1007/s00454-010-9322-8</a>.","short":"C. Chen, D. Freedman, Discrete &#38; Computational Geometry 45 (2011) 425–448.","chicago":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2011. <a href=\"https://doi.org/10.1007/s00454-010-9322-8\">https://doi.org/10.1007/s00454-010-9322-8</a>.","ista":"Chen C, Freedman D. 2011. Hardness results for homology localization. Discrete &#38; Computational Geometry. 45(3), 425–448.","apa":"Chen, C., &#38; Freedman, D. (2011). Hardness results for homology localization. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-010-9322-8\">https://doi.org/10.1007/s00454-010-9322-8</a>","ama":"Chen C, Freedman D. Hardness results for homology localization. <i>Discrete &#38; Computational Geometry</i>. 2011;45(3):425-448. doi:<a href=\"https://doi.org/10.1007/s00454-010-9322-8\">10.1007/s00454-010-9322-8</a>"},"page":"425 - 448","month":"01","author":[{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","last_name":"Chen","full_name":"Chen, Chao"},{"first_name":"Daniel","last_name":"Freedman","full_name":"Freedman, Daniel"}],"abstract":[{"text":"We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius. For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume. As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius. Our work is restricted to homology over the ℤ2 field.","lang":"eng"}],"publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"publication_status":"published","quality_controlled":"1","type":"journal_article","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"title":"Hardness results for homology localization","date_published":"2011-01-14T00:00:00Z","day":"14"},{"date_published":"2011-07-19T00:00:00Z","title":"Perceptual global illumination cancellation in complex projection environments","day":"19","publication":"Computer Graphics Forum","type":"journal_article","scopus_import":1,"quality_controlled":"1","publication_status":"published","publisher":"Wiley-Blackwell","date_updated":"2021-01-12T07:42:16Z","date_created":"2018-12-11T12:02:22Z","publist_id":"3377","department":[{"_id":"HeEd"}],"intvolume":"        30","month":"07","article_type":"original","citation":{"chicago":"Sheng, Yu, Barbara Cutler, Chao Chen, and Joshua Nasman. “Perceptual Global Illumination Cancellation in Complex Projection Environments.” <i>Computer Graphics Forum</i>. Wiley-Blackwell, 2011. <a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">https://doi.org/10.1111/j.1467-8659.2011.01985.x</a>.","ieee":"Y. Sheng, B. Cutler, C. Chen, and J. Nasman, “Perceptual global illumination cancellation in complex projection environments,” <i>Computer Graphics Forum</i>, vol. 30, no. 4. Wiley-Blackwell, pp. 1261–1268, 2011.","short":"Y. Sheng, B. Cutler, C. Chen, J. Nasman, Computer Graphics Forum 30 (2011) 1261–1268.","mla":"Sheng, Yu, et al. “Perceptual Global Illumination Cancellation in Complex Projection Environments.” <i>Computer Graphics Forum</i>, vol. 30, no. 4, Wiley-Blackwell, 2011, pp. 1261–68, doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">10.1111/j.1467-8659.2011.01985.x</a>.","apa":"Sheng, Y., Cutler, B., Chen, C., &#38; Nasman, J. (2011). Perceptual global illumination cancellation in complex projection environments. <i>Computer Graphics Forum</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">https://doi.org/10.1111/j.1467-8659.2011.01985.x</a>","ama":"Sheng Y, Cutler B, Chen C, Nasman J. Perceptual global illumination cancellation in complex projection environments. <i>Computer Graphics Forum</i>. 2011;30(4):1261-1268. doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">10.1111/j.1467-8659.2011.01985.x</a>","ista":"Sheng Y, Cutler B, Chen C, Nasman J. 2011. Perceptual global illumination cancellation in complex projection environments. Computer Graphics Forum. 30(4), 1261–1268."},"issue":"4","_id":"3269","main_file_link":[{"open_access":"1","url":"http://www.cs.cmu.edu/%7Eshengyu/download/egsr2011_paper.pdf"}],"volume":30,"doi":"10.1111/j.1467-8659.2011.01985.x","language":[{"iso":"eng"}],"oa":1,"article_processing_charge":"No","abstract":[{"lang":"eng","text":"The unintentional scattering of light between neighboring surfaces in complex projection environments increases the brightness and decreases the contrast, disrupting the appearance of the desired imagery. To achieve satisfactory projection results, the inverse problem of global illumination must be solved to cancel this secondary scattering. In this paper, we propose a global illumination cancellation method that minimizes the perceptual difference between the desired imagery and the actual total illumination in the resulting physical environment. Using Gauss-Newton and active set methods, we design a fast solver for the bound constrained nonlinear least squares problem raised by the perceptual error metrics. Our solver is further accelerated with a CUDA implementation and multi-resolution method to achieve 1–2 fps for problems with approximately 3000 variables. We demonstrate the global illumination cancellation algorithm with our multi-projector system. Results show that our method preserves the color fidelity of the desired imagery significantly better than previous methods."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","status":"public","page":"1261 - 1268","author":[{"first_name":"Yu","full_name":"Sheng, Yu","last_name":"Sheng"},{"full_name":"Cutler, Barbara","last_name":"Cutler","first_name":"Barbara"},{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","last_name":"Chen","full_name":"Chen, Chao"},{"last_name":"Nasman","full_name":"Nasman, Joshua","first_name":"Joshua"}],"year":"2011"},{"type":"conference","quality_controlled":"1","publication_status":"published","abstract":[{"text":"The persistence diagram of a filtered simplicial com- plex is usually computed by reducing the boundary matrix of the complex. We introduce a simple op- timization technique: by processing the simplices of the complex in decreasing dimension, we can “kill” columns (i.e., set them to zero) without reducing them. This technique completely avoids reduction on roughly half of the columns. We demonstrate that this idea significantly improves the running time of the reduction algorithm in practice. We also give an output-sensitive complexity analysis for the new al- gorithm which yields to sub-cubic asymptotic bounds under certain assumptions.","lang":"eng"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"TU Dortmund","date_published":"2011-01-01T00:00:00Z","title":"Persistent homology computation with a twist","day":"01","language":[{"iso":"eng"}],"year":"2011","_id":"3270","conference":{"end_date":"2011-03-30","name":"EuroCG: European Workshop on Computational Geometry","location":"Morschach, Switzerland","start_date":"2011-03-28"},"date_updated":"2021-01-12T07:42:17Z","date_created":"2018-12-11T12:02:22Z","oa_version":"None","department":[{"_id":"HeEd"}],"publist_id":"3376","status":"public","page":"197 - 200","month":"01","author":[{"full_name":"Chen, Chao","last_name":"Chen","first_name":"Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Michael","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299","full_name":"Kerber, Michael","last_name":"Kerber"}],"citation":{"chicago":"Chen, Chao, and Michael Kerber. “Persistent Homology Computation with a Twist,” 197–200. TU Dortmund, 2011.","ieee":"C. Chen and M. Kerber, “Persistent homology computation with a twist,” presented at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland, 2011, pp. 197–200.","short":"C. Chen, M. Kerber, in:, TU Dortmund, 2011, pp. 197–200.","mla":"Chen, Chao, and Michael Kerber. <i>Persistent Homology Computation with a Twist</i>. TU Dortmund, 2011, pp. 197–200.","apa":"Chen, C., &#38; Kerber, M. (2011). Persistent homology computation with a twist (pp. 197–200). Presented at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland: TU Dortmund.","ama":"Chen C, Kerber M. Persistent homology computation with a twist. In: TU Dortmund; 2011:197-200.","ista":"Chen C, Kerber M. 2011. Persistent homology computation with a twist. EuroCG: European Workshop on Computational Geometry, 197–200."}},{"day":"14","title":"Efficient computation of persistent homology for cubical data","date_published":"2011-11-14T00:00:00Z","publication":"Topological Methods in Data Analysis and Visualization II","language":[{"iso":"eng"}],"alternative_title":["Theory, Algorithms, and Applications"],"quality_controlled":"1","scopus_import":1,"type":"book_chapter","publication_status":"published","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","abstract":[{"lang":"eng","text":"In this paper we present an efficient framework for computation of persis- tent homology of cubical data in arbitrary dimensions. An existing algorithm using simplicial complexes is adapted to the setting of cubical complexes. The proposed approach enables efficient application of persistent homology in domains where the data is naturally given in a cubical form. By avoiding triangulation of the data, we significantly reduce the size of the complex. We also present a data-structure de- signed to compactly store and quickly manipulate cubical complexes. By means of numerical experiments, we show high speed and memory efficiency of our ap- proach. We compare our framework to other available implementations, showing its superiority. Finally, we report performance on selected 3D and 4D data-sets."}],"author":[{"last_name":"Wagner","full_name":"Wagner, Hubert","first_name":"Hubert"},{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","full_name":"Chen, Chao","last_name":"Chen"},{"first_name":"Erald","full_name":"Vuçini, Erald","last_name":"Vuçini"}],"month":"11","page":"91 - 106","editor":[{"full_name":"Peikert, Ronald","last_name":"Peikert","first_name":"Ronald"},{"full_name":"Hauser, Helwig","last_name":"Hauser","first_name":"Helwig"},{"last_name":"Carr","full_name":"Carr, Hamish","first_name":"Hamish"},{"first_name":"Raphael","full_name":"Fuchs, Raphael","last_name":"Fuchs"}],"citation":{"ieee":"H. Wagner, C. Chen, and E. Vuçini, “Efficient computation of persistent homology for cubical data,” in <i>Topological Methods in Data Analysis and Visualization II</i>, R. Peikert, H. Hauser, H. Carr, and R. Fuchs, Eds. Springer, 2011, pp. 91–106.","short":"H. Wagner, C. Chen, E. Vuçini, in:, R. Peikert, H. Hauser, H. Carr, R. Fuchs (Eds.), Topological Methods in Data Analysis and Visualization II, Springer, 2011, pp. 91–106.","mla":"Wagner, Hubert, et al. “Efficient Computation of Persistent Homology for Cubical Data.” <i>Topological Methods in Data Analysis and Visualization II</i>, edited by Ronald Peikert et al., Springer, 2011, pp. 91–106, doi:<a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">10.1007/978-3-642-23175-9_7</a>.","chicago":"Wagner, Hubert, Chao Chen, and Erald Vuçini. “Efficient Computation of Persistent Homology for Cubical Data.” In <i>Topological Methods in Data Analysis and Visualization II</i>, edited by Ronald Peikert, Helwig Hauser, Hamish Carr, and Raphael Fuchs, 91–106. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">https://doi.org/10.1007/978-3-642-23175-9_7</a>.","ista":"Wagner H, Chen C, Vuçini E. 2011.Efficient computation of persistent homology for cubical data. In: Topological Methods in Data Analysis and Visualization II. Theory, Algorithms, and Applications, , 91–106.","apa":"Wagner, H., Chen, C., &#38; Vuçini, E. (2011). Efficient computation of persistent homology for cubical data. In R. Peikert, H. Hauser, H. Carr, &#38; R. Fuchs (Eds.), <i>Topological Methods in Data Analysis and Visualization II</i> (pp. 91–106). Springer. <a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">https://doi.org/10.1007/978-3-642-23175-9_7</a>","ama":"Wagner H, Chen C, Vuçini E. Efficient computation of persistent homology for cubical data. In: Peikert R, Hauser H, Carr H, Fuchs R, eds. <i>Topological Methods in Data Analysis and Visualization II</i>. Springer; 2011:91-106. doi:<a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">10.1007/978-3-642-23175-9_7</a>"},"publist_id":"3375","oa_version":"None","department":[{"_id":"HeEd"}],"date_created":"2018-12-11T12:02:23Z","date_updated":"2021-01-12T07:42:18Z","status":"public","doi":"10.1007/978-3-642-23175-9_7","year":"2011","_id":"3271"},{"language":[{"iso":"eng"}],"date_published":"2011-12-12T00:00:00Z","title":"Mechanics of adhesion and de‐adhesion in zebrafish germ layer progenitors","day":"12","alternative_title":["ISTA Thesis"],"degree_awarded":"PhD","article_processing_charge":"No","publisher":"Institute of Science and Technology Austria","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","type":"dissertation","publication_status":"published","citation":{"chicago":"Maître, Jean-Léon. “Mechanics of Adhesion and De‐adhesion in Zebrafish Germ Layer Progenitors.” Institute of Science and Technology Austria, 2011.","mla":"Maître, Jean-Léon. <i>Mechanics of Adhesion and De‐adhesion in Zebrafish Germ Layer Progenitors</i>. Institute of Science and Technology Austria, 2011.","short":"J.-L. Maître, Mechanics of Adhesion and De‐adhesion in Zebrafish Germ Layer Progenitors, Institute of Science and Technology Austria, 2011.","ieee":"J.-L. Maître, “Mechanics of adhesion and de‐adhesion in zebrafish germ layer progenitors,” Institute of Science and Technology Austria, 2011.","ama":"Maître J-L. Mechanics of adhesion and de‐adhesion in zebrafish germ layer progenitors. 2011.","apa":"Maître, J.-L. (2011). <i>Mechanics of adhesion and de‐adhesion in zebrafish germ layer progenitors</i>. Institute of Science and Technology Austria.","ista":"Maître J-L. 2011. Mechanics of adhesion and de‐adhesion in zebrafish germ layer progenitors. Institute of Science and Technology Austria."},"month":"12","author":[{"last_name":"Maître","full_name":"Maître, Jean-Léon","orcid":"0000-0002-3688-1474","id":"48F1E0D8-F248-11E8-B48F-1D18A9856A87","first_name":"Jean-Léon"}],"status":"public","date_updated":"2023-09-07T11:30:16Z","date_created":"2018-12-11T12:02:23Z","department":[{"_id":"CaHe"}],"publist_id":"3373","oa_version":"None","publication_identifier":{"issn":["2663-337X"]},"supervisor":[{"orcid":"0000-0002-0912-4566","full_name":"Heisenberg, Carl-Philipp J","last_name":"Heisenberg","first_name":"Carl-Philipp J","id":"39427864-F248-11E8-B48F-1D18A9856A87"}],"year":"2011","_id":"3273"},{"publication_identifier":{"issn":["2663-337X"]},"pubrep_id":"11","year":"2011","page":"141","author":[{"first_name":"Kathrin","id":"F44D762E-4F9D-11E9-B64C-9EB26CEFFB5F","full_name":"Schumann, Kathrin","last_name":"Schumann"}],"oa_version":"Published Version","status":"public","degree_awarded":"PhD","file_date_updated":"2021-02-22T11:24:30Z","article_processing_charge":"No","abstract":[{"text":"Chemokines organize immune cell trafficking by inducing either directed (tactic) or random (kinetic) migration and by activating integrins in order to support surface adhesion (haptic). Beyond that the same chemokines can establish clearly defined functional areas in secondary lymphoid organs. Until now it is unclear how chemokines can fulfill such diverse functions. One decisive prerequisite to explain these capacities is to know how chemokines are presented in tissue. In theory chemokines could occur either soluble or immobilized, and could be distributed either homogenously or as a concentration gradient. To dissect if and how the presenting mode of chemokines influences immune cells, I tested the response of dendritic cells (DCs) to differentially displayed chemokines. DCs are antigen presenting cells that reside in the periphery and migrate into draining lymph nodes (LNs) once exposed to inflammatory stimuli to activate naïve T cells. DCs are guided to and within the LN by the chemokine receptor CCR7, which has two ligands, the chemokines CCL19 and CCL21. Both CCR7 ligands are expressed by fibroblastic reticular cells in the LN, but differ in their ability to bind to heparan sulfate residues. CCL21 has a highly charged C-terminal extension, which mediates binding to anionic surfaces, whereas CCL19 is lacking such residues and likely distributes as a soluble molecule. This study shows that surface-bound CCL21 causes random, haptokinetic DC motility, which is confined to the chemokine coated area by insideout activation of β2 integrins that mediate cell binding to the surface. CCL19 on the other hand forms concentration gradients which trigger directional, chemotactic movement, but no surface adhesion. In addition DCs can actively manipulate this system by recruiting and activating serine proteases on their surfaces, which create - by proteolytically removing the adhesive C-terminus - a solubilized variant of CCL21 that functionally resembles CCL19. By generating a CCL21 concentration gradient DCs establish a positive feedback loop to recruit further DCs from the periphery to the CCL21 coated region. In addition DCs can sense chemotactic gradients as well as immobilized haptokinetic fields at the same time and integrate these signals. The result is chemotactically biased haptokinesis - directional migration confined to a chemokine coated track or area - which could explain the dynamic but spatially tightly controlled swarming leukocyte locomotion patterns that have been observed in lymphatic organs by intravital microscopists. The finding that DCs can approach soluble cues in a non-adhesive manner while they attach to surfaces coated with immobilized cues raises the question how these cells transmit intracellular forces to the environment, especially in the non-adherent migration mode. In order to migrate, cells have to generate and transmit force to the extracellular substrate. Force transmission is the prerequisite to procure an expansion of the leading edge and a forward motion of the whole cell body. In the current conceptions actin polymerization at the leading edge is coupled to extracellular ligands via the integrin family of transmembrane receptors, which allows the transmission of intracellular force. Against the paradigm of force transmission during migration, leukocytes, like DCs, are able to migrate in threedimensional environments without using integrin transmembrane receptors (Lämmermann et al., 2008). This reflects the biological function of leukocytes, as they can invade almost all tissues, whereby their migration has to be independent from the extracellular environment. How the cells can achieve this is unclear. For this study I examined DC migration in a defined threedimensional environment and highlighted actin-dynamics with the probe Lifeact-GFP. The result was that chemotactic DCs can switch between integrin-dependent and integrin- independent locomotion and can thereby adapt to the adhesive properties of their environment. If the cells are able to couple their actin cytoskeleton to the substrate, actin polymerization is entirely converted into protrusion. Without coupling the actin cortex undergoes slippage and retrograde actin flow can be observed. But retrograde actin flow can be completely compensated by higher actin polymerization rate keeping the migration velocity and the shape of the cells unaltered. Mesenchymal cells like fibroblast cannot balance the loss of adhesive interaction, cannot protrude into open space and, therefore, strictly depend on integrinmediated force coupling. This leukocyte specific phenomenon of “adaptive force transmission” endows these cells with the unique ability to transit and invade almost every type of tissue. ","lang":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","ddc":["570","579"],"oa":1,"language":[{"iso":"eng"}],"supervisor":[{"first_name":"Michael K","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6620-9179","last_name":"Sixt","full_name":"Sixt, Michael K"}],"file":[{"file_size":4487708,"file_name":"2011_Thesis_Kathrin_Schumann.pdf","creator":"dernst","content_type":"application/pdf","checksum":"e69eee6252660f0b694a2ea8923ddc72","file_id":"6177","access_level":"closed","date_updated":"2020-07-14T12:46:06Z","date_created":"2019-03-26T08:12:21Z","relation":"main_file"},{"file_name":"2011_Thesis_Schumann_noS.pdf","file_size":4313127,"creator":"dernst","content_type":"application/pdf","success":1,"checksum":"71727d63f424b5b446f68f4b87ecadc0","file_id":"9175","access_level":"open_access","relation":"main_file","date_updated":"2021-02-22T11:24:30Z","date_created":"2021-02-22T11:24:30Z"}],"_id":"3275","month":"03","acknowledgement":"I would like to express my sincere gratitude to the following people who made with their continuous support and encouragement this thesis possible: First, I want to thank Prof. Dr. Michael Sixt for his excellent supervision and mentoring, especially for the nice, relaxed working atmosphere, a lot of brilliant ideas and the freedom to work in my own way.\r\n\r\nProf. Dr. Reinhard Fässler for his constant support of the Sixt lab and for providing excellent working conditions. \r\n\r\nProf. Dr. Sanjiv Luther and Prof. Dr. Tobias Bollenbach for agreeing to be member of my thesis committee and to evaluate my work.\r\n\r\nDr. Walther Göhring, Carmen Schmitz, the Recombinant Protein Production core facility and the animal care takers for providing the “infrastructure” for this thesis. \r\n\r\nProf. Dr. Daniel Legler, Markus Bruckner and Dr. Julien Polleux for very fruitful collaborations and discussions.\r\n\r\nMy labmates for their help, a lot of discussions and to make the Sixt lab to a convenient place to work : Karin Hirsch, Tim Lämmeramnn, Holger Pflicke, Jörg Renkawitz, Michele Weber and Alexander Eichner All members of the Department of Molecular Medicine for their help. Especially I want to thank Sarah Schmidt, Karin Hirsch and Raphael Ruppert for their friendship, nice chats and their uncensored point of view. ","citation":{"chicago":"Schumann, Kathrin. “The Role of Chemotactic Gradients in Dendritic Cell Migration.” Institute of Science and Technology Austria, 2011.","mla":"Schumann, Kathrin. <i>The Role of Chemotactic Gradients in Dendritic Cell Migration</i>. Institute of Science and Technology Austria, 2011.","short":"K. Schumann, The Role of Chemotactic Gradients in Dendritic Cell Migration, Institute of Science and Technology Austria, 2011.","ieee":"K. Schumann, “The role of chemotactic gradients in dendritic cell migration,” Institute of Science and Technology Austria, 2011.","ama":"Schumann K. The role of chemotactic gradients in dendritic cell migration. 2011.","apa":"Schumann, K. (2011). <i>The role of chemotactic gradients in dendritic cell migration</i>. Institute of Science and Technology Austria.","ista":"Schumann K. 2011. The role of chemotactic gradients in dendritic cell migration. Institute of Science and Technology Austria."},"date_updated":"2023-09-07T11:31:48Z","date_created":"2018-12-11T12:02:24Z","department":[{"_id":"MiSi"}],"publist_id":"3371","alternative_title":["ISTA Thesis"],"has_accepted_license":"1","publication_status":"published","type":"dissertation","publisher":"Institute of Science and Technology Austria","title":"The role of chemotactic gradients in dendritic cell migration","date_published":"2011-03-01T00:00:00Z","day":"01"}]