[{"publication":"Journal of Cell Science","intvolume":"       118","publist_id":"1964","type":"journal_article","_id":"4155","date_created":"2018-12-11T12:07:16Z","year":"2005","day":"01","status":"public","doi":"10.1242/​jcs.02547","page":"4199 - 4206","issue":"18","abstract":[{"text":"During vertebrate gastrulation, progenitor cells of different germ layers acquire specific adhesive properties that contribute to germ layer formation and separation. Wnt signals have been suggested to function in this process by modulating the different levels of adhesion between the germ layers, however, direct evidence for this is still lacking. Here we show that Wnt11, a key signal regulating gastrulation movements, is needed for the adhesion of zebrafish mesendodermal progenitor cells to fibronectin, an abundant extracellular matrix component during gastrulation. To measure this effect, we developed an assay to quantify the adhesion of single zebrafish primary mesendodermal progenitors using atomic-force microscopy (AFM). We observed significant differences in detachment force and work between cultured mesendodermal progenitors from wild-type embryos and from slb/wit11 mutant embryos, which carry a loss-of-function mutation in the wnt11 gene, when tested on fibronectin-coated substrates. These differences were probably due to reduced adhesion to the fibronectin substrate as neither the overall cell morphology nor the cell elasticity grossly differed between wild-type and mutant cells. Furthermore, in the presence of inhibitors of fibronectin-integrin binding, such as RGD peptides, the adhesion force and work were strongly decreased, indicating that integrins are involved in the binding of mesendodermal progenitors in our assay. These findings demonstrate that AFM can be used to quantitatively determine the substrate-adhesion of cultured primary gastrulating cells and provide insight into the role of Wnt11 signalling in modulating cell adhesion at the single cell scale.","lang":"eng"}],"publication_status":"published","month":"01","article_processing_charge":"No","title":"Measuring cell adhesion forces of primary gastrulating cells from zebrafish using atomic force microscopy","volume":118,"date_published":"2005-01-01T00:00:00Z","publisher":"Company of Biologists","language":[{"iso":"eng"}],"oa_version":"None","citation":{"short":"P. Puech, A. Taubenberger, F. Ulrich, M. Krieg, D. Mueller, C.-P.J. Heisenberg, Journal of Cell Science 118 (2005) 4199–4206.","mla":"Puech, Pierre, et al. “Measuring Cell Adhesion Forces of Primary Gastrulating Cells from Zebrafish Using Atomic Force Microscopy.” <i>Journal of Cell Science</i>, vol. 118, no. 18, Company of Biologists, 2005, pp. 4199–206, doi:<a href=\"https://doi.org/10.1242/​jcs.02547\">10.1242/​jcs.02547</a>.","apa":"Puech, P., Taubenberger, A., Ulrich, F., Krieg, M., Mueller, D., &#38; Heisenberg, C.-P. J. (2005). Measuring cell adhesion forces of primary gastrulating cells from zebrafish using atomic force microscopy. <i>Journal of Cell Science</i>. Company of Biologists. <a href=\"https://doi.org/10.1242/​jcs.02547\">https://doi.org/10.1242/​jcs.02547</a>","ama":"Puech P, Taubenberger A, Ulrich F, Krieg M, Mueller D, Heisenberg C-PJ. Measuring cell adhesion forces of primary gastrulating cells from zebrafish using atomic force microscopy. <i>Journal of Cell Science</i>. 2005;118(18):4199-4206. doi:<a href=\"https://doi.org/10.1242/​jcs.02547\">10.1242/​jcs.02547</a>","ista":"Puech P, Taubenberger A, Ulrich F, Krieg M, Mueller D, Heisenberg C-PJ. 2005. Measuring cell adhesion forces of primary gastrulating cells from zebrafish using atomic force microscopy. Journal of Cell Science. 118(18), 4199–4206.","chicago":"Puech, Pierre, Anna Taubenberger, Florian Ulrich, Michael Krieg, Daniel Mueller, and Carl-Philipp J Heisenberg. “Measuring Cell Adhesion Forces of Primary Gastrulating Cells from Zebrafish Using Atomic Force Microscopy.” <i>Journal of Cell Science</i>. Company of Biologists, 2005. <a href=\"https://doi.org/10.1242/​jcs.02547\">https://doi.org/10.1242/​jcs.02547</a>.","ieee":"P. Puech, A. Taubenberger, F. Ulrich, M. Krieg, D. Mueller, and C.-P. J. Heisenberg, “Measuring cell adhesion forces of primary gastrulating cells from zebrafish using atomic force microscopy,” <i>Journal of Cell Science</i>, vol. 118, no. 18. Company of Biologists, pp. 4199–4206, 2005."},"date_updated":"2021-01-12T07:54:54Z","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Pierre","last_name":"Puech","full_name":"Puech, Pierre"},{"full_name":"Taubenberger, Anna","last_name":"Taubenberger","first_name":"Anna"},{"full_name":"Ulrich, Florian","first_name":"Florian","last_name":"Ulrich"},{"full_name":"Krieg, Michael","first_name":"Michael","last_name":"Krieg"},{"full_name":"Mueller, Daniel","first_name":"Daniel","last_name":"Mueller"},{"last_name":"Heisenberg","first_name":"Carl-Philipp J","orcid":"0000-0002-0912-4566","id":"39427864-F248-11E8-B48F-1D18A9856A87","full_name":"Heisenberg, Carl-Philipp J"}]},{"publist_id":"1952","intvolume":"       132","publication":"Development","date_created":"2018-12-11T12:07:21Z","_id":"4167","type":"journal_article","status":"public","day":"15","year":"2005","doi":"10.1242/dev.01611","page":"645 - 658","month":"02","publication_status":"published","abstract":[{"text":"In this study, we elucidate the roles of the winged-helix transcription factor Foxa2 in ventral CNS development in zebrafish. Through cloning of monorail (mol), which we find encodes the transcription factor Foxa2, and phenotypic analysis of mol(-/-) embryos, we show that floorplate is induced in the absence of Foxa2 function but fails to further differentiate. In mol(-/-) mutants, expression of Foxa and Hh family genes is not maintained in floorplate cells and lateral expansion of the floorplate fails to occur. Our results suggest that this is due to defects both in the regulation of Hh activity in medial floorplate cells as well as cell-autonomous requirements for Foxa2 in the prospective laterally positioned floorplate cells themselves. Foxa2 is also required for induction and/or patterning of several distinct cell types in the ventral CNS. Serotonergic neurones of the raphe nucleus and the trochlear motor nucleus are absent in mol(-/-) embryos, and oculomotor and facial motoneurones ectopically occupy ventral CNS midline positions in the midbrain and hindbrain. There is also a severe reduction of prospective oligodendrocytes in the midbrain and hindbrain. Finally, in the absence of Foxa2, at least two likely Hh pathway target genes are ectopically expressed in more dorsal regions of the midbrain and hindbrain ventricular neuroepithelium, raising the possibility that Foxa2 activity may normally be required to limit the range of action of secreted Hh proteins.","lang":"eng"}],"issue":"4","publisher":"Company of Biologists","language":[{"iso":"eng"}],"date_published":"2005-02-15T00:00:00Z","volume":132,"title":"Monorail/Foxa2 regulates floorplate differentiation and specification of oligodendrocytes, serotonergic raphe neurones and cranial motoneurones","article_processing_charge":"No","extern":"1","date_updated":"2021-01-12T07:55:00Z","oa_version":"None","citation":{"short":"W. Norton, M. Mangoli, Z. Lele, H. Pogoda, B. Diamond, S. Mercurio, C. Russell, H. Teraoka, H. Stickney, G. Rauch, C.-P.J. Heisenberg, C. Houart, T. Schilling, H. Frohnhoefer, S. Rastegar, C. Neumann, R.M. Gardiner, U. Strähle, R. Geisler, M. Rees, W. Talbot, S. Wilson, Development 132 (2005) 645–658.","mla":"Norton, Will, et al. “Monorail/Foxa2 Regulates Floorplate Differentiation and Specification of Oligodendrocytes, Serotonergic Raphe Neurones and Cranial Motoneurones.” <i>Development</i>, vol. 132, no. 4, Company of Biologists, 2005, pp. 645–58, doi:<a href=\"https://doi.org/10.1242/dev.01611\">10.1242/dev.01611</a>.","ista":"Norton W, Mangoli M, Lele Z, Pogoda H, Diamond B, Mercurio S, Russell C, Teraoka H, Stickney H, Rauch G, Heisenberg C-PJ, Houart C, Schilling T, Frohnhoefer H, Rastegar S, Neumann C, Gardiner RM, Strähle U, Geisler R, Rees M, Talbot W, Wilson S. 2005. Monorail/Foxa2 regulates floorplate differentiation and specification of oligodendrocytes, serotonergic raphe neurones and cranial motoneurones. Development. 132(4), 645–658.","chicago":"Norton, Will, Maryam Mangoli, Zsolt Lele, Hans Pogoda, Brianne Diamond, Sara Mercurio, Claire Russell, et al. “Monorail/Foxa2 Regulates Floorplate Differentiation and Specification of Oligodendrocytes, Serotonergic Raphe Neurones and Cranial Motoneurones.” <i>Development</i>. Company of Biologists, 2005. <a href=\"https://doi.org/10.1242/dev.01611\">https://doi.org/10.1242/dev.01611</a>.","ama":"Norton W, Mangoli M, Lele Z, et al. Monorail/Foxa2 regulates floorplate differentiation and specification of oligodendrocytes, serotonergic raphe neurones and cranial motoneurones. <i>Development</i>. 2005;132(4):645-658. doi:<a href=\"https://doi.org/10.1242/dev.01611\">10.1242/dev.01611</a>","apa":"Norton, W., Mangoli, M., Lele, Z., Pogoda, H., Diamond, B., Mercurio, S., … Wilson, S. (2005). Monorail/Foxa2 regulates floorplate differentiation and specification of oligodendrocytes, serotonergic raphe neurones and cranial motoneurones. <i>Development</i>. Company of Biologists. <a href=\"https://doi.org/10.1242/dev.01611\">https://doi.org/10.1242/dev.01611</a>","ieee":"W. Norton <i>et al.</i>, “Monorail/Foxa2 regulates floorplate differentiation and specification of oligodendrocytes, serotonergic raphe neurones and cranial motoneurones,” <i>Development</i>, vol. 132, no. 4. Company of Biologists, pp. 645–658, 2005."},"author":[{"first_name":"Will","last_name":"Norton","full_name":"Norton, Will"},{"full_name":"Mangoli, Maryam","last_name":"Mangoli","first_name":"Maryam"},{"full_name":"Lele, Zsolt","last_name":"Lele","first_name":"Zsolt"},{"full_name":"Pogoda, Hans","last_name":"Pogoda","first_name":"Hans"},{"full_name":"Diamond, Brianne","first_name":"Brianne","last_name":"Diamond"},{"full_name":"Mercurio, Sara","first_name":"Sara","last_name":"Mercurio"},{"last_name":"Russell","first_name":"Claire","full_name":"Russell, Claire"},{"full_name":"Teraoka, Hiroki","last_name":"Teraoka","first_name":"Hiroki"},{"first_name":"Heather","last_name":"Stickney","full_name":"Stickney, Heather"},{"full_name":"Rauch, Gerd","last_name":"Rauch","first_name":"Gerd"},{"last_name":"Heisenberg","first_name":"Carl-Philipp J","orcid":"0000-0002-0912-4566","id":"39427864-F248-11E8-B48F-1D18A9856A87","full_name":"Heisenberg, Carl-Philipp J"},{"full_name":"Houart, Corinne","first_name":"Corinne","last_name":"Houart"},{"full_name":"Schilling, Thomas","first_name":"Thomas","last_name":"Schilling"},{"full_name":"Frohnhoefer, Hans","first_name":"Hans","last_name":"Frohnhoefer"},{"full_name":"Rastegar, Sepand","first_name":"Sepand","last_name":"Rastegar"},{"first_name":"Carl","last_name":"Neumann","full_name":"Neumann, Carl"},{"full_name":"Gardiner, R Mark","first_name":"R Mark","last_name":"Gardiner"},{"full_name":"Strähle, Uwe","last_name":"Strähle","first_name":"Uwe"},{"full_name":"Geisler, Robert","first_name":"Robert","last_name":"Geisler"},{"full_name":"Rees, Michelle","first_name":"Michelle","last_name":"Rees"},{"full_name":"Talbot, William","last_name":"Talbot","first_name":"William"},{"full_name":"Wilson, Stephen","last_name":"Wilson","first_name":"Stephen"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"publication_status":"published","month":"03","abstract":[{"lang":"eng","text":"During vertebrate gastrulation, the three germ layers, ectoderm, mesoderm and endoderm are formed, and the resulting progenitor cells are brought into the positions from which they will later contribute more complex tissues and organs. A core element in this process is the internalization of mesodermal and endodermal progenitors at the onset of gastrulation. Although many of the molecules that induce mesendoderm have been identified, much less is known about the cellular mechanisms underlying mesendodermal cell internalization and germ layer formation. Here we show that at the onset of zebrafish gastrulation, mesendodermal progenitors in dorsal/axial regions of the germ ring internalize by single cell delamination. Once internalized, mesendodermal progenitors upregulate ECadherin (Cadherin 1) expression, become increasingly motile and eventually migrate along the overlying epiblast (ectodermal) cell layer towards the animal pole of the gastrula. When E-Cadherin function is compromised, mesendodermal progenitors still internalize, but, with gastrulation proceeding, fail to elongate and efficiently migrate along the epiblast, whereas epiblast cells themselves exhibit reduced radial cell intercalation movements. This indicates that cadherin-mediated cell-cell adhesion is needed within the forming shield for both epiblast cell intercalation, and mesendodermal progenitor cell elongation and migration during zebrafish gastrulation. Our data provide insight into the cellular mechanisms underlying mesendodermal progenitor cell internalization and subsequent migration during zebrafish gastrulation, and the role of cadherin-mediated cell-cell adhesion in these processes."}],"issue":"6","date_published":"2005-03-15T00:00:00Z","publisher":"Company of Biologists","language":[{"iso":"eng"}],"title":"Shield formation at the onset of zebrafish gastrulation","volume":132,"article_processing_charge":"No","extern":"1","date_updated":"2021-01-12T07:55:02Z","oa_version":"None","citation":{"mla":"Montero, Juan, et al. “Shield Formation at the Onset of Zebrafish Gastrulation.” <i>Development</i>, vol. 132, no. 6, Company of Biologists, 2005, pp. 1187–98, doi:<a href=\"https://doi.org/10.1242/dev.01667\">10.1242/dev.01667</a>.","short":"J. Montero, L. Carvalho, M. Wilsch Bräuninger, B. Kilian, C. Mustafa, C.-P.J. Heisenberg, Development 132 (2005) 1187–1198.","ieee":"J. Montero, L. Carvalho, M. Wilsch Bräuninger, B. Kilian, C. Mustafa, and C.-P. J. Heisenberg, “Shield formation at the onset of zebrafish gastrulation,” <i>Development</i>, vol. 132, no. 6. Company of Biologists, pp. 1187–1198, 2005.","apa":"Montero, J., Carvalho, L., Wilsch Bräuninger, M., Kilian, B., Mustafa, C., &#38; Heisenberg, C.-P. J. (2005). Shield formation at the onset of zebrafish gastrulation. <i>Development</i>. Company of Biologists. <a href=\"https://doi.org/10.1242/dev.01667\">https://doi.org/10.1242/dev.01667</a>","chicago":"Montero, Juan, Lara Carvalho, Michaela Wilsch Bräuninger, Beate Kilian, Chigdem Mustafa, and Carl-Philipp J Heisenberg. “Shield Formation at the Onset of Zebrafish Gastrulation.” <i>Development</i>. Company of Biologists, 2005. <a href=\"https://doi.org/10.1242/dev.01667\">https://doi.org/10.1242/dev.01667</a>.","ista":"Montero J, Carvalho L, Wilsch Bräuninger M, Kilian B, Mustafa C, Heisenberg C-PJ. 2005. Shield formation at the onset of zebrafish gastrulation. Development. 132(6), 1187–1198.","ama":"Montero J, Carvalho L, Wilsch Bräuninger M, Kilian B, Mustafa C, Heisenberg C-PJ. Shield formation at the onset of zebrafish gastrulation. <i>Development</i>. 2005;132(6):1187-1198. doi:<a href=\"https://doi.org/10.1242/dev.01667\">10.1242/dev.01667</a>"},"author":[{"last_name":"Montero","first_name":"Juan","full_name":"Montero, Juan"},{"first_name":"Lara","last_name":"Carvalho","full_name":"Carvalho, Lara"},{"full_name":"Wilsch Bräuninger, Michaela","first_name":"Michaela","last_name":"Wilsch Bräuninger"},{"first_name":"Beate","last_name":"Kilian","full_name":"Kilian, Beate"},{"full_name":"Mustafa, Chigdem","first_name":"Chigdem","last_name":"Mustafa"},{"orcid":"0000-0002-0912-4566","last_name":"Heisenberg","first_name":"Carl-Philipp J","full_name":"Heisenberg, Carl-Philipp J","id":"39427864-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"1947","intvolume":"       132","publication":"Development","date_created":"2018-12-11T12:07:22Z","_id":"4171","type":"journal_article","status":"public","year":"2005","day":"15","page":"1187 - 1198","doi":"10.1242/dev.01667"},{"volume":122,"title":"Misshapen mediates actin-based cell contraction during zebrafish epiboly and Drosophila dorsal closure","article_processing_charge":"No","language":[{"iso":"eng"}],"date_published":"2005-01-01T00:00:00Z","publisher":"Elsevier","issue":"Supplement 1","month":"01","publication_status":"published","abstract":[{"text":"The spreading of an epithelial cell sheet over a substrate is a common process during embryogenesis. Typical examples include epiboly during zebrafish gastrulation and Drosophila dorsal closure. We provide evidence that in both cases, actin-based contraction of the leading edge of the epithelium is of critical importance.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Köppen, Mathias","last_name":"Köppen","first_name":"Mathias"},{"first_name":"Beatriz","last_name":"Fernández","full_name":"Fernández, Beatriz"},{"last_name":"Carvalho","first_name":"Lara","full_name":"Carvalho, Lara"},{"first_name":"António","last_name":"Jacinto","full_name":"Jacinto, António"},{"last_name":"Heisenberg","first_name":"Carl-Philipp J","orcid":"0000-0002-0912-4566","id":"39427864-F248-11E8-B48F-1D18A9856A87","full_name":"Heisenberg, Carl-Philipp J"}],"citation":{"mla":"Köppen, Mathias, et al. “Misshapen Mediates Actin-Based Cell Contraction during Zebrafish Epiboly and Drosophila Dorsal Closure.” <i>Mechanisms of Development</i>, vol. 122, no. Supplement 1, Elsevier, 2005, pp. S112–13, doi:<a href=\"https://doi.org/10.1016/j.mod.2005.06.010\">10.1016/j.mod.2005.06.010</a>.","short":"M. Köppen, B. Fernández, L. Carvalho, A. Jacinto, C.-P.J. Heisenberg, Mechanisms of Development 122 (2005) S112–S113.","ieee":"M. Köppen, B. Fernández, L. Carvalho, A. Jacinto, and C.-P. J. Heisenberg, “Misshapen mediates actin-based cell contraction during zebrafish epiboly and Drosophila dorsal closure,” <i>Mechanisms of Development</i>, vol. 122, no. Supplement 1. Elsevier, pp. S112–S113, 2005.","apa":"Köppen, M., Fernández, B., Carvalho, L., Jacinto, A., &#38; Heisenberg, C.-P. J. (2005). Misshapen mediates actin-based cell contraction during zebrafish epiboly and Drosophila dorsal closure. <i>Mechanisms of Development</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.mod.2005.06.010\">https://doi.org/10.1016/j.mod.2005.06.010</a>","ama":"Köppen M, Fernández B, Carvalho L, Jacinto A, Heisenberg C-PJ. Misshapen mediates actin-based cell contraction during zebrafish epiboly and Drosophila dorsal closure. <i>Mechanisms of Development</i>. 2005;122(Supplement 1):S112-S113. doi:<a href=\"https://doi.org/10.1016/j.mod.2005.06.010\">10.1016/j.mod.2005.06.010</a>","ista":"Köppen M, Fernández B, Carvalho L, Jacinto A, Heisenberg C-PJ. 2005. Misshapen mediates actin-based cell contraction during zebrafish epiboly and Drosophila dorsal closure. Mechanisms of Development. 122(Supplement 1), S112–S113.","chicago":"Köppen, Mathias, Beatriz Fernández, Lara Carvalho, António Jacinto, and Carl-Philipp J Heisenberg. “Misshapen Mediates Actin-Based Cell Contraction during Zebrafish Epiboly and Drosophila Dorsal Closure.” <i>Mechanisms of Development</i>. Elsevier, 2005. <a href=\"https://doi.org/10.1016/j.mod.2005.06.010\">https://doi.org/10.1016/j.mod.2005.06.010</a>."},"oa_version":"None","extern":"1","date_updated":"2021-01-12T07:55:07Z","publication":"Mechanisms of Development","publist_id":"1936","intvolume":"       122","page":"S112 - S113","doi":"10.1016/j.mod.2005.06.010","year":"2005","status":"public","day":"01","acknowledgement":"Poster Abstract","_id":"4183","type":"journal_article","date_created":"2018-12-11T12:07:27Z"},{"publication":"Evolution; International Journal of Organic Evolution","publist_id":"1849","intvolume":"        59","type":"journal_article","_id":"4249","date_created":"2018-12-11T12:07:50Z","day":"01","status":"public","doi":"10.1111/j.0014-3820.2005.tb01771.x","year":"2005","page":"1194 - 1210","issue":"6","month":"06","publication_status":"published","abstract":[{"lang":"eng","text":"We examined causes of speciation in asexual populations in both sympatry and parapatry, providing an alternative explanation for the speciation patterns reported by Dieckmann and Doebeli (1999) and Doebeli and Dieckmann (2003). Both in sympatry and parapatry, they find that speciation occurs relatively easily. We reveal that in the sympatric clonal model, the equilibrium distribution is continuous and the disruptive selection driving evolution of discrete clusters is only transient. Hence, if discrete phenotypes are to remain stable in the sympatric sexual model, there should be some source of nontransient disruptive selection that will drive evolution of assortment. We analyze sexually reproducing populations using the Bulmer’s infinitesimal model and show that cost-free assortment alone leads to speciation and disruptive selection only arises when the optimal distribution cannot be matched—in this example, because the phenotypic range is limited. In addition, Doebeli and Dieckmann’s analyses assumed a high genetic variance and a high mutation rate. Thus, these theoretical models do not support the conclusion that sympatric speciation is a likely outcome of competition for resources. In their parapatric model (Doebeli and Dieckmann 2003), clustering into distinct phenotypes is driven by edge effects, rather than by frequency-dependent competition."}],"title":"Speciation through competition: A critical review","volume":59,"publisher":"Wiley-Blackwell","date_published":"2005-06-01T00:00:00Z","citation":{"ieee":"J. Polechova and N. H. Barton, “Speciation through competition: A critical review,” <i>Evolution; International Journal of Organic Evolution</i>, vol. 59, no. 6. Wiley-Blackwell, pp. 1194–1210, 2005.","apa":"Polechova, J., &#38; Barton, N. H. (2005). Speciation through competition: A critical review. <i>Evolution; International Journal of Organic Evolution</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/j.0014-3820.2005.tb01771.x\">https://doi.org/10.1111/j.0014-3820.2005.tb01771.x</a>","chicago":"Polechova, Jitka, and Nicholas H Barton. “Speciation through Competition: A Critical Review.” <i>Evolution; International Journal of Organic Evolution</i>. Wiley-Blackwell, 2005. <a href=\"https://doi.org/10.1111/j.0014-3820.2005.tb01771.x\">https://doi.org/10.1111/j.0014-3820.2005.tb01771.x</a>.","ista":"Polechova J, Barton NH. 2005. Speciation through competition: A critical review. Evolution; International Journal of Organic Evolution. 59(6), 1194–1210.","ama":"Polechova J, Barton NH. Speciation through competition: A critical review. <i>Evolution; International Journal of Organic Evolution</i>. 2005;59(6):1194-1210. doi:<a href=\"https://doi.org/10.1111/j.0014-3820.2005.tb01771.x\">10.1111/j.0014-3820.2005.tb01771.x</a>","short":"J. Polechova, N.H. Barton, Evolution; International Journal of Organic Evolution 59 (2005) 1194–1210.","mla":"Polechova, Jitka, and Nicholas H. Barton. “Speciation through Competition: A Critical Review.” <i>Evolution; International Journal of Organic Evolution</i>, vol. 59, no. 6, Wiley-Blackwell, 2005, pp. 1194–210, doi:<a href=\"https://doi.org/10.1111/j.0014-3820.2005.tb01771.x\">10.1111/j.0014-3820.2005.tb01771.x</a>."},"extern":1,"quality_controlled":0,"date_updated":"2021-01-12T07:55:36Z","author":[{"first_name":"Jitka","last_name":"Polechova","orcid":"0000-0003-0951-3112","id":"3BBFB084-F248-11E8-B48F-1D18A9856A87","full_name":"Jitka Polechova"},{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","full_name":"Nicholas Barton","last_name":"Barton","first_name":"Nicholas H","orcid":"0000-0002-8548-5240"}]},{"citation":{"apa":"Barton, N. H., &#38; Otto, S. (2005). Evolution of recombination due to random drift. <i>Genetics</i>. Genetics Society of America. <a href=\"https://doi.org/10.1534/genetics.104.032821\">https://doi.org/10.1534/genetics.104.032821</a>","ama":"Barton NH, Otto S. Evolution of recombination due to random drift. <i>Genetics</i>. 2005;169(4):2353-2370. doi:<a href=\"https://doi.org/10.1534/genetics.104.032821\">10.1534/genetics.104.032821</a>","ista":"Barton NH, Otto S. 2005. Evolution of recombination due to random drift. Genetics. 169(4), 2353–2370.","chicago":"Barton, Nicholas H, and Sarah Otto. “Evolution of Recombination Due to Random Drift.” <i>Genetics</i>. Genetics Society of America, 2005. <a href=\"https://doi.org/10.1534/genetics.104.032821\">https://doi.org/10.1534/genetics.104.032821</a>.","ieee":"N. H. Barton and S. Otto, “Evolution of recombination due to random drift,” <i>Genetics</i>, vol. 169, no. 4. Genetics Society of America, pp. 2353–2370, 2005.","mla":"Barton, Nicholas H., and Sarah Otto. “Evolution of Recombination Due to Random Drift.” <i>Genetics</i>, vol. 169, no. 4, Genetics Society of America, 2005, pp. 2353–70, doi:<a href=\"https://doi.org/10.1534/genetics.104.032821\">10.1534/genetics.104.032821</a>.","short":"N.H. Barton, S. Otto, Genetics 169 (2005) 2353–2370."},"quality_controlled":0,"extern":1,"date_updated":"2021-01-12T07:55:37Z","author":[{"full_name":"Nicholas Barton","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8548-5240","last_name":"Barton","first_name":"Nicholas H"},{"last_name":"Otto","first_name":"Sarah","full_name":"Otto, Sarah P"}],"issue":"4","publication_status":"published","month":"03","abstract":[{"text":"In finite populations subject to selection, genetic drift generates negative linkage disequilibrium, on average, even if selection acts independently (i.e. multiplicatively) upon all loci. Negative disequilibrium reduces the variance in fitness and hence, by FISHER's Fundamental Theorem (1930), slows the rate of increase in mean fitness. Modifiers that increase recombination eliminate the negative disequilibria that impede selection and consequently increase in frequency by 'hitch-hiking'. In addition, recombinant progeny are more fit on average than non-recombinant progeny when there is negative linkage disequilibrium and loci interact multiplicatively. For both these reasons, stochastic fluctuations in linkage disequilibrium in finite populations favor the evolution of increased rates of recombination, even in the absence of epistatic interactions among loci and even when disequilibrium is initially absent. The method developed within this paper quantifies the strength of selection on a modifier allele that increases recombination due to stochastically generated linkage disequilibria. The analysis indicates that, in a population subject to multiplicative selection, genetic associations generated by drift do select for increased recombination, a result that is confirmed by Monte Carlo simulations. Selection for a modifier that increases recombination is highest when linkage among all loci is tight, when beneficial alleles rise from low to high frequency, and when the population size is small.","lang":"eng"}],"volume":169,"title":"Evolution of recombination due to random drift","date_published":"2005-03-01T00:00:00Z","publisher":"Genetics Society of America","type":"journal_article","_id":"4251","date_created":"2018-12-11T12:07:51Z","status":"public","day":"01","doi":"10.1534/genetics.104.032821","year":"2005","page":"2353 - 2370","publication":"Genetics","publist_id":"1846","intvolume":"       169"},{"intvolume":"       360","publist_id":"1847","publication":"Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences","page":"1411 - 1425","doi":"10.1098/rstb.2005.1667","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1569515/","open_access":"1"}],"day":"29","status":"public","year":"2005","oa":1,"date_created":"2018-12-11T12:07:51Z","type":"journal_article","_id":"4252","date_published":"2005-07-29T00:00:00Z","publisher":"Royal Society, The","volume":360,"title":"Theoretical models of selection and mutationon quantitative traits","abstract":[{"lang":"eng","text":"Empirical studies of quantitative genetic variation have revealed robust patterns that are observed both across traits and across species. However, these patterns have no compelling explanation, and some of the observations even appear to be mutually incompatible. We review and extend a major class of theoretical models, ‘mutation–selection models’, that have been proposed to explain quantitative genetic variation. We also briefly review an alternative class of ‘balancing selection models’. We consider to what extent the models are compatible with the general observations, and argue that a key issue is understanding and modelling pleiotropy. We discuss some"}],"month":"07","publication_status":"published","issue":"1459","author":[{"last_name":"Johnson","first_name":"Toby","full_name":"Johnson, Toby"},{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","full_name":"Nicholas Barton","first_name":"Nicholas H","last_name":"Barton","orcid":"0000-0002-8548-5240"}],"date_updated":"2021-01-12T07:55:38Z","quality_controlled":0,"extern":1,"citation":{"ama":"Johnson T, Barton NH. Theoretical models of selection and mutationon quantitative traits. <i>Philosophical Transactions of the Royal Society of London Series B, Biological Sciences</i>. 2005;360(1459):1411-1425. doi:<a href=\"https://doi.org/10.1098/rstb.2005.1667\">10.1098/rstb.2005.1667</a>","chicago":"Johnson, Toby, and Nicholas H Barton. “Theoretical Models of Selection and Mutationon Quantitative Traits.” <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>. Royal Society, The, 2005. <a href=\"https://doi.org/10.1098/rstb.2005.1667\">https://doi.org/10.1098/rstb.2005.1667</a>.","ista":"Johnson T, Barton NH. 2005. Theoretical models of selection and mutationon quantitative traits. Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences. 360(1459), 1411–1425.","apa":"Johnson, T., &#38; Barton, N. H. (2005). Theoretical models of selection and mutationon quantitative traits. <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>. Royal Society, The. <a href=\"https://doi.org/10.1098/rstb.2005.1667\">https://doi.org/10.1098/rstb.2005.1667</a>","ieee":"T. Johnson and N. H. Barton, “Theoretical models of selection and mutationon quantitative traits,” <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>, vol. 360, no. 1459. Royal Society, The, pp. 1411–1425, 2005.","short":"T. Johnson, N.H. Barton, Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences 360 (2005) 1411–1425.","mla":"Johnson, Toby, and Nicholas H. Barton. “Theoretical Models of Selection and Mutationon Quantitative Traits.” <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>, vol. 360, no. 1459, Royal Society, The, 2005, pp. 1411–25, doi:<a href=\"https://doi.org/10.1098/rstb.2005.1667\">10.1098/rstb.2005.1667</a>."}},{"citation":{"mla":"Podelski, Andreas, and Thomas Wies. <i>Boolean Heaps</i>. Springer, 2005, pp. 267–82, doi:<a href=\"https://doi.org/1550\">1550</a>.","short":"A. Podelski, T. Wies, in:, Springer, 2005, pp. 267–282.","ama":"Podelski A, Wies T. Boolean Heaps. In: Springer; 2005:267-282. doi:<a href=\"https://doi.org/1550\">1550</a>","chicago":"Podelski, Andreas, and Thomas Wies. “Boolean Heaps,” 267–82. Springer, 2005. <a href=\"https://doi.org/1550\">https://doi.org/1550</a>.","ista":"Podelski A, Wies T. 2005. Boolean Heaps. SAS: Static Analysis Symposium, LNCS 3672, , 267–282.","apa":"Podelski, A., &#38; Wies, T. (2005). Boolean Heaps (pp. 267–282). Presented at the SAS: Static Analysis Symposium, Springer. <a href=\"https://doi.org/1550\">https://doi.org/1550</a>","ieee":"A. Podelski and T. Wies, “Boolean Heaps,” presented at the SAS: Static Analysis Symposium, 2005, pp. 267–282."},"quality_controlled":0,"extern":1,"date_updated":"2021-01-12T07:56:27Z","alternative_title":["LNCS 3672"],"author":[{"first_name":"Andreas","last_name":"Podelski","full_name":"Podelski,Andreas"},{"last_name":"Wies","first_name":"Thomas","full_name":"Thomas Wies","id":"447BFB88-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","month":"01","title":"Boolean Heaps","date_published":"2005-01-01T00:00:00Z","publisher":"Springer","_id":"4367","type":"conference","date_created":"2018-12-11T12:08:29Z","page":"267 - 282","status":"public","doi":"1550","year":"2005","day":"01","conference":{"name":"SAS: Static Analysis Symposium"},"publist_id":"1092"},{"conference":{"name":"POPL: Principles of Programming Languages"},"publist_id":"1053","date_created":"2018-12-11T12:08:41Z","type":"conference","_id":"4404","status":"public","day":"01","doi":"1542","year":"2005","page":"98 - 109","month":"01","publication_status":"published","publisher":"ACM","date_published":"2005-01-01T00:00:00Z","title":"Synthesis of interface specifications for Java classes","extern":1,"quality_controlled":0,"date_updated":"2021-01-12T07:56:44Z","citation":{"ieee":"R. Alur, P. Cerny, P. Madhusudan, and W. Nam, “Synthesis of interface specifications for Java classes,” presented at the POPL: Principles of Programming Languages, 2005, pp. 98–109.","chicago":"Alur, Rajeev, Pavol Cerny, P. Madhusudan, and Wonhong Nam. “Synthesis of Interface Specifications for Java Classes,” 98–109. ACM, 2005. <a href=\"https://doi.org/1542\">https://doi.org/1542</a>.","ista":"Alur R, Cerny P, Madhusudan P, Nam W. 2005. Synthesis of interface specifications for Java classes. POPL: Principles of Programming Languages, 98–109.","ama":"Alur R, Cerny P, Madhusudan P, Nam W. Synthesis of interface specifications for Java classes. In: ACM; 2005:98-109. doi:<a href=\"https://doi.org/1542\">1542</a>","apa":"Alur, R., Cerny, P., Madhusudan, P., &#38; Nam, W. (2005). Synthesis of interface specifications for Java classes (pp. 98–109). Presented at the POPL: Principles of Programming Languages, ACM. <a href=\"https://doi.org/1542\">https://doi.org/1542</a>","short":"R. Alur, P. Cerny, P. Madhusudan, W. Nam, in:, ACM, 2005, pp. 98–109.","mla":"Alur, Rajeev, et al. <i>Synthesis of Interface Specifications for Java Classes</i>. ACM, 2005, pp. 98–109, doi:<a href=\"https://doi.org/1542\">1542</a>."},"author":[{"full_name":"Alur, Rajeev","first_name":"Rajeev","last_name":"Alur"},{"first_name":"Pavol","last_name":"Cerny","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","full_name":"Pavol Cerny"},{"first_name":"P.","last_name":"Madhusudan","full_name":"Madhusudan,P."},{"full_name":"Nam,Wonhong","last_name":"Nam","first_name":"Wonhong"}]},{"month":"01","publication_status":"published","abstract":[{"text":"The periodic resource model for hierarchical, compositional scheduling abstracts task groups by resource requirements. We study this model in the presence of dataflow constraints between the tasks within a group (intragroup dependencies), and between tasks in different groups (inter-group dependencies). We consider two natural semantics for dataflow constraints, namely, RTW (real-time workshop) semantics and LET (logical execution time) semantics. We show that while RTW semantics offers better end-to-end latency on the task group level, LET semantics allows tighter resource bounds in the abstraction hierarchy and therefore provides better composability properties. This result holds both for intragroup and intergroup dependencies, as well as for shared and for distributed resources.","lang":"eng"}],"date_published":"2005-01-01T00:00:00Z","publisher":"IEEE","title":"Trading end-to-end latency for composability","extern":1,"quality_controlled":0,"date_updated":"2021-01-12T07:56:47Z","citation":{"ista":"Matic S, Henzinger TA. 2005. Trading end-to-end latency for composability. RTSS: Real-Time Systems Symposium, 99–110.","chicago":"Matic, Slobodan, and Thomas A Henzinger. “Trading End-to-End Latency for Composability,” 99–110. IEEE, 2005. <a href=\"https://doi.org/10.1109/RTSS.2005.43\">https://doi.org/10.1109/RTSS.2005.43</a>.","ama":"Matic S, Henzinger TA. Trading end-to-end latency for composability. In: IEEE; 2005:99-110. doi:<a href=\"https://doi.org/10.1109/RTSS.2005.43\">10.1109/RTSS.2005.43</a>","apa":"Matic, S., &#38; Henzinger, T. A. (2005). Trading end-to-end latency for composability (pp. 99–110). Presented at the RTSS: Real-Time Systems Symposium, IEEE. <a href=\"https://doi.org/10.1109/RTSS.2005.43\">https://doi.org/10.1109/RTSS.2005.43</a>","ieee":"S. Matic and T. A. Henzinger, “Trading end-to-end latency for composability,” presented at the RTSS: Real-Time Systems Symposium, 2005, pp. 99–110.","short":"S. Matic, T.A. Henzinger, in:, IEEE, 2005, pp. 99–110.","mla":"Matic, Slobodan, and Thomas A. Henzinger. <i>Trading End-to-End Latency for Composability</i>. IEEE, 2005, pp. 99–110, doi:<a href=\"https://doi.org/10.1109/RTSS.2005.43\">10.1109/RTSS.2005.43</a>."},"author":[{"last_name":"Matic","first_name":"Slobodan","full_name":"Matic, Slobodan"},{"full_name":"Thomas Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"}],"publist_id":"317","conference":{"name":"RTSS: Real-Time Systems Symposium"},"date_created":"2018-12-11T12:08:43Z","_id":"4412","type":"conference","page":"99 - 110","doi":"10.1109/RTSS.2005.43","status":"public","year":"2005","day":"01"},{"publist_id":"311","conference":{"name":"VEE: Virtual Execution Environments"},"date_created":"2018-12-11T12:08:45Z","_id":"4418","type":"conference","year":"2005","status":"public","day":"01","page":"35 - 45","doi":"10.1145/1064979.1064986","month":"01","publication_status":"published","abstract":[{"lang":"eng","text":"We present a new software system architecture for the implementation of hard real-time applications. The core of the system is a microkernel whose reactivity (interrupt handling as in synchronous reactive programs) and proactivity (task scheduling as in traditional RTOSs) are fully programmable. The microkernel, which we implemented on a StrongARM processor, consists of two interacting domain-specific virtual machines, a reactive E (Embedded) machine and a proactive S (Scheduling) machine. The microkernel code (or microcode) that runs on the microkernel is partitioned into E and S code. E code manages the interaction of the system with the physical environment: the execution of E code is triggered by environment interrupts, which signal external events such as the arrival of a message or sensor value, and it releases application tasks to the S machine. S code manages the interaction of the system with the processor: the execution of S code is triggered by hardware interrupts, which signal internal events such as the completion of a task or time slice, and it dispatches application tasks to the CPU, possibly preempting a running task. This partition of the system orthogonalizes the two main concerns of real-time implementations: E code refers to environment time and thus defines the reactivity of the system in a hardware- and scheduler-independent fashion; S code refers to CPU time and defines a system scheduler. If both time lines can be reconciled, then the code is called time safe; violations of time safety are handled again in a programmable way, by run-time exceptions. The separation of E from S code permits the independent programming, verification, optimization, composition, dynamic adaptation, and reuse of both reaction and scheduling mechanisms. Our measurements show that the system overhead is very acceptable even for large sets of task, generally in the 0.2--0.3% range."}],"date_published":"2005-01-01T00:00:00Z","publisher":"ACM","title":"A programmable microkernel for real-time systems","extern":1,"quality_controlled":0,"date_updated":"2021-01-12T07:56:49Z","citation":{"ista":"Kirsch C, Sanvido M, Henzinger TA. 2005. A programmable microkernel for real-time systems. VEE: Virtual Execution Environments, 35–45.","ama":"Kirsch C, Sanvido M, Henzinger TA. A programmable microkernel for real-time systems. In: ACM; 2005:35-45. doi:<a href=\"https://doi.org/10.1145/1064979.1064986\">10.1145/1064979.1064986</a>","chicago":"Kirsch, Christoph, Marco Sanvido, and Thomas A Henzinger. “A Programmable Microkernel for Real-Time Systems,” 35–45. ACM, 2005. <a href=\"https://doi.org/10.1145/1064979.1064986\">https://doi.org/10.1145/1064979.1064986</a>.","apa":"Kirsch, C., Sanvido, M., &#38; Henzinger, T. A. (2005). A programmable microkernel for real-time systems (pp. 35–45). Presented at the VEE: Virtual Execution Environments, ACM. <a href=\"https://doi.org/10.1145/1064979.1064986\">https://doi.org/10.1145/1064979.1064986</a>","ieee":"C. Kirsch, M. Sanvido, and T. A. Henzinger, “A programmable microkernel for real-time systems,” presented at the VEE: Virtual Execution Environments, 2005, pp. 35–45.","mla":"Kirsch, Christoph, et al. <i>A Programmable Microkernel for Real-Time Systems</i>. ACM, 2005, pp. 35–45, doi:<a href=\"https://doi.org/10.1145/1064979.1064986\">10.1145/1064979.1064986</a>.","short":"C. Kirsch, M. Sanvido, T.A. Henzinger, in:, ACM, 2005, pp. 35–45."},"author":[{"first_name":"Christoph","last_name":"Kirsch","full_name":"Kirsch, Christoph M"},{"first_name":"Marco","last_name":"Sanvido","full_name":"Sanvido, Marco A"},{"orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","full_name":"Thomas Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}]},{"month":"01","publication_status":"published","abstract":[{"lang":"eng","text":"We define five increasingly comprehensive classes of infinite-state systems, called STS1--STS5, whose state spaces have finitary structure. For four of these classes, we provide examples from hybrid systems.STS1 These are the systems with finite bisimilarity quotients. They can be analyzed symbolically by iteratively applying predecessor and Boolean operations on state sets, starting from a finite number of observable state sets. Any such iteration is guaranteed to terminate in that only a finite number of state sets can be generated. This enables model checking of the μ-calculus.STS2 These are the systems with finite similarity quotients. They can be analyzed symbolically by iterating the predecessor and positive Boolean operations. This enables model checking of the existential and universal fragments of the μ-calculus.STS3 These are the systems with finite trace-equivalence quotients. They can be analyzed symbolically by iterating the predecessor operation and a restricted form of positive Boolean operations (intersection is restricted to intersection with observables). This enables model checking of all ω-regular properties, including linear temporal logic.STS4 These are the systems with finite distance-equivalence quotients (two states are equivalent if for every distance d, the same observables can be reached in d transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new state sets are generated. This enables model checking of the existential conjunction-free and universal disjunction-free fragments of the μ-calculus.STS5 These are the systems with finite bounded-reachability quotients (two states are equivalent if for every distance d, the same observables can be reached in d or fewer transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new states are encountered (this is a weaker termination condition than above). This enables model checking of reachability properties."}],"issue":"1","date_published":"2005-01-01T00:00:00Z","publisher":"ACM","title":"A classification of symbolic transition systems","volume":6,"quality_controlled":0,"extern":1,"date_updated":"2021-01-12T07:57:05Z","citation":{"ieee":"T. A. Henzinger, R. Majumdar, and J. Raskin, “A classification of symbolic transition systems,” <i>ACM Transactions on Computational Logic (TOCL)</i>, vol. 6, no. 1. ACM, pp. 1–32, 2005.","apa":"Henzinger, T. A., Majumdar, R., &#38; Raskin, J. (2005). A classification of symbolic transition systems. <i>ACM Transactions on Computational Logic (TOCL)</i>. ACM. <a href=\"https://doi.org/10.1145/1042038.1042039\">https://doi.org/10.1145/1042038.1042039</a>","chicago":"Henzinger, Thomas A, Ritankar Majumdar, and Jean Raskin. “A Classification of Symbolic Transition Systems.” <i>ACM Transactions on Computational Logic (TOCL)</i>. ACM, 2005. <a href=\"https://doi.org/10.1145/1042038.1042039\">https://doi.org/10.1145/1042038.1042039</a>.","ama":"Henzinger TA, Majumdar R, Raskin J. A classification of symbolic transition systems. <i>ACM Transactions on Computational Logic (TOCL)</i>. 2005;6(1):1-32. doi:<a href=\"https://doi.org/10.1145/1042038.1042039\">10.1145/1042038.1042039</a>","ista":"Henzinger TA, Majumdar R, Raskin J. 2005. A classification of symbolic transition systems. ACM Transactions on Computational Logic (TOCL). 6(1), 1–32.","mla":"Henzinger, Thomas A., et al. “A Classification of Symbolic Transition Systems.” <i>ACM Transactions on Computational Logic (TOCL)</i>, vol. 6, no. 1, ACM, 2005, pp. 1–32, doi:<a href=\"https://doi.org/10.1145/1042038.1042039\">10.1145/1042038.1042039</a>.","short":"T.A. Henzinger, R. Majumdar, J. Raskin, ACM Transactions on Computational Logic (TOCL) 6 (2005) 1–32."},"author":[{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Thomas Henzinger"},{"full_name":"Majumdar, Ritankar S","last_name":"Majumdar","first_name":"Ritankar"},{"full_name":"Raskin, Jean-François","last_name":"Raskin","first_name":"Jean"}],"publist_id":"272","intvolume":"         6","publication":"ACM Transactions on Computational Logic (TOCL)","date_created":"2018-12-11T12:08:56Z","_id":"4454","type":"journal_article","page":"1 - 32","doi":"10.1145/1042038.1042039","day":"01","status":"public","year":"2005"},{"month":"12","publication_status":"published","abstract":[{"text":"We define quantitative similarity functions between timed transition systems that measure the degree of closeness of two systems as a real, in contrast to the traditional boolean yes/no approach to timed simulation and language inclusion. Two systems are close if for each timed trace of one system, there exists a corresponding timed trace in the other system with the same sequence of events and closely corresponding event timings. We show that timed CTL is robust with respect to our quantitative version of bisimilarity, in particular, if a system satisfies a formula, then every close system satisfies a close formula. We also define a discounted version of CTL over timed systems, which assigns to every CTL formula a real value that is obtained by discounting real time. We prove the robustness of discounted CTL by establishing that close states in the bisimilarity metric have close values for all discounted CTL formulas.","lang":"eng"}],"title":"Quantifying similarities between timed systems","volume":3829,"publisher":"Springer","date_published":"2005-12-13T00:00:00Z","citation":{"mla":"Henzinger, Thomas A., et al. <i>Quantifying Similarities between Timed Systems</i>. Vol. 3829, Springer, 2005, pp. 226–41, doi:<a href=\"https://doi.org/10.1007/11603009_18\">10.1007/11603009_18</a>.","short":"T.A. Henzinger, R. Majumdar, V. Prabhu, in:, Springer, 2005, pp. 226–241.","ieee":"T. A. Henzinger, R. Majumdar, and V. Prabhu, “Quantifying similarities between timed systems,” presented at the FORMATS: Formal Modeling and Analysis of Timed Systems, 2005, vol. 3829, pp. 226–241.","apa":"Henzinger, T. A., Majumdar, R., &#38; Prabhu, V. (2005). Quantifying similarities between timed systems (Vol. 3829, pp. 226–241). Presented at the FORMATS: Formal Modeling and Analysis of Timed Systems, Springer. <a href=\"https://doi.org/10.1007/11603009_18\">https://doi.org/10.1007/11603009_18</a>","ama":"Henzinger TA, Majumdar R, Prabhu V. Quantifying similarities between timed systems. In: Vol 3829. Springer; 2005:226-241. doi:<a href=\"https://doi.org/10.1007/11603009_18\">10.1007/11603009_18</a>","ista":"Henzinger TA, Majumdar R, Prabhu V. 2005. Quantifying similarities between timed systems. FORMATS: Formal Modeling and Analysis of Timed Systems, LNCS, vol. 3829, 226–241.","chicago":"Henzinger, Thomas A, Ritankar Majumdar, and Vinayak Prabhu. “Quantifying Similarities between Timed Systems,” 3829:226–41. Springer, 2005. <a href=\"https://doi.org/10.1007/11603009_18\">https://doi.org/10.1007/11603009_18</a>."},"quality_controlled":0,"extern":1,"date_updated":"2021-01-12T07:57:05Z","alternative_title":["LNCS"],"author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Thomas Henzinger","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"},{"full_name":"Majumdar, Ritankar S","first_name":"Ritankar","last_name":"Majumdar"},{"full_name":"Prabhu, Vinayak S","last_name":"Prabhu","first_name":"Vinayak"}],"conference":{"name":"FORMATS: Formal Modeling and Analysis of Timed Systems"},"publist_id":"273","intvolume":"      3829","type":"conference","_id":"4455","date_created":"2018-12-11T12:08:56Z","page":"226 - 241","day":"13","year":"2005","status":"public","doi":"10.1007/11603009_18","acknowledgement":"This research was supported in part by the AFOSR MURI grant F49620-00-1-0327 and the NSF grants CCR-0208875, CCR-0225610, and CCR-0427202."},{"publist_id":"274","conference":{"name":"FSE: Foundations of Software Engineering"},"date_created":"2018-12-11T12:08:56Z","type":"conference","_id":"4456","status":"public","doi":"10.1145/1081706.1081713","page":"31 - 40","day":"01","year":"2005","month":"09","publication_status":"published","abstract":[{"lang":"eng","text":"A modular program analysis considers components independently and provides a succinct summary for each component, which is used when checking the rest of the system. Consider a system consisting of a library and a client. A temporal summary, or interface, of the library specifies legal sequences of library calls. The interface is safe if no call sequence violates the library's internal invariants; the interface is permissive if it contains every such sequence. Modular program analysis requires full interfaces, which are both safe and permissive: the client does not cause errors in the library if and only if it makes only sequences of library calls that are allowed by the full interface of the library.Previous interface-based methods have focused on safe interfaces, which may be too restrictive and thus reject good clients. We present an algorithm for automatically synthesizing software interfaces that are both safe and permissive. The algorithm generates interfaces as graphs whose vertices are labeled with predicates over the library's internal state, and whose edges are labeled with library calls. The interface state is refined incrementally until the full interface is constructed. In other words, the algorithm automatically synthesizes a typestate system for the library, against which any client can be checked for compatibility. We present an implementation of the algorithm which is based on the BLAST model checker, and we evaluate some case studies."}],"publisher":"ACM","date_published":"2005-09-01T00:00:00Z","title":"Permissive interfaces","quality_controlled":0,"extern":1,"date_updated":"2021-01-12T07:57:06Z","citation":{"short":"T.A. Henzinger, R. Jhala, R. Majumdar, in:, ACM, 2005, pp. 31–40.","mla":"Henzinger, Thomas A., et al. <i>Permissive Interfaces</i>. ACM, 2005, pp. 31–40, doi:<a href=\"https://doi.org/10.1145/1081706.1081713\">10.1145/1081706.1081713</a>.","ieee":"T. A. Henzinger, R. Jhala, and R. Majumdar, “Permissive interfaces,” presented at the FSE: Foundations of Software Engineering, 2005, pp. 31–40.","apa":"Henzinger, T. A., Jhala, R., &#38; Majumdar, R. (2005). Permissive interfaces (pp. 31–40). Presented at the FSE: Foundations of Software Engineering, ACM. <a href=\"https://doi.org/10.1145/1081706.1081713\">https://doi.org/10.1145/1081706.1081713</a>","chicago":"Henzinger, Thomas A, Ranjit Jhala, and Ritankar Majumdar. “Permissive Interfaces,” 31–40. ACM, 2005. <a href=\"https://doi.org/10.1145/1081706.1081713\">https://doi.org/10.1145/1081706.1081713</a>.","ama":"Henzinger TA, Jhala R, Majumdar R. Permissive interfaces. In: ACM; 2005:31-40. doi:<a href=\"https://doi.org/10.1145/1081706.1081713\">10.1145/1081706.1081713</a>","ista":"Henzinger TA, Jhala R, Majumdar R. 2005. Permissive interfaces. FSE: Foundations of Software Engineering, 31–40."},"author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Thomas Henzinger","last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724"},{"first_name":"Ranjit","last_name":"Jhala","full_name":"Jhala, Ranjit"},{"first_name":"Ritankar","last_name":"Majumdar","full_name":"Majumdar, Ritankar S"}]},{"citation":{"mla":"Henzinger, Thomas A., et al. <i>Composable Code Generation for Distributed Giotto</i>. ACM, 2005, pp. 21–30, doi:<a href=\"https://doi.org/10.1145/1065910.1065914\">10.1145/1065910.1065914</a>.","short":"T.A. Henzinger, C. Kirsch, S. Matic, in:, ACM, 2005, pp. 21–30.","ieee":"T. A. Henzinger, C. Kirsch, and S. Matic, “Composable code generation for distributed Giotto,” presented at the LCTES: Languages, Compilers, and Tools for Embedded Systems, 2005, pp. 21–30.","ista":"Henzinger TA, Kirsch C, Matic S. 2005. Composable code generation for distributed Giotto. LCTES: Languages, Compilers, and Tools for Embedded Systems, 21–30.","chicago":"Henzinger, Thomas A, Christoph Kirsch, and Slobodan Matic. “Composable Code Generation for Distributed Giotto,” 21–30. ACM, 2005. <a href=\"https://doi.org/10.1145/1065910.1065914\">https://doi.org/10.1145/1065910.1065914</a>.","ama":"Henzinger TA, Kirsch C, Matic S. Composable code generation for distributed Giotto. In: ACM; 2005:21-30. doi:<a href=\"https://doi.org/10.1145/1065910.1065914\">10.1145/1065910.1065914</a>","apa":"Henzinger, T. A., Kirsch, C., &#38; Matic, S. (2005). Composable code generation for distributed Giotto (pp. 21–30). Presented at the LCTES: Languages, Compilers, and Tools for Embedded Systems, ACM. <a href=\"https://doi.org/10.1145/1065910.1065914\">https://doi.org/10.1145/1065910.1065914</a>"},"quality_controlled":0,"extern":1,"date_updated":"2021-01-12T07:57:06Z","author":[{"orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger","full_name":"Thomas Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Christoph","last_name":"Kirsch","full_name":"Kirsch, Christoph M"},{"full_name":"Matic, Slobodan","first_name":"Slobodan","last_name":"Matic"}],"month":"06","publication_status":"published","abstract":[{"lang":"eng","text":"We present a compositional approach to the implementation of hard real-time software running on a distributed platform. We explain how several code suppliers, coordinated by a system integrator, can independently generate different parts of the distributed software. The task structure, interaction, and timing is specified as a Giotto program. Each supplier is given a part of the Giotto program and a timing interface, from which the supplier generates task and scheduling code. The integrator then checks, individually for each supplier, in pseudo-polynomial time, if the supplied code meets its timing specification. If all checks succeed, then the supplied software parts are guaranteed to work together and implement the original Giotto program. The feasibility of the approach is demonstrated by a prototype implementation."}],"title":"Composable code generation for distributed Giotto","publisher":"ACM","date_published":"2005-06-01T00:00:00Z","_id":"4457","type":"conference","date_created":"2018-12-11T12:08:57Z","page":"21 - 30","year":"2005","doi":"10.1145/1065910.1065914","day":"01","status":"public","publist_id":"275","conference":{"name":"LCTES: Languages, Compilers, and Tools for Embedded Systems"}},{"date_created":"2018-12-11T12:09:22Z","_id":"4536","type":"conference","acknowledgement":"Supported in part by the AFOSR MURI grant F49620-00-1-0327 and the NSF grants CCR-0208875 and CCR-0225610.","year":"2005","page":"144 - 161","doi":"DOI: 10.1007/11603009_13","day":"13","status":"public","publist_id":"190","conference":{"name":"FORMATS: Formal Modeling and Analysis of Timed Systems"},"intvolume":"      3829","extern":1,"quality_controlled":0,"date_updated":"2021-01-12T07:59:31Z","citation":{"short":"L. Doyen, T.A. Henzinger, J. Raskin, in:, Springer, 2005, pp. 144–161.","mla":"Doyen, Laurent, et al. <i>Automatic Rectangular Refinement of Affine Hybrid Systems</i>. Vol. 3829, Springer, 2005, pp. 144–61, doi:<a href=\"https://doi.org/DOI: 10.1007/11603009_13\">DOI: 10.1007/11603009_13</a>.","ama":"Doyen L, Henzinger TA, Raskin J. Automatic rectangular refinement of affine hybrid systems. In: Vol 3829. Springer; 2005:144-161. doi:<a href=\"https://doi.org/DOI: 10.1007/11603009_13\">DOI: 10.1007/11603009_13</a>","ista":"Doyen L, Henzinger TA, Raskin J. 2005. Automatic rectangular refinement of affine hybrid systems. FORMATS: Formal Modeling and Analysis of Timed Systems, LNCS, vol. 3829, 144–161.","chicago":"Doyen, Laurent, Thomas A Henzinger, and Jean Raskin. “Automatic Rectangular Refinement of Affine Hybrid Systems,” 3829:144–61. Springer, 2005. <a href=\"https://doi.org/DOI: 10.1007/11603009_13\">https://doi.org/DOI: 10.1007/11603009_13</a>.","apa":"Doyen, L., Henzinger, T. A., &#38; Raskin, J. (2005). Automatic rectangular refinement of affine hybrid systems (Vol. 3829, pp. 144–161). Presented at the FORMATS: Formal Modeling and Analysis of Timed Systems, Springer. <a href=\"https://doi.org/DOI: 10.1007/11603009_13\">https://doi.org/DOI: 10.1007/11603009_13</a>","ieee":"L. Doyen, T. A. Henzinger, and J. Raskin, “Automatic rectangular refinement of affine hybrid systems,” presented at the FORMATS: Formal Modeling and Analysis of Timed Systems, 2005, vol. 3829, pp. 144–161."},"author":[{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"},{"first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Thomas Henzinger"},{"first_name":"Jean","last_name":"Raskin","full_name":"Raskin, Jean-François"}],"alternative_title":["LNCS"],"publication_status":"published","month":"12","abstract":[{"lang":"eng","text":"We show how to automatically construct and refine rectangular abstractions of systems of linear differential equations. From a hybrid automaton whose dynamics are given by a system of linear differential equations, our method computes automatically a sequence of rectangular hybrid automata that are increasingly precise overapproximations of the original hybrid automaton. We prove an optimality criterion for successive refinements. We also show that this method can take into account a safety property to be verified, refining only relevant parts of the state space. The practicability of the method is illustrated on a benchmark case study. "}],"publisher":"Springer","date_published":"2005-12-13T00:00:00Z","title":"Automatic rectangular refinement of affine hybrid systems","volume":3829},{"doi":"10.1007/11590156_1","page":"1 - 18","day":"07","status":"public","year":"2005","date_created":"2018-12-11T12:09:23Z","_id":"4541","type":"conference","intvolume":"      3821","publist_id":"182","conference":{"name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science"},"author":[{"full_name":"Krishnendu Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Thomas Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"}],"alternative_title":["LNCS"],"date_updated":"2021-01-12T07:59:34Z","quality_controlled":0,"extern":1,"citation":{"mla":"Chatterjee, Krishnendu, and Thomas A. Henzinger. <i>Semiperfect-Information Games</i>. Vol. 3821, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2005, pp. 1–18, doi:<a href=\"https://doi.org/10.1007/11590156_1\">10.1007/11590156_1</a>.","short":"K. Chatterjee, T.A. Henzinger, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2005, pp. 1–18.","chicago":"Chatterjee, Krishnendu, and Thomas A Henzinger. “Semiperfect-Information Games,” 3821:1–18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2005. <a href=\"https://doi.org/10.1007/11590156_1\">https://doi.org/10.1007/11590156_1</a>.","ista":"Chatterjee K, Henzinger TA. 2005. Semiperfect-information games. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LNCS, vol. 3821, 1–18.","ama":"Chatterjee K, Henzinger TA. Semiperfect-information games. In: Vol 3821. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2005:1-18. doi:<a href=\"https://doi.org/10.1007/11590156_1\">10.1007/11590156_1</a>","apa":"Chatterjee, K., &#38; Henzinger, T. A. (2005). Semiperfect-information games (Vol. 3821, pp. 1–18). Presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.1007/11590156_1\">https://doi.org/10.1007/11590156_1</a>","ieee":"K. Chatterjee and T. A. Henzinger, “Semiperfect-information games,” presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, 2005, vol. 3821, pp. 1–18."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2005-12-07T00:00:00Z","volume":3821,"title":"Semiperfect-information games","abstract":[{"lang":"eng","text":"Much recent research has focused on the applications of games with ω-regular objectives in the control and verification of reactive systems. However, many of the game-based models are ill-suited for these applications, because they assume that each player has complete information about the state of the system (they are “perfect-information” games). This is because in many situations, a controller does not see the private state of the plant. Such scenarios are naturally modeled by “partial-information” games. On the other hand, these games are intractable; for example, partial-information games with simple reachability objectives are 2EXPTIME-complete.\nWe study the intermediate case of “semiperfect-information” games, where one player has complete knowledge of the state, while the other player has only partial knowledge. This model is appropriate in control situations where a controller must cope with plant behavior that is as adversarial as possible, i.e., the controller has partial information while the plant has perfect information. As is customary, we assume that the controller and plant take turns to make moves. We show that these semiperfect-information turn-based games are equivalent to perfect-information concurrent games, where the two players choose their moves simultaneously and independently. Since the perfect-information concurrent games are well-understood, we obtain several results of how semiperfect-information turn-based games differ from perfect-information turn-based games on one hand, and from partial-information turn-based games on the other hand. In particular, semiperfect-information turn-based games can benefit from randomized strategies while the perfect-information variety cannot, and semiperfect-information turn-based games are in NP ∩ coNP for all parity objectives.\n"}],"month":"12","publication_status":"published"},{"title":"The complexity of stochastic Rabin and Streett games","volume":3580,"publisher":"Springer","date_published":"2005-06-24T00:00:00Z","abstract":[{"lang":"eng","text":"The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We show that for Rabin winning conditions, both problems are in NP. As these problems were known to be NP-hard, it follows that they are NP-complete for Rabin conditions, and dually, coNP-complete for Streett conditions. The proof proceeds by showing that pure memoryless strategies suffice for qualitatively and quantitatively winning stochastic graph games with Rabin conditions. This insight is of interest in its own right, as it implies that controllers for Rabin objectives have simple implementations. We also prove that for every ω-regular condition, optimal winning strategies are no more complex than almost-sure winning strategies."}],"month":"06","publication_status":"published","alternative_title":["LNCS"],"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Krishnendu Chatterjee"},{"full_name":"de Alfaro, Luca","first_name":"Luca","last_name":"De Alfaro"},{"orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger","full_name":"Thomas Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"citation":{"ista":"Chatterjee K, De Alfaro L, Henzinger TA. 2005. The complexity of stochastic Rabin and Streett games. ICALP: Automata, Languages and Programming, LNCS, vol. 3580, 878–890.","chicago":"Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “The Complexity of Stochastic Rabin and Streett Games,” 3580:878–90. Springer, 2005. <a href=\"https://doi.org/10.1007/11523468_71\">https://doi.org/10.1007/11523468_71</a>.","ama":"Chatterjee K, De Alfaro L, Henzinger TA. The complexity of stochastic Rabin and Streett games. In: Vol 3580. Springer; 2005:878-890. doi:<a href=\"https://doi.org/10.1007/11523468_71\">10.1007/11523468_71</a>","apa":"Chatterjee, K., De Alfaro, L., &#38; Henzinger, T. A. (2005). The complexity of stochastic Rabin and Streett games (Vol. 3580, pp. 878–890). Presented at the ICALP: Automata, Languages and Programming, Springer. <a href=\"https://doi.org/10.1007/11523468_71\">https://doi.org/10.1007/11523468_71</a>","ieee":"K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “The complexity of stochastic Rabin and Streett games,” presented at the ICALP: Automata, Languages and Programming, 2005, vol. 3580, pp. 878–890.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Stochastic Rabin and Streett Games</i>. Vol. 3580, Springer, 2005, pp. 878–90, doi:<a href=\"https://doi.org/10.1007/11523468_71\">10.1007/11523468_71</a>.","short":"K. Chatterjee, L. De Alfaro, T.A. Henzinger, in:, Springer, 2005, pp. 878–890."},"date_updated":"2021-01-12T07:59:39Z","extern":1,"quality_controlled":0,"intvolume":"      3580","publist_id":"158","conference":{"name":"ICALP: Automata, Languages and Programming"},"status":"public","day":"24","doi":"10.1007/11523468_71","year":"2005","page":"878 - 890","acknowledgement":"This research was supported in part by the ONR grant N00014-02-1-0671, the AFOSR MURI grant F49620-00-1-0327, and the NSF grant CCR-0225610.","type":"conference","_id":"4553","date_created":"2018-12-11T12:09:27Z"},{"doi":"10.1109/LICS.2005.26","page":"178 - 187","status":"public","day":"19","year":"2005","_id":"4554","type":"conference","date_created":"2018-12-11T12:09:27Z","publist_id":"159","conference":{"name":"LICS: Logic in Computer Science"},"author":[{"full_name":"Krishnendu Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","full_name":"Thomas Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Jurdziński, Marcin","last_name":"Jurdziński","first_name":"Marcin"}],"citation":{"ieee":"K. Chatterjee, T. A. Henzinger, and M. Jurdziński, “Mean-payoff parity games,” presented at the LICS: Logic in Computer Science, 2005, pp. 178–187.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Jurdziński, M. (2005). Mean-payoff parity games (pp. 178–187). Presented at the LICS: Logic in Computer Science, IEEE. <a href=\"https://doi.org/10.1109/LICS.2005.26\">https://doi.org/10.1109/LICS.2005.26</a>","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Marcin Jurdziński. “Mean-Payoff Parity Games,” 178–87. IEEE, 2005. <a href=\"https://doi.org/10.1109/LICS.2005.26\">https://doi.org/10.1109/LICS.2005.26</a>.","ista":"Chatterjee K, Henzinger TA, Jurdziński M. 2005. Mean-payoff parity games. LICS: Logic in Computer Science, 178–187.","ama":"Chatterjee K, Henzinger TA, Jurdziński M. Mean-payoff parity games. In: IEEE; 2005:178-187. doi:<a href=\"https://doi.org/10.1109/LICS.2005.26\">10.1109/LICS.2005.26</a>","mla":"Chatterjee, Krishnendu, et al. <i>Mean-Payoff Parity Games</i>. IEEE, 2005, pp. 178–87, doi:<a href=\"https://doi.org/10.1109/LICS.2005.26\">10.1109/LICS.2005.26</a>.","short":"K. Chatterjee, T.A. Henzinger, M. Jurdziński, in:, IEEE, 2005, pp. 178–187."},"extern":1,"quality_controlled":0,"date_updated":"2021-01-12T07:59:39Z","title":"Mean-payoff parity games","publisher":"IEEE","date_published":"2005-09-19T00:00:00Z","publication_status":"published","month":"09","abstract":[{"text":"Games played on graphs may have qualitative objectives, such as the satisfaction of an ω-regular property, or quantitative objectives, such as the optimization of a real-valued reward. When games are used to model reactive systems with both fairness assumptions and quantitative (e.g., resource) constraints, then the corresponding objective combines both a qualitative and a quantitative component. In a general case of interest, the qualitative component is a parity condition and the quantitative component is a mean-payoff reward. We study and solve such mean-payoff parity games. We also prove some interesting facts about mean-payoff parity games which distinguish them both from mean-payoff and from parity games. In particular, we show that optimal strategies exist in mean-payoff parity games, but they may require infinite memory.","lang":"eng"}]},{"abstract":[{"lang":"eng","text":"Planning in adversarial and uncertain environments can be modeled as the problem of devising strategies in stochastic perfect information games. These games are generalizations of Markov decision processes (MDPs): there are two (adversarial) players, and a source of randomness. The main practical obstacle to computing winning strategies in such games is the size of the state space. In practice therefore, one typically works with abstractions of the model. The diffculty is to come up with an abstraction that is neither too coarse to remove all winning strategies (plans), nor too fine to be intractable. In verification, the paradigm of counterexample-guided abstraction refinement has been successful to construct useful but parsimonious abstractions automatically. We extend this paradigm to probabilistic models (namely, perfect information games and, as a special case, MDPs). This allows us to apply the counterexample-guided abstraction paradigm to the AI planning problem. As special cases, we get planning algorithms for MDPs and deterministic systems that automatically construct system abstractions."}],"publication_status":"published","month":"01","publisher":"AUAI Press","date_published":"2005-01-01T00:00:00Z","title":"Counterexample-guided planning","date_updated":"2021-01-12T07:59:41Z","quality_controlled":0,"extern":1,"citation":{"short":"K. Chatterjee, T.A. Henzinger, R. Jhala, R. Majumdar, in:, AUAI Press, 2005, pp. 104–111.","mla":"Chatterjee, Krishnendu, et al. <i>Counterexample-Guided Planning</i>. AUAI Press, 2005, pp. 104–11.","ieee":"K. Chatterjee, T. A. Henzinger, R. Jhala, and R. Majumdar, “Counterexample-guided planning,” presented at the UAI: Uncertainty in Artificial Intelligence, 2005, pp. 104–111.","apa":"Chatterjee, K., Henzinger, T. A., Jhala, R., &#38; Majumdar, R. (2005). Counterexample-guided planning (pp. 104–111). Presented at the UAI: Uncertainty in Artificial Intelligence, AUAI Press.","ama":"Chatterjee K, Henzinger TA, Jhala R, Majumdar R. Counterexample-guided planning. In: AUAI Press; 2005:104-111.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Ranjit Jhala, and Ritankar Majumdar. “Counterexample-Guided Planning,” 104–11. AUAI Press, 2005.","ista":"Chatterjee K, Henzinger TA, Jhala R, Majumdar R. 2005. Counterexample-guided planning. UAI: Uncertainty in Artificial Intelligence, 104–111."},"author":[{"full_name":"Krishnendu Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Thomas Henzinger"},{"first_name":"Ranjit","last_name":"Jhala","full_name":"Jhala, Ranjit"},{"last_name":"Majumdar","first_name":"Ritankar","full_name":"Majumdar, Ritankar S"}],"publist_id":"157","conference":{"name":"UAI: Uncertainty in Artificial Intelligence"},"date_created":"2018-12-11T12:09:28Z","_id":"4557","type":"conference","page":"104 - 111","year":"2005","day":"01","status":"public","main_file_link":[{"open_access":"0","url":"http://uai.sis.pitt.edu/papers/05/p104-chatterjee.pdf"}]}]