[{"publisher":"National Academy of Sciences","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3024655","open_access":"1"}],"_id":"3368","doi":"10.1073/pnas.1010767108","date_created":"2018-12-11T12:02:56Z","author":[{"full_name":"Krens, Gabriel","id":"2B819732-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4761-5996","first_name":"Gabriel","last_name":"Krens"},{"full_name":"Möllmert, Stephanie","id":"260FD49C-E911-11E9-B5EA-D9538404589B","first_name":"Stephanie","last_name":"Möllmert"},{"first_name":"Carl-Philipp J","last_name":"Heisenberg","full_name":"Heisenberg, Carl-Philipp J","id":"39427864-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0912-4566"}],"intvolume":"       108","type":"journal_article","day":"18","external_id":{"pmid":["21212360"],"isi":["000286310300003"]},"oa_version":"Submitted Version","month":"01","year":"2011","oa":1,"date_published":"2011-01-18T00:00:00Z","volume":108,"publication_status":"published","article_type":"letter_note","abstract":[{"lang":"eng","text":"Tissue surface tension (TST) is an important mechanical property influencing cell sorting and tissue envelopment. The study by Manning et al. (1) reported on a mathematical model describing TST on the basis of the balance between adhesive and tensile properties of the constituent cells. The model predicts that, in high-adhesion cell aggregates, surface cells will be stretched to maintain the same area of cell–cell contact as interior bulk cells, resulting in an elongated and flattened cell shape. The authors (1) observed flat and elongated cells at the surface of high-adhesion zebrafish germ-layer explants, which they argue are undifferentiated stretched germ-layer progenitor cells, and they use this observation as a validation of their model."}],"publist_id":"3244","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"date_updated":"2026-07-28T09:03:18Z","title":"Enveloping cell layer differentiation at the surface of zebrafish germ layer tissue explants","article_processing_charge":"No","issue":"3","corr_author":"1","department":[{"_id":"CaHe"}],"pmid":1,"status":"public","das_tickbox":"1","scopus_import":"1","isi":1,"publication":"PNAS","page":"E9 - E10","citation":{"short":"G. Krens, S. Möllmert, C.-P.J. Heisenberg, PNAS 108 (2011) E9–E10.","chicago":"Krens, Gabriel, Stephanie Möllmert, and Carl-Philipp J Heisenberg. “Enveloping Cell Layer Differentiation at the Surface of Zebrafish Germ Layer Tissue Explants.” <i>PNAS</i>. National Academy of Sciences, 2011. <a href=\"https://doi.org/10.1073/pnas.1010767108\">https://doi.org/10.1073/pnas.1010767108</a>.","mla":"Krens, Gabriel, et al. “Enveloping Cell Layer Differentiation at the Surface of Zebrafish Germ Layer Tissue Explants.” <i>PNAS</i>, vol. 108, no. 3, National Academy of Sciences, 2011, pp. E9–10, doi:<a href=\"https://doi.org/10.1073/pnas.1010767108\">10.1073/pnas.1010767108</a>.","ista":"Krens G, Möllmert S, Heisenberg C-PJ. 2011. Enveloping cell layer differentiation at the surface of zebrafish germ layer tissue explants. PNAS. 108(3), E9–E10.","apa":"Krens, G., Möllmert, S., &#38; Heisenberg, C.-P. J. (2011). Enveloping cell layer differentiation at the surface of zebrafish germ layer tissue explants. <i>PNAS</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.1010767108\">https://doi.org/10.1073/pnas.1010767108</a>","ama":"Krens G, Möllmert S, Heisenberg C-PJ. Enveloping cell layer differentiation at the surface of zebrafish germ layer tissue explants. <i>PNAS</i>. 2011;108(3):E9-E10. doi:<a href=\"https://doi.org/10.1073/pnas.1010767108\">10.1073/pnas.1010767108</a>","ieee":"G. Krens, S. Möllmert, and C.-P. J. Heisenberg, “Enveloping cell layer differentiation at the surface of zebrafish germ layer tissue explants,” <i>PNAS</i>, vol. 108, no. 3. National Academy of Sciences, pp. E9–E10, 2011."}},{"status":"public","scopus_import":"1","isi":1,"publication":"Optics Letters","citation":{"short":"M. Jahnel, M. Behrndt, A. Jannasch, E. Schaeffer, S. Grill, Optics Letters 36 (2011) 1260–1262.","mla":"Jahnel, Marcus, et al. “Measuring the Complete Force Field of an Optical Trap.” <i>Optics Letters</i>, vol. 36, no. 7, Optica Publishing Group, 2011, pp. 1260–62, doi:<a href=\"https://doi.org/10.1364/OL.36.001260\">10.1364/OL.36.001260</a>.","ista":"Jahnel M, Behrndt M, Jannasch A, Schaeffer E, Grill S. 2011. Measuring the complete force field of an optical trap. Optics Letters. 36(7), 1260–1262.","chicago":"Jahnel, Marcus, Martin Behrndt, Anita Jannasch, Erik Schaeffer, and Stephan Grill. “Measuring the Complete Force Field of an Optical Trap.” <i>Optics Letters</i>. Optica Publishing Group, 2011. <a href=\"https://doi.org/10.1364/OL.36.001260\">https://doi.org/10.1364/OL.36.001260</a>.","ieee":"M. Jahnel, M. Behrndt, A. Jannasch, E. Schaeffer, and S. Grill, “Measuring the complete force field of an optical trap,” <i>Optics Letters</i>, vol. 36, no. 7. Optica Publishing Group, pp. 1260–1262, 2011.","apa":"Jahnel, M., Behrndt, M., Jannasch, A., Schaeffer, E., &#38; Grill, S. (2011). Measuring the complete force field of an optical trap. <i>Optics Letters</i>. Optica Publishing Group. <a href=\"https://doi.org/10.1364/OL.36.001260\">https://doi.org/10.1364/OL.36.001260</a>","ama":"Jahnel M, Behrndt M, Jannasch A, Schaeffer E, Grill S. Measuring the complete force field of an optical trap. <i>Optics Letters</i>. 2011;36(7):1260-1262. doi:<a href=\"https://doi.org/10.1364/OL.36.001260\">10.1364/OL.36.001260</a>"},"page":"1260 - 1262","issue":"7","ddc":["570"],"department":[{"_id":"CaHe"}],"date_updated":"2026-07-29T10:07:18Z","title":"Measuring the complete force field of an optical trap","article_processing_charge":"No","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"oa":1,"year":"2011","date_published":"2011-03-30T00:00:00Z","volume":36,"publication_status":"published","abstract":[{"text":"The use of optical traps to measure or apply forces on the molecular level requires a precise knowledge of the trapping force field. Close to the trap center, this field is typically approximated as linear in the displacement of the trapped microsphere. However, applications demanding high forces at low laser intensities can probe the light-microsphere interaction beyond the linear regime. Here, we measured the full nonlinear force and displacement response of an optical trap in two dimensions using a dual-beam optical trap setup with back-focal-plane photodetection. We observed a substantial stiffening of the trap beyond the linear regime that depends on microsphere size, in agreement with Mie theory calculations. Surprisingly, we found that the linear detection range for forces exceeds the one for displacement by far. Our approach allows for a complete calibration of an optical trap.","lang":"eng"}],"publist_id":"3234","related_material":{"record":[{"status":"public","id":"1403","relation":"dissertation_contains"}]},"day":"30","external_id":{"isi":["000289251000080"]},"oa_version":"Published Version","month":"03","doi":"10.1364/OL.36.001260","author":[{"last_name":"Jahnel","first_name":"Marcus","full_name":"Jahnel, Marcus"},{"first_name":"Martin","last_name":"Behrndt","id":"3ECECA3A-F248-11E8-B48F-1D18A9856A87","full_name":"Behrndt, Martin"},{"last_name":"Jannasch","first_name":"Anita","full_name":"Jannasch, Anita"},{"first_name":"Erik","last_name":"Schaeffer","full_name":"Schaeffer, Erik"},{"first_name":"Stephan","last_name":"Grill","full_name":"Grill, Stephan"}],"date_created":"2018-12-11T12:02:58Z","intvolume":"        36","type":"journal_article","publisher":"Optica Publishing Group","main_file_link":[{"url":"https://www.osapublishing.org/ol/abstract.cfm?uri=ol-36-7-1260","open_access":"1"}],"_id":"3373"},{"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","title":"Spatial waves of advance with bistable dynamics: Cytoplasmic and genetic analogues of Allee effects","date_updated":"2026-08-04T09:17:38Z","publication_identifier":{"eissn":["1537-5323"],"issn":["0003-0147"]},"article_processing_charge":"No","ddc":["570"],"issue":"3","department":[{"_id":"NiBa"}],"status":"public","pubrep_id":"554","citation":{"short":"N.H. Barton, M. Turelli, American Naturalist 178 (2011) E48–E75.","chicago":"Barton, Nicholas H, and Michael Turelli. “Spatial Waves of Advance with Bistable Dynamics: Cytoplasmic and Genetic Analogues of Allee Effects.” <i>American Naturalist</i>. University of Chicago Press, 2011. <a href=\"https://doi.org/10.1086/661246\">https://doi.org/10.1086/661246</a>.","mla":"Barton, Nicholas H., and Michael Turelli. “Spatial Waves of Advance with Bistable Dynamics: Cytoplasmic and Genetic Analogues of Allee Effects.” <i>American Naturalist</i>, vol. 178, no. 3, University of Chicago Press, 2011, pp. E48–75, doi:<a href=\"https://doi.org/10.1086/661246\">10.1086/661246</a>.","ista":"Barton NH, Turelli M. 2011. Spatial waves of advance with bistable dynamics: Cytoplasmic and genetic analogues of Allee effects. American Naturalist. 178(3), E48–E75.","ama":"Barton NH, Turelli M. Spatial waves of advance with bistable dynamics: Cytoplasmic and genetic analogues of Allee effects. <i>American Naturalist</i>. 2011;178(3):E48-E75. doi:<a href=\"https://doi.org/10.1086/661246\">10.1086/661246</a>","apa":"Barton, N. H., &#38; Turelli, M. (2011). Spatial waves of advance with bistable dynamics: Cytoplasmic and genetic analogues of Allee effects. <i>American Naturalist</i>. University of Chicago Press. <a href=\"https://doi.org/10.1086/661246\">https://doi.org/10.1086/661246</a>","ieee":"N. H. Barton and M. Turelli, “Spatial waves of advance with bistable dynamics: Cytoplasmic and genetic analogues of Allee effects,” <i>American Naturalist</i>, vol. 178, no. 3. University of Chicago Press, pp. E48–E75, 2011."},"page":"E48 - E75","publication":"American Naturalist","isi":1,"scopus_import":"1","file":[{"date_updated":"2020-07-14T12:46:11Z","creator":"system","file_name":"IST-2016-554-v1+1_BartonTurelli2011_copy.pdf","date_created":"2018-12-12T10:08:31Z","relation":"main_file","checksum":"7fd22a2ef3321a6fca6a439b3be5d8f4","file_id":"4692","content_type":"application/pdf","file_size":629130,"access_level":"open_access"}],"_id":"3393","publisher":"University of Chicago Press","author":[{"first_name":"Nicholas H","last_name":"Barton","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8548-5240"},{"full_name":"Turelli, Michael","first_name":"Michael","last_name":"Turelli"}],"date_created":"2018-12-11T12:03:05Z","doi":"10.1086/661246","intvolume":"       178","type":"journal_article","oa_version":"Submitted Version","external_id":{"isi":["000294256800001"]},"day":"01","has_accepted_license":"1","month":"09","date_published":"2011-09-01T00:00:00Z","volume":178,"oa":1,"year":"2011","publist_id":"3214","file_date_updated":"2020-07-14T12:46:11Z","abstract":[{"lang":"eng","text":"Unlike unconditionally advantageous “Fisherian” variants that tend to spread throughout a species range once introduced anywhere, “bistable” variants, such as chromosome translocations, have two alternative stable frequencies, absence and (near) fixation. Analogous to populations with Allee effects, bistable variants tend to increase locally only once they become sufficiently common, and their spread depends on their rate of increase averaged over all frequencies. Several proposed manipulations of insect populations, such as using Wolbachia or “engineered underdominance” to suppress vector-borne diseases, produce bistable rather than Fisherian dynamics. We synthesize and extend theoretical analyses concerning three features of their spatial behavior: rate of spread, conditions to initiate spread from a localized introduction, and wave stopping caused by variation in population densities or dispersal rates. Unlike Fisherian variants, bistable variants tend to spread spatially only for particular parameter combinations and initial conditions. Wave initiation requires introduction over an extended region, while subsequent spatial spread is slower than for Fisherian waves and can easily be halted by local spatial inhomogeneities. We present several new results, including robust sufficient conditions to initiate (and stop) spread, using a one-parameter cubic approximation applicable to several models. The results have both basic and applied implications."}],"publication_status":"published","article_type":"original"},{"intvolume":"         8","type":"journal_article","doi":"10.1098/rsif.2010.0438","project":[{"grant_number":"250152","_id":"25B07788-B435-11E9-9278-68D0E5697425","name":"Limits to selection in biology and in evolutionary computation","call_identifier":"FP7"}],"author":[{"first_name":"Harold","last_name":"de Vladar","full_name":"de Vladar, Harold","id":"2A181218-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5985-7653"},{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","first_name":"Nicholas H","last_name":"Barton"}],"date_created":"2018-12-11T12:02:58Z","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3061091/"}],"publisher":"Royal Society","_id":"3375","abstract":[{"text":"By exploiting an analogy between population genetics and statistical mechanics, we study the evolution of a polygenic trait under stabilizing selection, mutation and genetic drift. This requires us to track only four macroscopic variables, instead of the distribution of all the allele frequencies that influence the trait. These macroscopic variables are the expectations of: the trait mean and its square, the genetic variance, and of a measure of heterozygosity, and are derived from a generating function that is in turn derived by maximizing an entropy measure. These four macroscopics are enough to accurately describe the dynamics of the trait mean and of its genetic variance (and in principle of any other quantity). Unlike previous approaches that were based on an infinite series of moments or cumulants, which had to be truncated arbitrarily, our calculations provide a well-defined approximation procedure. We apply the framework to abrupt and gradual changes in the optimum, as well as to changes in the strength of stabilizing selection. Our approximations are surprisingly accurate, even for systems with as few as five loci. We find that when the effects of drift are included, the expected genetic variance is hardly altered by directional selection, even though it fluctuates in any particular instance. We also find hysteresis, showing that even after averaging over the microscopic variables, the macroscopic trajectories retain a memory of the underlying genetic states.","lang":"eng"}],"article_type":"original","publication_status":"published","publist_id":"3232","volume":8,"date_published":"2011-05-01T00:00:00Z","year":"2011","oa":1,"month":"05","day":"01","oa_version":"Submitted Version","ec_funded":1,"external_id":{"isi":["000289671700011"],"pmid":["21084341"]},"article_processing_charge":"No","date_updated":"2026-08-12T14:07:44Z","title":"The statistical mechanics of a polygenic character under stabilizing selection mutation and drift","quality_controlled":"1","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"scopus_import":"1","citation":{"ieee":"H. de Vladar and N. H. Barton, “The statistical mechanics of a polygenic character under stabilizing selection mutation and drift,” <i>Journal of the Royal Society Interface</i>, vol. 8, no. 58. Royal Society, pp. 720–739, 2011.","ama":"de Vladar H, Barton NH. The statistical mechanics of a polygenic character under stabilizing selection mutation and drift. <i>Journal of the Royal Society Interface</i>. 2011;8(58):720-739. doi:<a href=\"https://doi.org/10.1098/rsif.2010.0438\">10.1098/rsif.2010.0438</a>","apa":"de Vladar, H., &#38; Barton, N. H. (2011). The statistical mechanics of a polygenic character under stabilizing selection mutation and drift. <i>Journal of the Royal Society Interface</i>. Royal Society. <a href=\"https://doi.org/10.1098/rsif.2010.0438\">https://doi.org/10.1098/rsif.2010.0438</a>","mla":"de Vladar, Harold, and Nicholas H. Barton. “The Statistical Mechanics of a Polygenic Character under Stabilizing Selection Mutation and Drift.” <i>Journal of the Royal Society Interface</i>, vol. 8, no. 58, Royal Society, 2011, pp. 720–39, doi:<a href=\"https://doi.org/10.1098/rsif.2010.0438\">10.1098/rsif.2010.0438</a>.","ista":"de Vladar H, Barton NH. 2011. The statistical mechanics of a polygenic character under stabilizing selection mutation and drift. Journal of the Royal Society Interface. 8(58), 720–739.","chicago":"Vladar, Harold de, and Nicholas H Barton. “The Statistical Mechanics of a Polygenic Character under Stabilizing Selection Mutation and Drift.” <i>Journal of the Royal Society Interface</i>. Royal Society, 2011. <a href=\"https://doi.org/10.1098/rsif.2010.0438\">https://doi.org/10.1098/rsif.2010.0438</a>.","short":"H. de Vladar, N.H. Barton, Journal of the Royal Society Interface 8 (2011) 720–739."},"page":"720 - 739","publication":"Journal of the Royal Society Interface","status":"public","pmid":1,"department":[{"_id":"NiBa"}],"corr_author":"1","issue":"58"},{"main_file_link":[{"open_access":"1","url":"https://infoscience.epfl.ch/record/186096"}],"publisher":"Springer Nature","_id":"10908","doi":"10.1007/978-3-642-17511-4_7","date_created":"2022-03-21T08:14:35Z","author":[{"last_name":"Blanc","first_name":"Régis","full_name":"Blanc, Régis"},{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Hottelier, Thibaud","first_name":"Thibaud","last_name":"Hottelier"},{"last_name":"Kovács","first_name":"Laura","full_name":"Kovács, Laura"}],"editor":[{"full_name":"Clarke, Edmund M","last_name":"Clarke","first_name":"Edmund M"},{"first_name":"Andrei","last_name":"Voronkov","full_name":"Voronkov, Andrei"}],"type":"conference","intvolume":"      6355","day":"01","oa_version":"Submitted Version","place":"Berlin, Heidelberg","external_id":{"isi":["000309668000007"]},"series_title":"LNCS","month":"05","date_published":"2010-05-01T00:00:00Z","volume":6355,"oa":1,"year":"2010","abstract":[{"lang":"eng","text":"We present ABC, a software tool for automatically computing symbolic upper bounds on the number of iterations of nested program loops. The system combines static analysis of programs with symbolic summation techniques to derive loop invariant relations between program variables. Iteration bounds are obtained from the inferred invariants, by replacing variables with bounds on their greatest values. We have successfully applied ABC to a large number of examples. The derived symbolic bounds express non-trivial polynomial relations over loop variables. We also report on results to automatically infer symbolic expressions over harmonic numbers as upper bounds on loop iteration counts."}],"publication_status":"published","quality_controlled":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"conference":{"start_date":"2010-04-25","name":"LPAR: Logic for Programming, Artificial Intelligence and Reasoning","location":"Dakar, Senegal","end_date":"2010-05-01"},"date_updated":"2025-09-30T09:51:13Z","acknowledgement":"This work was supported in part by the Swiss NSF. The fourth author is supported by an FWF Hertha Firnberg Research grant (T425-N23).","publication_identifier":{"eisbn":["9783642175114"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783642175107"]},"title":"ABC: Algebraic Bound Computation for loops","article_processing_charge":"No","corr_author":"1","department":[{"_id":"ToHe"}],"status":"public","isi":1,"scopus_import":"1","page":"103-118","citation":{"short":"R. Blanc, T.A. Henzinger, T. Hottelier, L. Kovács, in:, E.M. Clarke, A. Voronkov (Eds.), Logic for Programming, Artificial Intelligence, and Reasoning, Springer Nature, Berlin, Heidelberg, 2010, pp. 103–118.","ista":"Blanc R, Henzinger TA, Hottelier T, Kovács L. 2010. ABC: Algebraic Bound Computation for loops. Logic for Programming, Artificial Intelligence, and Reasoning. LPAR: Logic for Programming, Artificial Intelligence and ReasoningLNCS vol. 6355, 103–118.","mla":"Blanc, Régis, et al. “ABC: Algebraic Bound Computation for Loops.” <i>Logic for Programming, Artificial Intelligence, and Reasoning</i>, edited by Edmund M Clarke and Andrei Voronkov, vol. 6355, Springer Nature, 2010, pp. 103–18, doi:<a href=\"https://doi.org/10.1007/978-3-642-17511-4_7\">10.1007/978-3-642-17511-4_7</a>.","chicago":"Blanc, Régis, Thomas A Henzinger, Thibaud Hottelier, and Laura Kovács. “ABC: Algebraic Bound Computation for Loops.” In <i>Logic for Programming, Artificial Intelligence, and Reasoning</i>, edited by Edmund M Clarke and Andrei Voronkov, 6355:103–18. LNCS. Berlin, Heidelberg: Springer Nature, 2010. <a href=\"https://doi.org/10.1007/978-3-642-17511-4_7\">https://doi.org/10.1007/978-3-642-17511-4_7</a>.","ieee":"R. Blanc, T. A. Henzinger, T. Hottelier, and L. Kovács, “ABC: Algebraic Bound Computation for loops,” in <i>Logic for Programming, Artificial Intelligence, and Reasoning</i>, Dakar, Senegal, 2010, vol. 6355, pp. 103–118.","apa":"Blanc, R., Henzinger, T. A., Hottelier, T., &#38; Kovács, L. (2010). ABC: Algebraic Bound Computation for loops. In E. M. Clarke &#38; A. Voronkov (Eds.), <i>Logic for Programming, Artificial Intelligence, and Reasoning</i> (Vol. 6355, pp. 103–118). Berlin, Heidelberg: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-17511-4_7\">https://doi.org/10.1007/978-3-642-17511-4_7</a>","ama":"Blanc R, Henzinger TA, Hottelier T, Kovács L. ABC: Algebraic Bound Computation for loops. In: Clarke EM, Voronkov A, eds. <i>Logic for Programming, Artificial Intelligence, and Reasoning</i>. Vol 6355. LNCS. Berlin, Heidelberg: Springer Nature; 2010:103-118. doi:<a href=\"https://doi.org/10.1007/978-3-642-17511-4_7\">10.1007/978-3-642-17511-4_7</a>"},"publication":"Logic for Programming, Artificial Intelligence, and Reasoning"},{"_id":"10909","publisher":"Society for Industrial and Applied Mathematics","conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2010-01-19","location":"Austin, TX, United States","start_date":"2010-01-17"},"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","article_processing_charge":"No","type":"conference","author":[{"first_name":"Chao","last_name":"Chen","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","full_name":"Chen, Chao"},{"last_name":"Freedman","first_name":"Daniel","full_name":"Freedman, Daniel"}],"title":"Hardness results for homology localization","date_created":"2022-03-21T08:24:07Z","date_updated":"2025-09-30T09:22:32Z","acknowledgement":"Partially supported by the Austrian Science Fund under grantFSP-S9103-N04 and P20134-N13.","publication_identifier":{"eisbn":["9781611973075"]},"doi":"10.1137/1.9781611973075.129","department":[{"_id":"HeEd"}],"month":"02","oa_version":"None","day":"01","corr_author":"1","citation":{"ama":"Chen C, Freedman D. Hardness results for homology localization. In: <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2010:1594-1604. doi:<a href=\"https://doi.org/10.1137/1.9781611973075.129\">10.1137/1.9781611973075.129</a>","apa":"Chen, C., &#38; Freedman, D. (2010). Hardness results for homology localization. In <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1594–1604). Austin, TX, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611973075.129\">https://doi.org/10.1137/1.9781611973075.129</a>","ieee":"C. Chen and D. Freedman, “Hardness results for homology localization,” in <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Austin, TX, United States, 2010, pp. 1594–1604.","chicago":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” In <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1594–1604. Society for Industrial and Applied Mathematics, 2010. <a href=\"https://doi.org/10.1137/1.9781611973075.129\">https://doi.org/10.1137/1.9781611973075.129</a>.","ista":"Chen C, Freedman D. 2010. Hardness results for homology localization. Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1594–1604.","mla":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2010, pp. 1594–604, doi:<a href=\"https://doi.org/10.1137/1.9781611973075.129\">10.1137/1.9781611973075.129</a>.","short":"C. Chen, D. Freedman, in:, Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2010, pp. 1594–1604."},"related_material":{"record":[{"relation":"later_version","status":"public","id":"3267"}]},"page":"1594-1604","publication":"Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms","abstract":[{"lang":"eng","text":"We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We focus on the volume measure, that is, the 1-norm of a cycle. Two main results are presented. First, we prove 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). A side effect is 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. We also discuss other geometric measures (diameter and radius) and show their disadvantages in homology localization. Our work is restricted to homology over the ℤ2 field."}],"publication_status":"published","scopus_import":"1","status":"public","date_published":"2010-02-01T00:00:00Z","year":"2010"},{"month":"12","has_accepted_license":"1","external_id":{"isi":["000286183400001"]},"oa_version":"Published Version","day":"06","file_date_updated":"2020-07-14T12:45:40Z","publist_id":"4517","publication_status":"published","abstract":[{"text":"Background: The availability of many gene alignments with overlapping taxon sets raises the question of which strategy is the best to infer species phylogenies from multiple gene information. Methods and programs abound that use the gene alignment in different ways to reconstruct the species tree. In particular, different methods combine the original data at different points along the way from the underlying sequences to the final tree. Accordingly, they are classified into superalignment, supertree and medium-level approaches. Here, we present a simulation study to compare different methods from each of these three approaches.\r\n\r\nResults: We observe that superalignment methods usually outperform the other approaches over a wide range of parameters including sparse data and gene-specific evolutionary parameters. In the presence of high incongruency among gene trees, however, other combination methods show better performance than the superalignment approach. Surprisingly, some supertree and medium-level methods exhibit, on average, worse results than a single gene phylogeny with complete taxon information.\r\n\r\nConclusions: For some methods, using the reconstructed gene tree as an estimation of the species tree is superior to the combination of incomplete information. Superalignment usually performs best since it is less susceptible to stochastic error. Supertree methods can outperform superalignment in the presence of gene-tree conflict.","lang":"eng"}],"oa":1,"year":"2010","volume":5,"date_published":"2010-12-06T00:00:00Z","_id":"2409","publisher":"BioMed Central","file":[{"file_id":"4739","checksum":"e2497285388bc4da629bafb46662eb43","relation":"main_file","access_level":"open_access","file_size":723929,"content_type":"application/pdf","file_name":"IST-2018-939-v1+1_2010_Kupczok_Accuracy_of.pdf","date_created":"2018-12-12T10:09:16Z","creator":"system","date_updated":"2020-07-14T12:45:40Z"}],"type":"journal_article","intvolume":"         5","author":[{"full_name":"Kupczok, Anne","id":"2BB22BC2-F248-11E8-B48F-1D18A9856A87","last_name":"Kupczok","first_name":"Anne"},{"full_name":"Schmidt, Heiko","first_name":"Heiko","last_name":"Schmidt"},{"last_name":"Von Haeseler","first_name":"Arndt","full_name":"Von Haeseler, Arndt"}],"date_created":"2018-12-11T11:57:30Z","doi":"10.1186/1748-7188-5-37","department":[{"_id":"JoBo"}],"issue":"1","ddc":["576"],"publication":"Algorithms for Molecular Biology","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"citation":{"ista":"Kupczok A, Schmidt H, Von Haeseler A. 2010. Accuracy of phylogeny reconstruction methods combining overlapping gene data sets. Algorithms for Molecular Biology. 5(1), 37.","mla":"Kupczok, Anne, et al. “Accuracy of Phylogeny Reconstruction Methods Combining Overlapping Gene Data Sets.” <i>Algorithms for Molecular Biology</i>, vol. 5, no. 1, 37, BioMed Central, 2010, doi:<a href=\"https://doi.org/10.1186/1748-7188-5-37\">10.1186/1748-7188-5-37</a>.","chicago":"Kupczok, Anne, Heiko Schmidt, and Arndt Von Haeseler. “Accuracy of Phylogeny Reconstruction Methods Combining Overlapping Gene Data Sets.” <i>Algorithms for Molecular Biology</i>. BioMed Central, 2010. <a href=\"https://doi.org/10.1186/1748-7188-5-37\">https://doi.org/10.1186/1748-7188-5-37</a>.","short":"A. Kupczok, H. Schmidt, A. Von Haeseler, Algorithms for Molecular Biology 5 (2010).","ieee":"A. Kupczok, H. Schmidt, and A. Von Haeseler, “Accuracy of phylogeny reconstruction methods combining overlapping gene data sets,” <i>Algorithms for Molecular Biology</i>, vol. 5, no. 1. BioMed Central, 2010.","ama":"Kupczok A, Schmidt H, Von Haeseler A. Accuracy of phylogeny reconstruction methods combining overlapping gene data sets. <i>Algorithms for Molecular Biology</i>. 2010;5(1). doi:<a href=\"https://doi.org/10.1186/1748-7188-5-37\">10.1186/1748-7188-5-37</a>","apa":"Kupczok, A., Schmidt, H., &#38; Von Haeseler, A. (2010). Accuracy of phylogeny reconstruction methods combining overlapping gene data sets. <i>Algorithms for Molecular Biology</i>. BioMed Central. <a href=\"https://doi.org/10.1186/1748-7188-5-37\">https://doi.org/10.1186/1748-7188-5-37</a>"},"scopus_import":"1","isi":1,"pubrep_id":"939","status":"public","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"quality_controlled":"1","article_processing_charge":"No","article_number":"37","title":"Accuracy of phylogeny reconstruction methods combining overlapping gene data sets","date_updated":"2025-09-30T09:48:29Z","acknowledgement":"Financial support from the Wiener Wissenschafts-, Forschungs- and Technologiefonds (WWTF) is greatly appreciated. A.v.H. acknowledges support from the German Research Foundation (DFG, SPP-1174)."},{"quality_controlled":"1","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","publication_identifier":{"issn":["1477-9129","0950-1991"]},"date_updated":"2023-05-08T10:57:11Z","acknowledgement":"We thank the following for providing mutant lines and reagents: Hong Ma, De Ye, Sacco De Vries, and Rod Scott for providing the pA9::Barnase lines and information on A9 expression patterns. Carla Galinha and Paolo Piazza gave valuable help with in situ hybridisation and qRT-PCR, respectively, and we acknowledge Qing Zhang, Helen Prescott and Matthew Dicks for providing excellent technical assistance. We are indebted to Miltos Tsiantis and Angela Hay for helpful discussion, and the research was funded by Oxford University through a Clarendon Scholarship to X.F., with additional financial support from Magdalen College (Oxford).","title":"Tapetal cell fate, lineage and proliferation in the Arabidopsis anther","pmid":1,"department":[{"_id":"XiFe"}],"issue":"14","scopus_import":"1","publication":"Development","citation":{"short":"X. Feng, H.G. Dickinson, Development 137 (2010) 2409–2416.","ista":"Feng X, Dickinson HG. 2010. Tapetal cell fate, lineage and proliferation in the Arabidopsis anther. Development. 137(14), 2409–2416.","mla":"Feng, Xiaoqi, and Hugh G. Dickinson. “Tapetal Cell Fate, Lineage and Proliferation in the Arabidopsis Anther.” <i>Development</i>, vol. 137, no. 14, The Company of Biologists, 2010, pp. 2409–16, doi:<a href=\"https://doi.org/10.1242/dev.049320\">10.1242/dev.049320</a>.","chicago":"Feng, Xiaoqi, and Hugh G. Dickinson. “Tapetal Cell Fate, Lineage and Proliferation in the Arabidopsis Anther.” <i>Development</i>. The Company of Biologists, 2010. <a href=\"https://doi.org/10.1242/dev.049320\">https://doi.org/10.1242/dev.049320</a>.","ieee":"X. Feng and H. G. Dickinson, “Tapetal cell fate, lineage and proliferation in the Arabidopsis anther,” <i>Development</i>, vol. 137, no. 14. The Company of Biologists, pp. 2409–2416, 2010.","ama":"Feng X, Dickinson HG. Tapetal cell fate, lineage and proliferation in the Arabidopsis anther. <i>Development</i>. 2010;137(14):2409-2416. doi:<a href=\"https://doi.org/10.1242/dev.049320\">10.1242/dev.049320</a>","apa":"Feng, X., &#38; Dickinson, H. G. (2010). Tapetal cell fate, lineage and proliferation in the Arabidopsis anther. <i>Development</i>. The Company of Biologists. <a href=\"https://doi.org/10.1242/dev.049320\">https://doi.org/10.1242/dev.049320</a>"},"page":"2409-2416","keyword":["Developmental Biology","Molecular Biology","Anther Tapetum","Arabidopsis","Cell Fate Establishment","EMS1","Reproductive Cell Lineage"],"status":"public","publisher":"The Company of Biologists","_id":"12199","intvolume":"       137","type":"journal_article","doi":"10.1242/dev.049320","author":[{"last_name":"Feng","first_name":"Xiaoqi","orcid":"0000-0002-4008-1234","id":"e0164712-22ee-11ed-b12a-d80fcdf35958","full_name":"Feng, Xiaoqi"},{"first_name":"Hugh G.","last_name":"Dickinson","full_name":"Dickinson, Hugh G."}],"date_created":"2023-01-16T09:21:54Z","extern":"1","month":"07","day":"15","external_id":{"pmid":["20570940"]},"oa_version":"None","article_type":"original","publication_status":"published","abstract":[{"text":"The four microsporangia of the flowering plant anther develop from archesporial cells in the L2 of the primordium. Within each microsporangium, developing microsporocytes are surrounded by concentric monolayers of tapetal, middle layer and endothecial cells. How this intricate array of tissues, each containing relatively few cells, is established in an organ possessing no formal meristems is poorly understood. We describe here the pivotal role of the LRR receptor kinase EXCESS MICROSPOROCYTES 1 (EMS1) in forming the monolayer of tapetal nurse cells in Arabidopsis. Unusually for plants, tapetal cells are specified very early in development, and are subsequently stimulated to proliferate by a receptor-like kinase (RLK) complex that includes EMS1. Mutations in members of this EMS1 signalling complex and its putative ligand result in male-sterile plants in which tapetal initials fail to proliferate. Surprisingly, these cells continue to develop, isolated at the locular periphery. Mutant and wild-type microsporangia expand at similar rates and the ‘tapetal’ space at the periphery of mutant locules becomes occupied by microsporocytes. However, induction of late expression of EMS1 in the few tapetal initials in ems1 plants results in their proliferation to generate a functional tapetum, and this proliferation suppresses microsporocyte number. Our experiments also show that integrity of the tapetal monolayer is crucial for the maintenance of the polarity of divisions within it. This unexpected autonomy of the tapetal ‘lineage’ is discussed in the context of tissue development in complex plant organs, where constancy in size, shape and cell number is crucial.","lang":"eng"}],"year":"2010","volume":137,"date_published":"2010-07-15T00:00:00Z"},{"intvolume":"        38","type":"journal_article","doi":"10.1042/bst0380571","author":[{"last_name":"Feng","first_name":"Xiaoqi","orcid":"0000-0002-4008-1234","full_name":"Feng, Xiaoqi","id":"e0164712-22ee-11ed-b12a-d80fcdf35958"},{"full_name":"Dickinson, Hugh G.","last_name":"Dickinson","first_name":"Hugh G."}],"date_created":"2023-01-16T09:22:18Z","publisher":"Portland Press Ltd.","_id":"12200","abstract":[{"lang":"eng","text":"Key steps in the evolution of the angiosperm anther include the patterning of the concentrically organized microsporangium and the incorporation of four such microsporangia into a leaf-like structure. Mutant studies in the model plant Arabidopsis thaliana are leading to an increasingly accurate picture of (i) the cell lineages culminating in the different cell types present in the microsporangium (the microsporocytes, the tapetum, and the middle and endothecial layers), and (ii) some of the genes responsible for specifying their fates. However, the processes that confer polarity on the developing anther and position the microsporangia within it remain unclear. Certainly, data from a range of experimental strategies suggest that hormones play a central role in establishing polarity and the patterning of the anther initial, and may be responsible for locating the microsporangia. But the fact that microsporangia were originally positioned externally suggests that their development is likely to be autonomous, perhaps with the reproductive cells generating signals controlling the growth and division of the investing anther epidermis. These possibilities are discussed in the context of the expression of genes which initiate and maintain male and female reproductive development, and in the perspective of our current views of anther evolution."}],"article_type":"original","publication_status":"published","date_published":"2010-03-22T00:00:00Z","volume":38,"year":"2010","month":"03","extern":"1","day":"22","oa_version":"None","external_id":{"pmid":["20298223"]},"article_processing_charge":"No","date_updated":"2023-05-08T10:57:59Z","publication_identifier":{"issn":["0300-5127","1470-8752"]},"title":"Cell–cell interactions during patterning of the <i>Arabidopsis</i> anther","quality_controlled":"1","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","page":"571-576","citation":{"short":"X. Feng, H.G. Dickinson, Biochemical Society Transactions 38 (2010) 571–576.","mla":"Feng, Xiaoqi, and Hugh G. Dickinson. “Cell–Cell Interactions during Patterning of the <i>Arabidopsis</i> Anther.” <i>Biochemical Society Transactions</i>, vol. 38, no. 2, Portland Press Ltd., 2010, pp. 571–76, doi:<a href=\"https://doi.org/10.1042/bst0380571\">10.1042/bst0380571</a>.","ista":"Feng X, Dickinson HG. 2010. Cell–cell interactions during patterning of the <i>Arabidopsis</i> anther. Biochemical Society Transactions. 38(2), 571–576.","chicago":"Feng, Xiaoqi, and Hugh G. Dickinson. “Cell–Cell Interactions during Patterning of the <i>Arabidopsis</i> Anther.” <i>Biochemical Society Transactions</i>. Portland Press Ltd., 2010. <a href=\"https://doi.org/10.1042/bst0380571\">https://doi.org/10.1042/bst0380571</a>.","ieee":"X. Feng and H. G. Dickinson, “Cell–cell interactions during patterning of the <i>Arabidopsis</i> anther,” <i>Biochemical Society Transactions</i>, vol. 38, no. 2. Portland Press Ltd., pp. 571–576, 2010.","ama":"Feng X, Dickinson HG. Cell–cell interactions during patterning of the <i>Arabidopsis</i> anther. <i>Biochemical Society Transactions</i>. 2010;38(2):571-576. doi:<a href=\"https://doi.org/10.1042/bst0380571\">10.1042/bst0380571</a>","apa":"Feng, X., &#38; Dickinson, H. G. (2010). Cell–cell interactions during patterning of the <i>Arabidopsis</i> anther. <i>Biochemical Society Transactions</i>. Portland Press Ltd. <a href=\"https://doi.org/10.1042/bst0380571\">https://doi.org/10.1042/bst0380571</a>"},"publication":"Biochemical Society Transactions","status":"public","keyword":["Biochemistry","Anther Development","Arabidopsis","Cell Fate","Microsporangium","Polarity","Receptor Kinase"],"department":[{"_id":"XiFe"}],"pmid":1,"issue":"2"},{"title":"Forward analysis of depth-bounded processes","date_updated":"2026-04-09T14:35:23Z","language":[{"iso":"eng"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","conference":{"name":"FoSSaCS: Foundations of Software Science and Computation Structures","location":"Paphos, Cyprus","end_date":"2010-03-28","start_date":"2010-03-20"},"quality_controlled":"1","citation":{"short":"T. Wies, D. Zufferey, T.A. Henzinger, in:, L. Ong (Ed.), Springer, 2010, pp. 94–108.","chicago":"Wies, Thomas, Damien Zufferey, and Thomas A Henzinger. “Forward Analysis of Depth-Bounded Processes.” edited by Luke Ong, 6014:94–108. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-12032-9_8\">https://doi.org/10.1007/978-3-642-12032-9_8</a>.","mla":"Wies, Thomas, et al. <i>Forward Analysis of Depth-Bounded Processes</i>. Edited by Luke Ong, vol. 6014, Springer, 2010, pp. 94–108, doi:<a href=\"https://doi.org/10.1007/978-3-642-12032-9_8\">10.1007/978-3-642-12032-9_8</a>.","ista":"Wies T, Zufferey D, Henzinger TA. 2010. Forward analysis of depth-bounded processes. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 6014, 94–108.","apa":"Wies, T., Zufferey, D., &#38; Henzinger, T. A. (2010). Forward analysis of depth-bounded processes. In L. Ong (Ed.) (Vol. 6014, pp. 94–108). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Paphos, Cyprus: Springer. <a href=\"https://doi.org/10.1007/978-3-642-12032-9_8\">https://doi.org/10.1007/978-3-642-12032-9_8</a>","ama":"Wies T, Zufferey D, Henzinger TA. Forward analysis of depth-bounded processes. In: Ong L, ed. Vol 6014. Springer; 2010:94-108. doi:<a href=\"https://doi.org/10.1007/978-3-642-12032-9_8\">10.1007/978-3-642-12032-9_8</a>","ieee":"T. Wies, D. Zufferey, and T. A. Henzinger, “Forward analysis of depth-bounded processes,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Paphos, Cyprus, 2010, vol. 6014, pp. 94–108."},"page":"94 - 108","scopus_import":1,"pubrep_id":"50","status":"public","department":[{"_id":"ToHe"}],"corr_author":"1","ddc":["004"],"intvolume":"      6014","type":"conference","editor":[{"first_name":"Luke","last_name":"Ong","full_name":"Ong, Luke"}],"date_created":"2018-12-11T12:08:27Z","author":[{"id":"447BFB88-F248-11E8-B48F-1D18A9856A87","full_name":"Wies, Thomas","first_name":"Thomas","last_name":"Wies"},{"orcid":"0000-0002-3197-8736","id":"4397AC76-F248-11E8-B48F-1D18A9856A87","full_name":"Zufferey, Damien","last_name":"Zufferey","first_name":"Damien"},{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"doi":"10.1007/978-3-642-12032-9_8","_id":"4361","publisher":"Springer","file":[{"date_updated":"2020-07-14T12:46:27Z","creator":"system","date_created":"2018-12-12T10:08:17Z","file_name":"IST-2012-50-v1+1_Forward_analysis_of_depth-bounded_processes.pdf","checksum":"3e610de84937d821316362658239134a","relation":"main_file","file_id":"4677","content_type":"application/pdf","access_level":"open_access","file_size":240766}],"file_date_updated":"2020-07-14T12:46:27Z","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"1405"}]},"publist_id":"1099","publication_status":"published","abstract":[{"text":"Depth-bounded processes form the most expressive known fragment of the π-calculus for which interesting verification problems are still decidable. In this paper we develop an adequate domain of limits for the well-structured transition systems that are induced by depth-bounded processes. An immediate consequence of our result is that there exists a forward algorithm that decides the covering problem for this class. Unlike backward algorithms, the forward algorithm terminates even if the depth of the process is not known a priori. More importantly, our result suggests a whole spectrum of forward algorithms that enable the effective verification of a large class of mobile systems.","lang":"eng"}],"alternative_title":["LNCS"],"oa":1,"year":"2010","date_published":"2010-03-01T00:00:00Z","volume":6014,"month":"03","has_accepted_license":"1","oa_version":"Submitted Version","day":"01"},{"volume":6418,"status":"public","date_published":"2010-01-01T00:00:00Z","year":"2010","alternative_title":["LNCS"],"abstract":[{"text":"Software transactional memories (STMs) promise simple and efficient concurrent programming. Several correctness properties have been proposed for STMs. Based on a bounded conflict graph algorithm for verifying correctness of STMs, we develop TRACER, a tool for runtime verification of STM implementations. The novelty of TRACER lies in the way it combines coarse and precise runtime analyses to guarantee sound and complete verification in an efficient manner. We implement TRACER in the TL2 STM implementation. We evaluate the performance of TRACER on STAMP benchmarks. While a precise runtime verification technique based on conflict graphs results in an average slowdown of 60x, the two-level approach of TRACER performs complete verification with an average slowdown of around 25x across different benchmarks.","lang":"eng"}],"publication_status":"published","scopus_import":1,"publist_id":"1096","citation":{"apa":"Singh, V. (2010). Runtime verification for software transactional memories. In O. Sokolsky, G. Rosu, N. Tilmann, H. Barringer, Y. Falcone, B. Finkbeiner, … G. Pace (Eds.) (Vol. 6418, pp. 421–435). Presented at the RV: International Conference on Runtime Verification, St. Julians, Malta: Springer. <a href=\"https://doi.org/10.1007/978-3-642-16612-9_32\">https://doi.org/10.1007/978-3-642-16612-9_32</a>","ama":"Singh V. Runtime verification for software transactional memories. In: Sokolsky O, Rosu G, Tilmann N, et al., eds. Vol 6418. Springer; 2010:421-435. doi:<a href=\"https://doi.org/10.1007/978-3-642-16612-9_32\">10.1007/978-3-642-16612-9_32</a>","ieee":"V. Singh, “Runtime verification for software transactional memories,” presented at the RV: International Conference on Runtime Verification, St. Julians, Malta, 2010, vol. 6418, pp. 421–435.","chicago":"Singh, Vasu. “Runtime Verification for Software Transactional Memories.” edited by Oleg Sokolsky, Grigore Rosu, Nikolai Tilmann, Howard Barringer, Ylies Falcone, Bernd Finkbeiner, Klaus Havelund, Insup Lee, and Gordon Pace, 6418:421–35. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-16612-9_32\">https://doi.org/10.1007/978-3-642-16612-9_32</a>.","ista":"Singh V. 2010. Runtime verification for software transactional memories. RV: International Conference on Runtime Verification, LNCS, vol. 6418, 421–435.","mla":"Singh, Vasu. <i>Runtime Verification for Software Transactional Memories</i>. Edited by Oleg Sokolsky et al., vol. 6418, Springer, 2010, pp. 421–35, doi:<a href=\"https://doi.org/10.1007/978-3-642-16612-9_32\">10.1007/978-3-642-16612-9_32</a>.","short":"V. Singh, in:, O. Sokolsky, G. Rosu, N. Tilmann, H. Barringer, Y. Falcone, B. Finkbeiner, K. Havelund, I. Lee, G. Pace (Eds.), Springer, 2010, pp. 421–435."},"page":"421 - 435","corr_author":"1","day":"01","oa_version":"None","month":"01","department":[{"_id":"ToHe"}],"date_updated":"2024-10-09T20:54:01Z","doi":"10.1007/978-3-642-16612-9_32","editor":[{"full_name":"Sokolsky, Oleg","last_name":"Sokolsky","first_name":"Oleg"},{"full_name":"Rosu, Grigore","first_name":"Grigore","last_name":"Rosu"},{"full_name":"Tilmann, Nikolai","first_name":"Nikolai","last_name":"Tilmann"},{"last_name":"Barringer","first_name":"Howard","full_name":"Barringer, Howard"},{"full_name":"Falcone, Ylies","first_name":"Ylies","last_name":"Falcone"},{"full_name":"Finkbeiner, Bernd","first_name":"Bernd","last_name":"Finkbeiner"},{"last_name":"Havelund","first_name":"Klaus","full_name":"Havelund, Klaus"},{"full_name":"Lee, Insup","last_name":"Lee","first_name":"Insup"},{"first_name":"Gordon","last_name":"Pace","full_name":"Pace, Gordon"}],"author":[{"id":"4DAE2708-F248-11E8-B48F-1D18A9856A87","full_name":"Singh, Vasu","last_name":"Singh","first_name":"Vasu"}],"title":"Runtime verification for software transactional memories","date_created":"2018-12-11T12:08:28Z","intvolume":"      6418","type":"conference","quality_controlled":"1","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2010-11-01","name":"RV: International Conference on Runtime Verification","end_date":"2010-11-04","location":"St. Julians, Malta"},"language":[{"iso":"eng"}],"publisher":"Springer","_id":"4362"},{"quality_controlled":"1","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"conference":{"start_date":"2010-09-08","end_date":"2010-09-10","location":"Klosterneuburg, Austria","name":"FORMATS: Formal Modeling and Analysis of Timed Systems"},"date_updated":"2024-10-09T20:54:01Z","title":"From MTL to deterministic timed automata","department":[{"_id":"ToHe"}],"corr_author":"1","ddc":["004"],"scopus_import":1,"citation":{"ieee":"D. Nickovic and N. Piterman, “From MTL to deterministic timed automata,” presented at the FORMATS: Formal Modeling and Analysis of Timed Systems, Klosterneuburg, Austria, 2010, vol. 6246, pp. 152–167.","ama":"Nickovic D, Piterman N. From MTL to deterministic timed automata. In: Henzinger TA, Chatterjee K, eds. Vol 6246. Springer; 2010:152-167. doi:<a href=\"https://doi.org/10.1007/978-3-642-15297-9_13\">10.1007/978-3-642-15297-9_13</a>","apa":"Nickovic, D., &#38; Piterman, N. (2010). From MTL to deterministic timed automata. In T. A. Henzinger &#38; K. Chatterjee (Eds.) (Vol. 6246, pp. 152–167). Presented at the FORMATS: Formal Modeling and Analysis of Timed Systems, Klosterneuburg, Austria: Springer. <a href=\"https://doi.org/10.1007/978-3-642-15297-9_13\">https://doi.org/10.1007/978-3-642-15297-9_13</a>","mla":"Nickovic, Dejan, and Nir Piterman. <i>From MTL to Deterministic Timed Automata</i>. Edited by Thomas A. Henzinger and Krishnendu Chatterjee, vol. 6246, Springer, 2010, pp. 152–67, doi:<a href=\"https://doi.org/10.1007/978-3-642-15297-9_13\">10.1007/978-3-642-15297-9_13</a>.","ista":"Nickovic D, Piterman N. 2010. From MTL to deterministic timed automata. FORMATS: Formal Modeling and Analysis of Timed Systems, LNCS, vol. 6246, 152–167.","chicago":"Nickovic, Dejan, and Nir Piterman. “From MTL to Deterministic Timed Automata.” edited by Thomas A. Henzinger and Krishnendu Chatterjee, 6246:152–67. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-15297-9_13\">https://doi.org/10.1007/978-3-642-15297-9_13</a>.","short":"D. Nickovic, N. Piterman, in:, T.A. Henzinger, K. Chatterjee (Eds.), Springer, 2010, pp. 152–167."},"page":"152 - 167","pubrep_id":"49","status":"public","publisher":"Springer","_id":"4369","file":[{"date_updated":"2020-07-14T12:46:27Z","creator":"system","date_created":"2018-12-12T10:13:43Z","file_name":"IST-2012-49-v1+1_From_MTL_to_deterministic_timed_automata.pdf","checksum":"b0ca5f5fbe8a3d20ccbc6f51a344a459","relation":"main_file","file_id":"5028","content_type":"application/pdf","access_level":"open_access","file_size":249789}],"type":"conference","intvolume":"      6246","project":[{"grant_number":"215543","call_identifier":"FP7","name":"COMponent-Based Embedded Systems design Techniques","_id":"25EFB36C-B435-11E9-9278-68D0E5697425"},{"grant_number":"214373","_id":"25F1337C-B435-11E9-9278-68D0E5697425","name":"Design for Embedded Systems","call_identifier":"FP7"}],"doi":"10.1007/978-3-642-15297-9_13","date_created":"2018-12-11T12:08:30Z","author":[{"id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","full_name":"Nickovic, Dejan","last_name":"Nickovic","first_name":"Dejan"},{"full_name":"Piterman, Nir","last_name":"Piterman","first_name":"Nir"}],"editor":[{"last_name":"Henzinger","first_name":"Thomas A.","full_name":"Henzinger, Thomas A."},{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"}],"has_accepted_license":"1","month":"09","day":"08","oa_version":"Submitted Version","ec_funded":1,"abstract":[{"lang":"eng","text":"In this paper we propose a novel technique for constructing timed automata from properties expressed in the logic mtl, under bounded-variability assumptions. We handle full mtl and include all future operators. Our construction is based on separation of the continuous time monitoring of the input sequence and discrete predictions regarding the future. The separation of the continuous from the discrete allows us to determinize our automata in an exponential construction that does not increase the number of clocks. This leads to a doubly exponential construction from mtl to deterministic timed automata, compared with triply exponential using existing approaches. We offer an alternative to the existing approach to linear real-time model checking, which has never been implemented. It further offers a unified framework for model checking, runtime monitoring, and synthesis, in an approach that can reuse tools, implementations, and insights from the discrete setting."}],"publication_status":"published","publist_id":"1090","file_date_updated":"2020-07-14T12:46:27Z","date_published":"2010-09-08T00:00:00Z","volume":6246,"year":"2010","oa":1,"alternative_title":["LNCS"]},{"abstract":[{"lang":"eng","text":"Techniques such as verification condition generation, predicate abstraction, and expressive type systems reduce software verification to proving formulas in expressive logics. Programs and their specifications often make use of data structures such as sets, multisets, algebraic data types, or graphs. Consequently, formulas generated from verification also involve such data structures. To automate the proofs of such formulas we propose a logic (a “calculus”) of such data structures. We build the calculus by starting from decidable logics of individual data structures, and connecting them through functions and sets, in ways that go beyond the frameworks such as Nelson-Oppen. The result are new decidable logics that can simultaneously specify properties of different kinds of data structures and overcome the limitations of the individual logics. Several of our decidable logics include abstraction functions that map a data structure into its more abstract view (a tree into a multiset, a multiset into a set), into a numerical quantity (the size or the height), or into the truth value of a candidate data structure invariant (sortedness, or the heap property). For algebraic data types, we identify an asymptotic many-to-one condition on the abstraction function that guarantees the existence of a decision procedure. In addition to the combination based on abstraction functions, we can combine multiple data structure theories if they all reduce to the same data structure logic. As an instance of this approach, we describe a decidable logic whose formulas are propositional combinations of formulas in: weak monadic second-order logic of two successors, two-variable logic with counting, multiset algebra with Presburger arithmetic, the Bernays-Schönfinkel-Ramsey class of first-order logic, and the logic of algebraic data types with the set content function. The subformulas in this combination can share common variables that refer to sets of objects along with the common set algebra operations. Such sound and complete combination is possible because the relations on sets definable in the component logics are all expressible in Boolean Algebra with Presburger Arithmetic. Presburger arithmetic and its new extensions play an important role in our decidability results. In several cases, when we combine logics that belong to NP, we can prove the satisfiability for the combined logic is still in NP."}],"publication_status":"published","publist_id":"1081","volume":5944,"date_published":"2010-01-01T00:00:00Z","oa":1,"year":"2010","alternative_title":["LNCS"],"month":"01","day":"01","oa_version":"Submitted Version","type":"conference","intvolume":"      5944","doi":"10.1007/978-3-642-11319-2_6","date_created":"2018-12-11T12:08:33Z","author":[{"first_name":"Viktor","last_name":"Kuncak","full_name":"Kuncak, Viktor"},{"first_name":"Ruzica","last_name":"Piskac","full_name":"Piskac, Ruzica"},{"last_name":"Suter","first_name":"Philippe","full_name":"Suter, Philippe"},{"full_name":"Wies, Thomas","id":"447BFB88-F248-11E8-B48F-1D18A9856A87","last_name":"Wies","first_name":"Thomas"}],"editor":[{"last_name":"Barthe","first_name":"Gilles","full_name":"Barthe, Gilles"},{"full_name":"Hermenegildo, Manuel","last_name":"Hermenegildo","first_name":"Manuel"}],"publisher":"Springer","main_file_link":[{"open_access":"1","url":"https://infoscience.epfl.ch/record/161290/"}],"_id":"4378","scopus_import":1,"citation":{"short":"V. Kuncak, R. Piskac, P. Suter, T. Wies, in:, G. Barthe, M. Hermenegildo (Eds.), Springer, 2010, pp. 26–44.","chicago":"Kuncak, Viktor, Ruzica Piskac, Philippe Suter, and Thomas Wies. “Building a Calculus of Data Structures.” edited by Gilles Barthe and Manuel Hermenegildo, 5944:26–44. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-11319-2_6\">https://doi.org/10.1007/978-3-642-11319-2_6</a>.","ista":"Kuncak V, Piskac R, Suter P, Wies T. 2010. Building a calculus of data structures. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 5944, 26–44.","mla":"Kuncak, Viktor, et al. <i>Building a Calculus of Data Structures</i>. Edited by Gilles Barthe and Manuel Hermenegildo, vol. 5944, Springer, 2010, pp. 26–44, doi:<a href=\"https://doi.org/10.1007/978-3-642-11319-2_6\">10.1007/978-3-642-11319-2_6</a>.","ama":"Kuncak V, Piskac R, Suter P, Wies T. Building a calculus of data structures. In: Barthe G, Hermenegildo M, eds. Vol 5944. Springer; 2010:26-44. doi:<a href=\"https://doi.org/10.1007/978-3-642-11319-2_6\">10.1007/978-3-642-11319-2_6</a>","apa":"Kuncak, V., Piskac, R., Suter, P., &#38; Wies, T. (2010). Building a calculus of data structures. In G. Barthe &#38; M. Hermenegildo (Eds.) (Vol. 5944, pp. 26–44). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Madrid, Spain: Springer. <a href=\"https://doi.org/10.1007/978-3-642-11319-2_6\">https://doi.org/10.1007/978-3-642-11319-2_6</a>","ieee":"V. Kuncak, R. Piskac, P. Suter, and T. Wies, “Building a calculus of data structures,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Madrid, Spain, 2010, vol. 5944, pp. 26–44."},"page":"26 - 44","status":"public","department":[{"_id":"ToHe"}],"date_updated":"2021-01-12T07:56:31Z","title":"Building a calculus of data structures","quality_controlled":"1","language":[{"iso":"eng"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2010-01-17","name":"VMCAI: Verification, Model Checking and Abstract Interpretation","location":"Madrid, Spain","end_date":"2010-01-19"}},{"publist_id":"1078","file_date_updated":"2020-07-14T12:46:28Z","abstract":[{"lang":"eng","text":"Cloud computing is an emerging paradigm aimed to offer users pay-per-use computing resources, while leaving the burden of managing the computing infrastructure to the cloud provider. We present a new programming and pricing model that gives the cloud user the flexibility of trading execution speed and price on a per-job basis. We discuss the scheduling and resource management challenges for the cloud provider that arise in the implementation of this model. We argue that techniques from real-time and embedded software can be useful in this context."}],"publication_status":"published","date_published":"2010-10-24T00:00:00Z","oa":1,"year":"2010","has_accepted_license":"1","month":"10","oa_version":"Submitted Version","day":"24","type":"conference","date_created":"2018-12-11T12:08:33Z","author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"last_name":"Tomar","first_name":"Anmol","id":"3D8D36B6-F248-11E8-B48F-1D18A9856A87","full_name":"Tomar, Anmol"},{"last_name":"Singh","first_name":"Vasu","id":"4DAE2708-F248-11E8-B48F-1D18A9856A87","full_name":"Singh, Vasu"},{"first_name":"Thomas","last_name":"Wies","id":"447BFB88-F248-11E8-B48F-1D18A9856A87","full_name":"Wies, Thomas"},{"full_name":"Zufferey, Damien","id":"4397AC76-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3197-8736","first_name":"Damien","last_name":"Zufferey"}],"doi":"10.1145/1879021.1879022","_id":"4380","publisher":"ACM","file":[{"creator":"system","file_name":"IST-2012-48-v1+1_A_marketplace_for_cloud_resources.pdf","date_created":"2018-12-12T10:09:42Z","date_updated":"2020-07-14T12:46:28Z","file_id":"4767","relation":"main_file","checksum":"7680dd24016810710f7c977bc94f85e9","file_size":222626,"access_level":"open_access","content_type":"application/pdf"}],"citation":{"ista":"Henzinger TA, Tomar A, Singh V, Wies T, Zufferey D. 2010. A marketplace for cloud resources. EMSOFT: Embedded Software , 1–8.","mla":"Henzinger, Thomas A., et al. <i>A Marketplace for Cloud Resources</i>. ACM, 2010, pp. 1–8, doi:<a href=\"https://doi.org/10.1145/1879021.1879022\">10.1145/1879021.1879022</a>.","chicago":"Henzinger, Thomas A, Anmol Tomar, Vasu Singh, Thomas Wies, and Damien Zufferey. “A Marketplace for Cloud Resources,” 1–8. ACM, 2010. <a href=\"https://doi.org/10.1145/1879021.1879022\">https://doi.org/10.1145/1879021.1879022</a>.","short":"T.A. Henzinger, A. Tomar, V. Singh, T. Wies, D. Zufferey, in:, ACM, 2010, pp. 1–8.","ieee":"T. A. Henzinger, A. Tomar, V. Singh, T. Wies, and D. Zufferey, “A marketplace for cloud resources,” presented at the EMSOFT: Embedded Software , Arizona, USA, 2010, pp. 1–8.","ama":"Henzinger TA, Tomar A, Singh V, Wies T, Zufferey D. A marketplace for cloud resources. In: ACM; 2010:1-8. doi:<a href=\"https://doi.org/10.1145/1879021.1879022\">10.1145/1879021.1879022</a>","apa":"Henzinger, T. A., Tomar, A., Singh, V., Wies, T., &#38; Zufferey, D. (2010). A marketplace for cloud resources (pp. 1–8). Presented at the EMSOFT: Embedded Software , Arizona, USA: ACM. <a href=\"https://doi.org/10.1145/1879021.1879022\">https://doi.org/10.1145/1879021.1879022</a>"},"page":"1 - 8","scopus_import":1,"pubrep_id":"48","status":"public","department":[{"_id":"ToHe"}],"corr_author":"1","ddc":["005"],"title":"A marketplace for cloud resources","date_updated":"2024-10-09T20:54:01Z","conference":{"name":"EMSOFT: Embedded Software ","location":"Arizona, USA","end_date":"2010-10-29","start_date":"2010-10-24"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"quality_controlled":"1"},{"publisher":"IEEE","_id":"4381","file":[{"checksum":"98e534675339a8e2beca08890d048145","relation":"main_file","file_id":"5188","content_type":"application/pdf","file_size":467436,"access_level":"open_access","date_updated":"2020-07-14T12:46:28Z","creator":"system","date_created":"2018-12-12T10:16:03Z","file_name":"IST-2012-47-v1+1_FlexPRICE-_Flexible_provisioning_of_resources_in_a_cloud_environment.pdf"}],"type":"conference","doi":"10.1109/CLOUD.2010.71","date_created":"2018-12-11T12:08:33Z","author":[{"first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"first_name":"Anmol","last_name":"Tomar","id":"3D8D36B6-F248-11E8-B48F-1D18A9856A87","full_name":"Tomar, Anmol"},{"last_name":"Singh","first_name":"Vasu","id":"4DAE2708-F248-11E8-B48F-1D18A9856A87","full_name":"Singh, Vasu"},{"last_name":"Wies","first_name":"Thomas","full_name":"Wies, Thomas","id":"447BFB88-F248-11E8-B48F-1D18A9856A87"},{"id":"4397AC76-F248-11E8-B48F-1D18A9856A87","full_name":"Zufferey, Damien","orcid":"0000-0002-3197-8736","first_name":"Damien","last_name":"Zufferey"}],"month":"08","has_accepted_license":"1","day":"26","oa_version":"Submitted Version","publication_status":"published","abstract":[{"lang":"eng","text":"Cloud computing aims to give users virtually unlimited pay-per-use computing resources without the burden of managing the underlying infrastructure. We claim that, in order to realize the full potential of cloud computing, the user must be presented with a pricing model that offers flexibility at the requirements level, such as a choice between different degrees of execution speed and the cloud provider must be presented with a programming model that offers flexibility at the execution level, such as a choice between different scheduling policies. In such a flexible framework, with each job, the user purchases a virtual computer with the desired speed and cost characteristics, and the cloud provider can optimize the utilization of resources across a stream of jobs from different users. We designed a flexible framework to test our hypothesis, which is called FlexPRICE (Flexible Provisioning of Resources in a Cloud Environment) and works as follows. A user presents a job to the cloud. The cloud finds different schedules to execute the job and presents a set of quotes to the user in terms of price and duration for the execution. The user then chooses a particular quote and the cloud is obliged to execute the job according to the chosen quote. FlexPRICE thus hides the complexity of the actual scheduling decisions from the user, but still provides enough flexibility to meet the users actual demands. We implemented FlexPRICE in a simulator called PRICES that allows us to experiment with our framework. We observe that FlexPRICE provides a wide range of execution options-from fast and expensive to slow and cheap-- for the whole spectrum of data-intensive and computation-intensive jobs. We also observe that the set of quotes computed by FlexPRICE do not vary as the number of simultaneous jobs increases."}],"file_date_updated":"2020-07-14T12:46:28Z","publist_id":"1077","oa":1,"year":"2010","date_published":"2010-08-26T00:00:00Z","quality_controlled":"1","conference":{"name":"CLOUD: Cloud Computing","location":"Miami, USA","end_date":"2010-07-10","start_date":"2010-07-05"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"article_processing_charge":"No","date_updated":"2024-10-09T20:54:00Z","title":"FlexPRICE: Flexible provisioning of resources in a cloud environment","department":[{"_id":"ToHe"}],"ddc":["004"],"corr_author":"1","scopus_import":1,"page":"83 - 90","citation":{"short":"T.A. Henzinger, A. Tomar, V. Singh, T. Wies, D. Zufferey, in:, IEEE, 2010, pp. 83–90.","mla":"Henzinger, Thomas A., et al. <i>FlexPRICE: Flexible Provisioning of Resources in a Cloud Environment</i>. IEEE, 2010, pp. 83–90, doi:<a href=\"https://doi.org/10.1109/CLOUD.2010.71\">10.1109/CLOUD.2010.71</a>.","ista":"Henzinger TA, Tomar A, Singh V, Wies T, Zufferey D. 2010. FlexPRICE: Flexible provisioning of resources in a cloud environment. CLOUD: Cloud Computing, 83–90.","chicago":"Henzinger, Thomas A, Anmol Tomar, Vasu Singh, Thomas Wies, and Damien Zufferey. “FlexPRICE: Flexible Provisioning of Resources in a Cloud Environment,” 83–90. IEEE, 2010. <a href=\"https://doi.org/10.1109/CLOUD.2010.71\">https://doi.org/10.1109/CLOUD.2010.71</a>.","ieee":"T. A. Henzinger, A. Tomar, V. Singh, T. Wies, and D. Zufferey, “FlexPRICE: Flexible provisioning of resources in a cloud environment,” presented at the CLOUD: Cloud Computing, Miami, USA, 2010, pp. 83–90.","apa":"Henzinger, T. A., Tomar, A., Singh, V., Wies, T., &#38; Zufferey, D. (2010). FlexPRICE: Flexible provisioning of resources in a cloud environment (pp. 83–90). Presented at the CLOUD: Cloud Computing, Miami, USA: IEEE. <a href=\"https://doi.org/10.1109/CLOUD.2010.71\">https://doi.org/10.1109/CLOUD.2010.71</a>","ama":"Henzinger TA, Tomar A, Singh V, Wies T, Zufferey D. FlexPRICE: Flexible provisioning of resources in a cloud environment. In: IEEE; 2010:83-90. doi:<a href=\"https://doi.org/10.1109/CLOUD.2010.71\">10.1109/CLOUD.2010.71</a>"},"status":"public","pubrep_id":"47"},{"doi":"10.1145/1810479.1810529","author":[{"last_name":"Guerraoui","first_name":"Rachid","full_name":"Guerraoui, Rachid"},{"first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724"},{"first_name":"Michal","last_name":"Kapalka","full_name":"Kapalka, Michal"},{"first_name":"Vasu","last_name":"Singh","id":"4DAE2708-F248-11E8-B48F-1D18A9856A87","full_name":"Singh, Vasu"}],"date_created":"2018-12-11T12:08:34Z","type":"conference","file":[{"content_type":"application/pdf","access_level":"open_access","file_size":246409,"relation":"main_file","checksum":"f2ad6c00a6304da34bf21bcdcfd36c4b","file_id":"5080","date_updated":"2020-07-14T12:46:28Z","date_created":"2018-12-12T10:14:28Z","file_name":"IST-2012-46-v1+1_Transactions_in_the_jungle.pdf","creator":"system"}],"publisher":"ACM","_id":"4382","date_published":"2010-06-13T00:00:00Z","year":"2010","oa":1,"abstract":[{"text":"Transactional memory (TM) has shown potential to simplify the task of writing concurrent programs. Inspired by classical work on databases, formal definitions of the semantics of TM executions have been proposed. Many of these definitions assumed that accesses to shared data are solely performed through transactions. In practice, due to legacy code and concurrency libraries, transactions in a TM have to share data with non-transactional operations. The semantics of such interaction, while widely discussed by practitioners, lacks a clear formal specification. Those interactions can vary, sometimes in subtle ways, between TM implementations and underlying memory models. We propose a correctness condition for TMs, parametrized opacity, to formally capture the now folklore notion of strong atomicity by stipulating the two following intuitive requirements: first, every transaction appears as if it is executed instantaneously with respect to other transactions and non-transactional operations, and second, non-transactional operations conform to the given underlying memory model. We investigate the inherent cost of implementing parametrized opacity. We first prove that parametrized opacity requires either instrumenting non-transactional operations (for most memory models) or writing to memory by transactions using potentially expensive read-modify-write instructions (such as compare-and-swap). Then, we show that for a class of practical relaxed memory models, parametrized opacity can indeed be implemented with constant-time instrumentation of non-transactional writes and no instrumentation of non-transactional reads. We show that, in practice, parametrizing the notion of correctness allows developing more efficient TM implementations.","lang":"eng"}],"publication_status":"published","publist_id":"1076","file_date_updated":"2020-07-14T12:46:28Z","day":"13","oa_version":"Submitted Version","has_accepted_license":"1","month":"06","date_updated":"2024-10-21T06:03:05Z","title":"Transactions in the jungle","quality_controlled":"1","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","conference":{"name":"SPAA: ACM Symposium on Parallel Algorithms and Architectures","location":"Santorini, Greece","end_date":"2010-06-15","start_date":"2010-06-13"},"language":[{"iso":"eng"}],"status":"public","pubrep_id":"46","scopus_import":"1","page":"263 - 272","citation":{"ieee":"R. Guerraoui, T. A. Henzinger, M. Kapalka, and V. Singh, “Transactions in the jungle,” presented at the SPAA: ACM Symposium on Parallel Algorithms and Architectures, Santorini, Greece, 2010, pp. 263–272.","ama":"Guerraoui R, Henzinger TA, Kapalka M, Singh V. Transactions in the jungle. In: ACM; 2010:263-272. doi:<a href=\"https://doi.org/10.1145/1810479.1810529\">10.1145/1810479.1810529</a>","apa":"Guerraoui, R., Henzinger, T. A., Kapalka, M., &#38; Singh, V. (2010). Transactions in the jungle (pp. 263–272). Presented at the SPAA: ACM Symposium on Parallel Algorithms and Architectures, Santorini, Greece: ACM. <a href=\"https://doi.org/10.1145/1810479.1810529\">https://doi.org/10.1145/1810479.1810529</a>","short":"R. Guerraoui, T.A. Henzinger, M. Kapalka, V. Singh, in:, ACM, 2010, pp. 263–272.","mla":"Guerraoui, Rachid, et al. <i>Transactions in the Jungle</i>. ACM, 2010, pp. 263–72, doi:<a href=\"https://doi.org/10.1145/1810479.1810529\">10.1145/1810479.1810529</a>.","ista":"Guerraoui R, Henzinger TA, Kapalka M, Singh V. 2010. Transactions in the jungle. SPAA: ACM Symposium on Parallel Algorithms and Architectures, 263–272.","chicago":"Guerraoui, Rachid, Thomas A Henzinger, Michal Kapalka, and Vasu Singh. “Transactions in the Jungle,” 263–72. ACM, 2010. <a href=\"https://doi.org/10.1145/1810479.1810529\">https://doi.org/10.1145/1810479.1810529</a>."},"ddc":["005"],"department":[{"_id":"ToHe"}]},{"alternative_title":["LNCS"],"arxiv":1,"date_published":"2010-07-01T00:00:00Z","volume":6174,"oa":1,"year":"2010","publist_id":"1068","related_material":{"record":[{"status":"public","id":"5393","relation":"earlier_version"}]},"file_date_updated":"2020-07-14T12:46:28Z","abstract":[{"text":"GIST is a tool that (a) solves the qualitative analysis problem of turn-based probabilistic games with ω-regular objectives; and (b) synthesizes reasonable environment assumptions for synthesis of unrealizable specifications. Our tool provides the first and efficient implementations of several reduction-based techniques to solve turn-based probabilistic games, and uses the analysis of turn-based probabilistic games for synthesizing environment assumptions for unrealizable specifications.","lang":"eng"}],"publication_status":"published","oa_version":"Submitted Version","ec_funded":1,"external_id":{"arxiv":["1004.2367"]},"day":"01","has_accepted_license":"1","month":"07","date_created":"2018-12-11T12:08:36Z","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Barbara","last_name":"Jobstmann","full_name":"Jobstmann, Barbara"},{"id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87","full_name":"Radhakrishna, Arjun","first_name":"Arjun","last_name":"Radhakrishna"}],"doi":"10.1007/978-3-642-14295-6_57","project":[{"grant_number":"215543","call_identifier":"FP7","name":"COMponent-Based Embedded Systems design Techniques","_id":"25EFB36C-B435-11E9-9278-68D0E5697425"},{"_id":"25F1337C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Design for Embedded Systems","grant_number":"214373"}],"intvolume":"      6174","type":"conference","file":[{"access_level":"open_access","file_size":293605,"content_type":"application/pdf","file_id":"5221","relation":"main_file","checksum":"0b2ef8c4037ffccc6902d93081af24f7","file_name":"IST-2012-43-v1+1_GIST-_A_solver_for_probabilistic_games.pdf","date_created":"2018-12-12T10:16:33Z","creator":"system","date_updated":"2020-07-14T12:46:28Z"}],"_id":"4388","publisher":"Springer","pubrep_id":"43","status":"public","page":"665 - 669","citation":{"short":"K. Chatterjee, T.A. Henzinger, B. Jobstmann, A. Radhakrishna, in:, Springer, 2010, pp. 665–669.","mla":"Chatterjee, Krishnendu, et al. <i>GIST: A Solver for Probabilistic Games</i>. Vol. 6174, Springer, 2010, pp. 665–69, doi:<a href=\"https://doi.org/10.1007/978-3-642-14295-6_57\">10.1007/978-3-642-14295-6_57</a>.","ista":"Chatterjee K, Henzinger TA, Jobstmann B, Radhakrishna A. 2010. GIST: A solver for probabilistic games. CAV: Computer Aided Verification, LNCS, vol. 6174, 665–669.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Barbara Jobstmann, and Arjun Radhakrishna. “GIST: A Solver for Probabilistic Games,” 6174:665–69. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-14295-6_57\">https://doi.org/10.1007/978-3-642-14295-6_57</a>.","ieee":"K. Chatterjee, T. A. Henzinger, B. Jobstmann, and A. Radhakrishna, “GIST: A solver for probabilistic games,” presented at the CAV: Computer Aided Verification, Edinburgh, UK, 2010, vol. 6174, pp. 665–669.","apa":"Chatterjee, K., Henzinger, T. A., Jobstmann, B., &#38; Radhakrishna, A. (2010). GIST: A solver for probabilistic games (Vol. 6174, pp. 665–669). Presented at the CAV: Computer Aided Verification, Edinburgh, UK: Springer. <a href=\"https://doi.org/10.1007/978-3-642-14295-6_57\">https://doi.org/10.1007/978-3-642-14295-6_57</a>","ama":"Chatterjee K, Henzinger TA, Jobstmann B, Radhakrishna A. GIST: A solver for probabilistic games. In: Vol 6174. Springer; 2010:665-669. doi:<a href=\"https://doi.org/10.1007/978-3-642-14295-6_57\">10.1007/978-3-642-14295-6_57</a>"},"scopus_import":1,"ddc":["004"],"corr_author":"1","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"GIST: A solver for probabilistic games","date_updated":"2024-10-09T20:54:00Z","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"conference":{"location":"Edinburgh, UK","end_date":"2010-07-17","name":"CAV: Computer Aided Verification","start_date":"2010-07-15"},"quality_controlled":"1"},{"has_accepted_license":"1","month":"08","day":"23","oa_version":"Submitted Version","abstract":[{"text":"Digital components play a central role in the design of complex embedded systems. These components are interconnected with other, possibly analog, devices and the physical environment. This environment cannot be entirely captured and can provide inaccurate input data to the component. It is thus important for digital components to have a robust behavior, i.e. the presence of a small change in the input sequences should not result in a drastic change in the output sequences. In this paper, we study a notion of robustness for sequential circuits. However, since sequential circuits may have parts that are naturally discontinuous (e.g., digital controllers with switching behavior), we need a flexible framework that accommodates this fact and leaves discontinuous parts of the circuit out from the robustness analysis. As a consequence, we consider sequential circuits that have their input variables partitioned into two disjoint sets: control and disturbance variables. Our contributions are (1) a definition of robustness for sequential circuits as a form of continuity with respect to disturbance variables, (2) the characterization of the exact class of sequential circuits that are robust according to our definition, (3) an algorithm to decide whether a sequential circuit is robust or not.","lang":"eng"}],"publication_status":"published","publist_id":"1069","file_date_updated":"2020-07-14T12:46:28Z","date_published":"2010-08-23T00:00:00Z","oa":1,"year":"2010","publisher":"IEEE","_id":"4389","file":[{"creator":"system","date_created":"2018-12-12T10:09:10Z","file_name":"IST-2012-44-v1+1_Robustness_of_sequential_circuits.pdf","date_updated":"2020-07-14T12:46:28Z","file_id":"4733","checksum":"42b2952bfc6b6974617bd554842b904a","relation":"main_file","access_level":"open_access","file_size":159920,"content_type":"application/pdf"}],"type":"conference","doi":"10.1109/ACSD.2010.26","date_created":"2018-12-11T12:08:36Z","author":[{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"first_name":"Axel","last_name":"Legay","full_name":"Legay, Axel"},{"last_name":"Nickovic","first_name":"Dejan","full_name":"Nickovic, Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87"}],"department":[{"_id":"ToHe"}],"ddc":["004"],"scopus_import":1,"page":"77 - 84","citation":{"ieee":"L. Doyen, T. A. Henzinger, A. Legay, and D. Nickovic, “Robustness of sequential circuits,” presented at the ACSD: Application of Concurrency to System Design, 2010, pp. 77–84.","apa":"Doyen, L., Henzinger, T. A., Legay, A., &#38; Nickovic, D. (2010). Robustness of sequential circuits (pp. 77–84). Presented at the ACSD: Application of Concurrency to System Design, IEEE. <a href=\"https://doi.org/10.1109/ACSD.2010.26\">https://doi.org/10.1109/ACSD.2010.26</a>","ama":"Doyen L, Henzinger TA, Legay A, Nickovic D. Robustness of sequential circuits. In: IEEE; 2010:77-84. doi:<a href=\"https://doi.org/10.1109/ACSD.2010.26\">10.1109/ACSD.2010.26</a>","ista":"Doyen L, Henzinger TA, Legay A, Nickovic D. 2010. Robustness of sequential circuits. ACSD: Application of Concurrency to System Design, 77–84.","mla":"Doyen, Laurent, et al. <i>Robustness of Sequential Circuits</i>. IEEE, 2010, pp. 77–84, doi:<a href=\"https://doi.org/10.1109/ACSD.2010.26\">10.1109/ACSD.2010.26</a>.","chicago":"Doyen, Laurent, Thomas A Henzinger, Axel Legay, and Dejan Nickovic. “Robustness of Sequential Circuits,” 77–84. IEEE, 2010. <a href=\"https://doi.org/10.1109/ACSD.2010.26\">https://doi.org/10.1109/ACSD.2010.26</a>.","short":"L. Doyen, T.A. Henzinger, A. Legay, D. Nickovic, in:, IEEE, 2010, pp. 77–84."},"pubrep_id":"44","status":"public","quality_controlled":"1","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","conference":{"name":"ACSD: Application of Concurrency to System Design"},"language":[{"iso":"eng"}],"date_updated":"2021-01-12T07:56:36Z","title":"Robustness of sequential circuits"},{"date_updated":"2024-10-21T06:03:05Z","title":"Model checking of linearizability of concurrent list implementations","article_processing_charge":"No","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Edinburgh, UK","end_date":"2010-07-17","name":"CAV: Computer Aided Verification","start_date":"2010-07-15"},"language":[{"iso":"eng"}],"pubrep_id":"27","status":"public","scopus_import":"1","page":"465 - 479","citation":{"apa":"Cerny, P., Radhakrishna, A., Zufferey, D., Chaudhuri, S., &#38; Alur, R. (2010). Model checking of linearizability of concurrent list implementations (Vol. 6174, pp. 465–479). Presented at the CAV: Computer Aided Verification, Edinburgh, UK: Springer. <a href=\"https://doi.org/10.1007/978-3-642-14295-6_41\">https://doi.org/10.1007/978-3-642-14295-6_41</a>","ama":"Cerny P, Radhakrishna A, Zufferey D, Chaudhuri S, Alur R. Model checking of linearizability of concurrent list implementations. In: Vol 6174. Springer; 2010:465-479. doi:<a href=\"https://doi.org/10.1007/978-3-642-14295-6_41\">10.1007/978-3-642-14295-6_41</a>","ieee":"P. Cerny, A. Radhakrishna, D. Zufferey, S. Chaudhuri, and R. Alur, “Model checking of linearizability of concurrent list implementations,” presented at the CAV: Computer Aided Verification, Edinburgh, UK, 2010, vol. 6174, pp. 465–479.","chicago":"Cerny, Pavol, Arjun Radhakrishna, Damien Zufferey, Swarat Chaudhuri, and Rajeev Alur. “Model Checking of Linearizability of Concurrent List Implementations,” 6174:465–79. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-14295-6_41\">https://doi.org/10.1007/978-3-642-14295-6_41</a>.","ista":"Cerny P, Radhakrishna A, Zufferey D, Chaudhuri S, Alur R. 2010. Model checking of linearizability of concurrent list implementations. CAV: Computer Aided Verification, LNCS, vol. 6174, 465–479.","mla":"Cerny, Pavol, et al. <i>Model Checking of Linearizability of Concurrent List Implementations</i>. Vol. 6174, Springer, 2010, pp. 465–79, doi:<a href=\"https://doi.org/10.1007/978-3-642-14295-6_41\">10.1007/978-3-642-14295-6_41</a>.","short":"P. Cerny, A. Radhakrishna, D. Zufferey, S. Chaudhuri, R. Alur, in:, Springer, 2010, pp. 465–479."},"ddc":["000"],"corr_author":"1","department":[{"_id":"ToHe"}],"doi":"10.1007/978-3-642-14295-6_41","date_created":"2018-12-11T12:08:36Z","author":[{"first_name":"Pavol","last_name":"Cerny","full_name":"Cerny, Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Radhakrishna","first_name":"Arjun","id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87","full_name":"Radhakrishna, Arjun"},{"first_name":"Damien","last_name":"Zufferey","full_name":"Zufferey, Damien","id":"4397AC76-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3197-8736"},{"full_name":"Chaudhuri, Swarat","last_name":"Chaudhuri","first_name":"Swarat"},{"full_name":"Alur, Rajeev","last_name":"Alur","first_name":"Rajeev"}],"type":"conference","intvolume":"      6174","file":[{"content_type":"application/pdf","file_size":3633276,"access_level":"open_access","checksum":"2eb211ce40b3c4988bce3a3592980704","relation":"main_file","file_id":"7873","date_updated":"2020-07-14T12:46:28Z","date_created":"2020-05-19T16:31:56Z","file_name":"2010_CAV_Cerny.pdf","creator":"dernst"}],"publisher":"Springer","_id":"4390","year":"2010","oa":1,"volume":6174,"date_published":"2010-07-01T00:00:00Z","alternative_title":["LNCS"],"publication_status":"published","abstract":[{"lang":"eng","text":"Concurrent data structures with fine-grained synchronization are notoriously difficult to implement correctly. The difficulty of reasoning about these implementations does not stem from the number of variables or the program size, but rather from the large number of possible interleavings. These implementations are therefore prime candidates for model checking. We introduce an algorithm for verifying linearizability of singly-linked heap-based concurrent data structures. We consider a model consisting of an unbounded heap where each vertex stores an element from an unbounded data domain, with a restricted set of operations for testing and updating pointers and data elements. Our main result is that linearizability is decidable for programs that invoke a fixed number of methods, possibly in parallel. This decidable fragment covers many of the common implementation techniques — fine-grained locking, lazy synchronization, and lock-free synchronization. We also show how the technique can be used to verify optimistic implementations with the help of programmer annotations. We developed a verification tool CoLT and evaluated it on a representative sample of Java implementations of the concurrent set data structure. The tool verified linearizability of a number of implementations, found a known error in a lock-free implementation and proved that the corrected version is linearizable."}],"file_date_updated":"2020-07-14T12:46:28Z","publist_id":"1066","related_material":{"record":[{"relation":"earlier_version","id":"5391","status":"public"}]},"day":"01","oa_version":"Submitted Version","month":"07","has_accepted_license":"1"},{"department":[{"_id":"ToHe"}],"corr_author":"1","publication":"Time For Verification: Essays in Memory of Amir Pnueli","page":"42 - 60","citation":{"ista":"Cerny P, Henzinger TA, Radhakrishna A. 2010.Quantitative Simulation Games. In: Time For Verification: Essays in Memory of Amir Pnueli. LNCS, vol. 6200, 42–60.","mla":"Cerny, Pavol, et al. “Quantitative Simulation Games.” <i>Time For Verification: Essays in Memory of Amir Pnueli</i>, edited by Zohar Manna and Doron Peled, vol. 6200, Springer, 2010, pp. 42–60, doi:<a href=\"https://doi.org/10.1007/978-3-642-13754-9_3\">10.1007/978-3-642-13754-9_3</a>.","chicago":"Cerny, Pavol, Thomas A Henzinger, and Arjun Radhakrishna. “Quantitative Simulation Games.” In <i>Time For Verification: Essays in Memory of Amir Pnueli</i>, edited by Zohar Manna and Doron Peled, 6200:42–60. Essays in Memory of Amir Pnueli. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-13754-9_3\">https://doi.org/10.1007/978-3-642-13754-9_3</a>.","short":"P. Cerny, T.A. Henzinger, A. Radhakrishna, in:, Z. Manna, D. Peled (Eds.), Time For Verification: Essays in Memory of Amir Pnueli, Springer, 2010, pp. 42–60.","ieee":"P. Cerny, T. A. Henzinger, and A. Radhakrishna, “Quantitative Simulation Games,” in <i>Time For Verification: Essays in Memory of Amir Pnueli</i>, vol. 6200, Z. Manna and D. Peled, Eds. Springer, 2010, pp. 42–60.","ama":"Cerny P, Henzinger TA, Radhakrishna A. Quantitative Simulation Games. In: Manna Z, Peled D, eds. <i>Time For Verification: Essays in Memory of Amir Pnueli</i>. Vol 6200. Essays in Memory of Amir Pnueli. Springer; 2010:42-60. doi:<a href=\"https://doi.org/10.1007/978-3-642-13754-9_3\">10.1007/978-3-642-13754-9_3</a>","apa":"Cerny, P., Henzinger, T. A., &#38; Radhakrishna, A. (2010). Quantitative Simulation Games. In Z. Manna &#38; D. Peled (Eds.), <i>Time For Verification: Essays in Memory of Amir Pnueli</i> (Vol. 6200, pp. 42–60). Springer. <a href=\"https://doi.org/10.1007/978-3-642-13754-9_3\">https://doi.org/10.1007/978-3-642-13754-9_3</a>"},"scopus_import":1,"status":"public","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"quality_controlled":"1","title":"Quantitative Simulation Games","date_updated":"2024-10-09T20:53:58Z","month":"07","series_title":"Essays in Memory of Amir Pnueli","ec_funded":1,"oa_version":"None","day":"29","publist_id":"1064","publication_status":"published","abstract":[{"lang":"eng","text":"While a boolean notion of correctness is given by a preorder on systems and properties, a quantitative notion of correctness is defined by a distance function on systems and properties, where the distance between a system and a property provides a measure of “fit” or “desirability.” In this article, we explore several ways how the simulation preorder can be generalized to a distance function. This is done by equipping the classical simulation game between a system and a property with quantitative objectives. In particular, for systems that satisfy a property, a quantitative simulation game can measure the “robustness” of the satisfaction, that is, how much the system can deviate from its nominal behavior while still satisfying the property. For systems that violate a property, a quantitative simulation game can measure the “seriousness” of the violation, that is, how much the property has to be modified so that it is satisfied by the system. These distances can be computed in polynomial time, since the computation reduces to the value problem in limit average games with constant weights. Finally, we demonstrate how the robustness distance can be used to measure how many transmission errors are tolerated by error correcting codes. "}],"alternative_title":["LNCS"],"year":"2010","volume":6200,"date_published":"2010-07-29T00:00:00Z","_id":"4392","publisher":"Springer","intvolume":"      6200","type":"book_chapter","author":[{"first_name":"Pavol","last_name":"Cerny","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","full_name":"Cerny, Pavol"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87","full_name":"Radhakrishna, Arjun","first_name":"Arjun","last_name":"Radhakrishna"}],"editor":[{"full_name":"Manna, Zohar","first_name":"Zohar","last_name":"Manna"},{"first_name":"Doron","last_name":"Peled","full_name":"Peled, Doron"}],"date_created":"2018-12-11T12:08:37Z","project":[{"grant_number":"215543","name":"COMponent-Based Embedded Systems design Techniques","call_identifier":"FP7","_id":"25EFB36C-B435-11E9-9278-68D0E5697425"},{"grant_number":"214373","_id":"25F1337C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Design for Embedded Systems"}],"doi":"10.1007/978-3-642-13754-9_3"}]