[{"title":"A high-speed object tracker from off-the-shelf components","publication":"ICCV: International Conference on Computer Vision","quality_controlled":0,"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"day":"27","_id":"3717","publist_id":"2640","acknowledgement":"IEEE Workshop URL:  http://humanoidscv.ime.cmc.osaka-u.ac.jp/","status":"public","author":[{"last_name":"Lampert","orcid":"0000-0001-8622-7887","first_name":"Christoph","full_name":"Christoph Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Peters","full_name":"Peters, Jan","first_name":"Jan"}],"citation":{"apa":"Lampert, C., &#38; Peters, J. (2009). <i>A high-speed object tracker from off-the-shelf components</i>. <i>ICCV: International Conference on Computer Vision</i>. IEEE.","ista":"Lampert C, Peters J. 2009. A high-speed object tracker from off-the-shelf components, IEEE,p.","ama":"Lampert C, Peters J. <i>A High-Speed Object Tracker from off-the-Shelf Components</i>. IEEE; 2009.","mla":"Lampert, Christoph, and Jan Peters. “A High-Speed Object Tracker from off-the-Shelf Components.” <i>ICCV: International Conference on Computer Vision</i>, IEEE, 2009.","short":"C. Lampert, J. Peters, A High-Speed Object Tracker from off-the-Shelf Components, IEEE, 2009.","chicago":"Lampert, Christoph, and Jan Peters. <i>A High-Speed Object Tracker from off-the-Shelf Components</i>. <i>ICCV: International Conference on Computer Vision</i>. IEEE, 2009.","ieee":"C. Lampert and J. Peters, <i>A high-speed object tracker from off-the-shelf components</i>. IEEE, 2009."},"type":"conference_poster","publication_status":"published","date_created":"2018-12-11T12:04:47Z","extern":1,"abstract":[{"text":"We introduce RTblob, an open-source real-time vision system for 3D object detection that achieves over 200 Hz tracking speed with only off-the-shelf hardware component. It allows fast and accurate tracking of colored objects in 3D without expensive and often custom-built hardware, instead making use of the PC graphics cards for the necessary image processing operations.","lang":"eng"}],"year":"2009","month":"09","date_updated":"2020-07-14T12:46:14Z","publisher":"IEEE","date_published":"2009-09-27T00:00:00Z","main_file_link":[{"url":"http://pubman.mpdl.mpg.de/pubman/faces/viewItemOverviewPage.jsp?itemId=escidoc:1789154","open_access":"0"}]},{"status":"public","author":[{"first_name":"Gasper","full_name":"Gasper Tkacik","orcid":"0000-0002-6699-1455","last_name":"Tkacik","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Schneidman, Elad","first_name":"Elad","last_name":"Schneidman"},{"last_name":"Berry","full_name":"Berry, Michael J","first_name":"Michael"},{"last_name":"Bialek","full_name":"Bialek, William S","first_name":"William"}],"oa":1,"type":"preprint","citation":{"ieee":"G. Tkačik, E. Schneidman, M. Berry, and W. Bialek, “Spin glass models for a network of real neurons,” <i>ArXiv</i>, vol. q-NC. ArXiv, 2009.","chicago":"Tkačik, Gašper, Elad Schneidman, Michael Berry, and William Bialek. “Spin Glass Models for a Network of Real Neurons.” <i>ArXiv</i>. ArXiv, 2009.","short":"G. Tkačik, E. Schneidman, M. Berry, W. Bialek, ArXiv q-NC (2009).","mla":"Tkačik, Gašper, et al. “Spin Glass Models for a Network of Real Neurons.” <i>ArXiv</i>, vol. q-NC, ArXiv, 2009.","ama":"Tkačik G, Schneidman E, Berry M, Bialek W. Spin glass models for a network of real neurons. <i>ArXiv</i>. 2009;q-NC.","apa":"Tkačik, G., Schneidman, E., Berry, M., &#38; Bialek, W. (2009). Spin glass models for a network of real neurons. <i>ArXiv</i>. ArXiv.","ista":"Tkačik G, Schneidman E, Berry M, Bialek W. 2009. Spin glass models for a network of real neurons. ArXiv, q-NC, ."},"title":"Spin glass models for a network of real neurons","quality_controlled":0,"publication":"ArXiv","day":"01","_id":"3732","publist_id":"2496","year":"2009","abstract":[{"lang":"eng","text":"Ising models with pairwise interactions are the least structured, or maximum-entropy, probability distributions that exactly reproduce measured pairwise correlations between spins. Here we use this equivalence to construct Ising models that describe the correlated spiking activity of populations of 40 neurons in the salamander retina responding to natural movies. We show that pairwise interactions between neurons account for observed higher-order correlations, and that for groups of 10 or more neurons pairwise interactions can no longer be regarded as small perturbations in an independent system. We then construct network ensembles that generalize the network instances observed in the experiment, and study their thermodynamic behavior and coding capacity. Based on this construction, we can also create synthetic networks of 120 neurons, and find that with increasing size the networks operate closer to a critical point and start exhibiting collective behaviors reminiscent of spin glasses. We examine closely two such behaviors that could be relevant for neural code: tuning of the network to the critical point to maximize the ability to encode diverse stimuli, and using the metastable states of the Ising Hamiltonian as neural code words."}],"extern":1,"volume":"q-bio.NC","month":"01","date_updated":"2021-01-12T07:51:48Z","publisher":"ArXiv","date_published":"2009-01-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/0912.5409v1"}],"publication_status":"published","date_created":"2018-12-11T12:04:52Z"},{"doi":"10.1073/pnas.0905497106","intvolume":"       106","status":"public","author":[{"first_name":"Sergey","full_name":"Kryazhimskiy,Sergey","last_name":"Kryazhimskiy"},{"id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","last_name":"Tkacik","orcid":"0000-0002-6699-1455","full_name":"Gasper Tkacik","first_name":"Gasper"},{"last_name":"Plotkin","full_name":"Plotkin,Joshua B","first_name":"Joshua"}],"type":"journal_article","citation":{"chicago":"Kryazhimskiy, Sergey, Gašper Tkačik, and Joshua Plotkin. “The Dynamics of Adaptation on Correlated Fitness Landscapes.” <i>PNAS</i>. National Academy of Sciences, 2009. <a href=\"https://doi.org/10.1073/pnas.0905497106\">https://doi.org/10.1073/pnas.0905497106</a>.","ieee":"S. Kryazhimskiy, G. Tkačik, and J. Plotkin, “The dynamics of adaptation on correlated fitness landscapes,” <i>PNAS</i>, vol. 106, no. 44. National Academy of Sciences, pp. 18638–18643, 2009.","apa":"Kryazhimskiy, S., Tkačik, G., &#38; Plotkin, J. (2009). The dynamics of adaptation on correlated fitness landscapes. <i>PNAS</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.0905497106\">https://doi.org/10.1073/pnas.0905497106</a>","ista":"Kryazhimskiy S, Tkačik G, Plotkin J. 2009. The dynamics of adaptation on correlated fitness landscapes. PNAS. 106(44), 18638–18643.","ama":"Kryazhimskiy S, Tkačik G, Plotkin J. The dynamics of adaptation on correlated fitness landscapes. <i>PNAS</i>. 2009;106(44):18638-18643. doi:<a href=\"https://doi.org/10.1073/pnas.0905497106\">10.1073/pnas.0905497106</a>","mla":"Kryazhimskiy, Sergey, et al. “The Dynamics of Adaptation on Correlated Fitness Landscapes.” <i>PNAS</i>, vol. 106, no. 44, National Academy of Sciences, 2009, pp. 18638–43, doi:<a href=\"https://doi.org/10.1073/pnas.0905497106\">10.1073/pnas.0905497106</a>.","short":"S. Kryazhimskiy, G. Tkačik, J. Plotkin, PNAS 106 (2009) 18638–18643."},"issue":"44","publication":"PNAS","quality_controlled":0,"title":"The dynamics of adaptation on correlated fitness landscapes","day":"01","_id":"3733","publist_id":"2497","page":"18638 - 18643","volume":106,"abstract":[{"lang":"eng","text":"Evolutionary theory predicts that a population in a new environment will accumulate adaptive substitutions, but precisely how they accumulate is poorly understood. The dynamics of adaptation depend on the underlying fitness landscape. Virtually nothing is known about fitness landscapes in nature, and few methods allow us to infer the landscape from empirical data. With a view toward this inference problem, we have developed a theory that, in the weak-mutation limit, predicts how a population's mean fitness and the number of accumulated substitutions are expected to increase over time, depending on the underlying fitness landscape. We find that fitness and substitution trajectories depend not on the full distribution of fitness effects of available mutations but rather on the expected fixation probability and the expected fitness increment of mutations. We introduce a scheme that classifies landscapes in terms of the qualitative evolutionary dynamics they produce. We show that linear substitution trajectories, long considered the hallmark of neutral evolution, can arise even when mutations are strongly selected. Our results provide a basis for understanding the dynamics of adaptation and for inferring properties of an organism's fitness landscape from temporal data. Applying these methods to data from a long-term experiment, we infer the sign and strength of epistasis among beneficial mutations in the Escherichia coli genome."}],"extern":1,"year":"2009","date_updated":"2021-01-12T07:51:48Z","month":"01","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2767361","open_access":"0"}],"date_published":"2009-01-01T00:00:00Z","publisher":"National Academy of Sciences","publication_status":"published","date_created":"2018-12-11T12:04:52Z"},{"doi":"10.1103/PhysRevE.80.031920","intvolume":"        80","status":"public","author":[{"id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","first_name":"Gasper","full_name":"Gasper Tkacik","last_name":"Tkacik","orcid":"0000-0002-6699-1455"},{"full_name":"Walczak, Aleksandra M","first_name":"Aleksandra","last_name":"Walczak"},{"full_name":"Bialek, William S","first_name":"William","last_name":"Bialek"}],"type":"journal_article","citation":{"short":"G. Tkačik, A. Walczak, W. Bialek, Physical Review E Statistical Nonlinear and Soft Matter Physics 80 (2009).","ama":"Tkačik G, Walczak A, Bialek W. Optimizing information flow in small genetic networks. <i>Physical Review E Statistical Nonlinear and Soft Matter Physics</i>. 2009;80(3). doi:<a href=\"https://doi.org/10.1103/PhysRevE.80.031920\">10.1103/PhysRevE.80.031920</a>","mla":"Tkačik, Gašper, et al. “Optimizing Information Flow in Small Genetic Networks.” <i>Physical Review E Statistical Nonlinear and Soft Matter Physics</i>, vol. 80, no. 3, American Institute of Physics, 2009, doi:<a href=\"https://doi.org/10.1103/PhysRevE.80.031920\">10.1103/PhysRevE.80.031920</a>.","ista":"Tkačik G, Walczak A, Bialek W. 2009. Optimizing information flow in small genetic networks. Physical Review E Statistical Nonlinear and Soft Matter Physics. 80(3).","apa":"Tkačik, G., Walczak, A., &#38; Bialek, W. (2009). Optimizing information flow in small genetic networks. <i>Physical Review E Statistical Nonlinear and Soft Matter Physics</i>. American Institute of Physics. <a href=\"https://doi.org/10.1103/PhysRevE.80.031920\">https://doi.org/10.1103/PhysRevE.80.031920</a>","ieee":"G. Tkačik, A. Walczak, and W. Bialek, “Optimizing information flow in small genetic networks,” <i>Physical Review E Statistical Nonlinear and Soft Matter Physics</i>, vol. 80, no. 3. American Institute of Physics, 2009.","chicago":"Tkačik, Gašper, Aleksandra Walczak, and William Bialek. “Optimizing Information Flow in Small Genetic Networks.” <i>Physical Review E Statistical Nonlinear and Soft Matter Physics</i>. American Institute of Physics, 2009. <a href=\"https://doi.org/10.1103/PhysRevE.80.031920\">https://doi.org/10.1103/PhysRevE.80.031920</a>."},"issue":"3 ","title":"Optimizing information flow in small genetic networks","publication":"Physical Review E Statistical Nonlinear and Soft Matter Physics","quality_controlled":0,"_id":"3737","day":"29","publist_id":"2493","year":"2009","abstract":[{"lang":"eng","text":"In order to survive, reproduce, and (in multicellular organisms) differentiate, cells must control the concentrations of the myriad different proteins that are encoded in the genome. The precision of this control is limited by the inevitable randomness of individual molecular events. Here we explore how cells can maximize their control power in the presence of these physical limits; formally, we solve the theoretical problem of maximizing the information transferred from inputs to outputs when the number of available molecules is held fixed. We start with the simplest version of the problem, in which a single transcription factor protein controls the readout of one or more genes by binding to DNA. We further simplify by assuming that this regulatory network operates in steady state, that the noise is small relative to the available dynamic range, and that the target genes do not interact. Even in this simple limit, we find a surprisingly rich set of optimal solutions. Importantly, for each locally optimal regulatory network, all parameters are determined once the physical constraints on the number of available molecules are specified. Although we are solving an oversimplified version of the problem facing real cells, we see parallels between the structure of these optimal solutions and the behavior of actual genetic regulatory networks. Subsequent papers will discuss more complete versions of the problem."}],"extern":1,"volume":80,"month":"09","date_updated":"2021-01-12T07:51:50Z","publisher":"American Institute of Physics","main_file_link":[{"open_access":"0","url":"http://arxiv.org/abs/0903.4491"}],"date_published":"2009-09-29T00:00:00Z","publication_status":"published","date_created":"2018-12-11T12:04:53Z"},{"date_created":"2018-12-11T12:04:56Z","publication_status":"published","month":"05","date_updated":"2021-01-12T07:51:54Z","extern":1,"abstract":[{"text":"The precision of biochemical signaling is limited by randomness in the diffusive arrival of molecules at their targets. For proteins binding to specific sites on DNA and regulating transcription, the ability of the proteins to diffuse in one dimension by sliding along the length of the DNA, in addition to their diffusion in bulk solution, would seem to generate a larger target for DNA binding, consequently reducing the noise in the occupancy of the regulatory site. Here we show that this effect is largely canceled by the enhanced temporal correlations in one-dimensional diffusion. With realistic parameters, sliding along DNA has surprisingly little effect on the physical limits to the precision of transcriptional regulation.","lang":"eng"}],"year":"2009","volume":79,"publisher":"American Institute of Physics","date_published":"2009-05-04T00:00:00Z","title":"Diffusion, dimensionality, and noise in transcriptional regulation","publication":"Physical Review E Statistical Nonlinear and Soft Matter Physics","quality_controlled":0,"issue":"5","publist_id":"2483","_id":"3745","day":"04","status":"public","intvolume":"        79","doi":"10.1103/PhysRevE.79.051901","type":"journal_article","citation":{"chicago":"Tkačik, Gašper, and William Bialek. “Diffusion, Dimensionality, and Noise in Transcriptional Regulation.” <i>Physical Review E Statistical Nonlinear and Soft Matter Physics</i>. American Institute of Physics, 2009. <a href=\"https://doi.org/10.1103/PhysRevE.79.051901\">https://doi.org/10.1103/PhysRevE.79.051901</a>.","ieee":"G. Tkačik and W. Bialek, “Diffusion, dimensionality, and noise in transcriptional regulation,” <i>Physical Review E Statistical Nonlinear and Soft Matter Physics</i>, vol. 79, no. 5. American Institute of Physics, 2009.","ista":"Tkačik G, Bialek W. 2009. Diffusion, dimensionality, and noise in transcriptional regulation. Physical Review E Statistical Nonlinear and Soft Matter Physics. 79(5).","apa":"Tkačik, G., &#38; Bialek, W. (2009). Diffusion, dimensionality, and noise in transcriptional regulation. <i>Physical Review E Statistical Nonlinear and Soft Matter Physics</i>. American Institute of Physics. <a href=\"https://doi.org/10.1103/PhysRevE.79.051901\">https://doi.org/10.1103/PhysRevE.79.051901</a>","mla":"Tkačik, Gašper, and William Bialek. “Diffusion, Dimensionality, and Noise in Transcriptional Regulation.” <i>Physical Review E Statistical Nonlinear and Soft Matter Physics</i>, vol. 79, no. 5, American Institute of Physics, 2009, doi:<a href=\"https://doi.org/10.1103/PhysRevE.79.051901\">10.1103/PhysRevE.79.051901</a>.","ama":"Tkačik G, Bialek W. Diffusion, dimensionality, and noise in transcriptional regulation. <i>Physical Review E Statistical Nonlinear and Soft Matter Physics</i>. 2009;79(5). doi:<a href=\"https://doi.org/10.1103/PhysRevE.79.051901\">10.1103/PhysRevE.79.051901</a>","short":"G. Tkačik, W. Bialek, Physical Review E Statistical Nonlinear and Soft Matter Physics 79 (2009)."},"author":[{"id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6699-1455","last_name":"Tkacik","full_name":"Gasper Tkacik","first_name":"Gasper"},{"full_name":"Bialek, William S","first_name":"William","last_name":"Bialek"}]},{"date_updated":"2021-01-12T07:51:54Z","month":"01","year":"2009","extern":1,"date_published":"2009-01-01T00:00:00Z","publisher":"Springer","date_created":"2018-12-11T12:04:56Z","publication_status":"published","status":"public","doi":"10.1007/978-0-387-30440-3_48","citation":{"ieee":"G. Tkačik and W. Bialek, “Cell Biology: Networks, regulation, pathways,” in <i>Encyclopedia of Complexity and Systems Science</i>, R. Meyers, Ed. Springer, 2009, pp. 719–741.","chicago":"Tkačik, Gašper, and William Bialek. “Cell Biology: Networks, Regulation, Pathways.” In <i>Encyclopedia of Complexity and Systems Science</i>, edited by R. Meyers, 719–41. Springer, 2009. <a href=\"https://doi.org/10.1007/978-0-387-30440-3_48\">https://doi.org/10.1007/978-0-387-30440-3_48</a>.","short":"G. Tkačik, W. Bialek, in:, R. Meyers (Ed.), Encyclopedia of Complexity and Systems Science, Springer, 2009, pp. 719–741.","ama":"Tkačik G, Bialek W. Cell Biology: Networks, regulation, pathways. In: Meyers R, ed. <i>Encyclopedia of Complexity and Systems Science</i>. Springer; 2009:719-741. doi:<a href=\"https://doi.org/10.1007/978-0-387-30440-3_48\">10.1007/978-0-387-30440-3_48</a>","mla":"Tkačik, Gašper, and William Bialek. “Cell Biology: Networks, Regulation, Pathways.” <i>Encyclopedia of Complexity and Systems Science</i>, edited by R. Meyers, Springer, 2009, pp. 719–41, doi:<a href=\"https://doi.org/10.1007/978-0-387-30440-3_48\">10.1007/978-0-387-30440-3_48</a>.","ista":"Tkačik G, Bialek W. 2009.Cell Biology: Networks, regulation, pathways. In: Encyclopedia of Complexity and Systems Science. , 719–741.","apa":"Tkačik, G., &#38; Bialek, W. (2009). Cell Biology: Networks, regulation, pathways. In R. Meyers (Ed.), <i>Encyclopedia of Complexity and Systems Science</i> (pp. 719–741). Springer. <a href=\"https://doi.org/10.1007/978-0-387-30440-3_48\">https://doi.org/10.1007/978-0-387-30440-3_48</a>"},"type":"book_chapter","author":[{"orcid":"0000-0002-6699-1455","last_name":"Tkacik","full_name":"Gasper Tkacik","first_name":"Gasper","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"William","full_name":"Bialek, William S","last_name":"Bialek"}],"publication":"Encyclopedia of Complexity and Systems Science","quality_controlled":0,"title":"Cell Biology: Networks, regulation, pathways","publist_id":"2481","page":"719 - 741","editor":[{"last_name":"Meyers","first_name":"R.","full_name":"Meyers,R. A."}],"_id":"3747","day":"01"},{"status":"public","intvolume":"        28","doi":"10.1145/1531326.1531382","citation":{"chicago":"Wojtan, Chris, Nils Thürey, Markus Gross, and Greg Turk. “Deforming Meshes That Split and Merge.” <i>ACM Transactions on Graphics</i>. ACM, 2009. <a href=\"https://doi.org/10.1145/1531326.1531382\">https://doi.org/10.1145/1531326.1531382</a>.","ieee":"C. Wojtan, N. Thürey, M. Gross, and G. Turk, “Deforming meshes that split and merge,” <i>ACM Transactions on Graphics</i>, vol. 28, no. 3. ACM, 2009.","apa":"Wojtan, C., Thürey, N., Gross, M., &#38; Turk, G. (2009). Deforming meshes that split and merge. <i>ACM Transactions on Graphics</i>. ACM. <a href=\"https://doi.org/10.1145/1531326.1531382\">https://doi.org/10.1145/1531326.1531382</a>","ista":"Wojtan C, Thürey N, Gross M, Turk G. 2009. Deforming meshes that split and merge. ACM Transactions on Graphics. 28(3).","short":"C. Wojtan, N. Thürey, M. Gross, G. Turk, ACM Transactions on Graphics 28 (2009).","mla":"Wojtan, Chris, et al. “Deforming Meshes That Split and Merge.” <i>ACM Transactions on Graphics</i>, vol. 28, no. 3, ACM, 2009, doi:<a href=\"https://doi.org/10.1145/1531326.1531382\">10.1145/1531326.1531382</a>.","ama":"Wojtan C, Thürey N, Gross M, Turk G. Deforming meshes that split and merge. <i>ACM Transactions on Graphics</i>. 2009;28(3). doi:<a href=\"https://doi.org/10.1145/1531326.1531382\">10.1145/1531326.1531382</a>"},"type":"journal_article","language":[{"iso":"eng"}],"author":[{"full_name":"Wojtan, Christopher J","first_name":"Christopher J","last_name":"Wojtan","orcid":"0000-0001-6646-5546","id":"3C61F1D2-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Thürey","first_name":"Nils","full_name":"Thürey, Nils"},{"last_name":"Gross","first_name":"Markus","full_name":"Gross, Markus"},{"last_name":"Turk","full_name":"Turk, Greg","first_name":"Greg"}],"publication":"ACM Transactions on Graphics","title":"Deforming meshes that split and merge","issue":"3","publist_id":"2466","_id":"3764","day":"01","date_updated":"2023-02-23T11:41:39Z","month":"08","volume":28,"extern":"1","abstract":[{"lang":"eng","text":"We present a method for accurately tracking the moving surface of deformable materials in a manner that gracefully handles topological changes. We employ a Lagrangian surface tracking method, and we use a triangle mesh for our surface representation so that fine features can be retained. We make topological changes to the mesh by first identifying merging or splitting events at a particular grid resolution, and then locally creating new pieces of the mesh in the affected cells using a standard isosurface creation method. We stitch the new, topologically simplified portion of the mesh to the rest of the mesh at the cell boundaries. Our method detects and treats topological events with an emphasis on the preservation of detailed features, while simultaneously simplifying those portions of the material that are not visible. Our surface tracker is not tied to a particular method for simulating deformable materials. In particular, we show results from two significantly different simulators: a Lagrangian FEM simulator with tetrahedral elements, and an Eulerian grid-based fluid simulator. Although our surface tracking method is generic, it is particularly well-suited for simulations that exhibit fine surface details and numerous topological events. Highlights of our results include merging of viscoplastic materials with complex geometry, a taffy-pulling animation with many fold and merge events, and stretching and slicing of stiff plastic material."}],"year":"2009","date_published":"2009-08-01T00:00:00Z","publisher":"ACM","date_created":"2018-12-11T12:05:02Z","article_processing_charge":"No","publication_status":"published","oa_version":"None","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"date_published":"2009-10-14T00:00:00Z","publisher":"Oxford University Press","date_updated":"2025-07-02T06:49:41Z","month":"10","volume":25,"year":"2009","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"None","date_created":"2018-12-11T12:05:04Z","article_processing_charge":"No","publication_status":"published","article_type":"letter_note","type":"journal_article","citation":{"chicago":"Kupczok, Anne, and Arndt Von Haeseler. “Comment on ‘A Congruence Index for Testing Topological Similarity between Trees.’” <i>Bioinformatics</i>. Oxford University Press, 2009. <a href=\"https://doi.org/10.1093/bioinformatics/btn539\">https://doi.org/10.1093/bioinformatics/btn539</a>.","ieee":"A. Kupczok and A. Von Haeseler, “Comment on ‘A congruence index for testing topological similarity between trees,’” <i>Bioinformatics</i>, vol. 25, no. 1. Oxford University Press, pp. 147–149, 2009.","apa":"Kupczok, A., &#38; Von Haeseler, A. (2009). Comment on “A congruence index for testing topological similarity between trees.” <i>Bioinformatics</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/bioinformatics/btn539\">https://doi.org/10.1093/bioinformatics/btn539</a>","ista":"Kupczok A, Von Haeseler A. 2009. Comment on ‘A congruence index for testing topological similarity between trees’. Bioinformatics. 25(1), 147–149.","short":"A. Kupczok, A. Von Haeseler, Bioinformatics 25 (2009) 147–149.","ama":"Kupczok A, Von Haeseler A. Comment on “A congruence index for testing topological similarity between trees.” <i>Bioinformatics</i>. 2009;25(1):147-149. doi:<a href=\"https://doi.org/10.1093/bioinformatics/btn539\">10.1093/bioinformatics/btn539</a>","mla":"Kupczok, Anne, and Arndt Von Haeseler. “Comment on ‘A Congruence Index for Testing Topological Similarity between Trees.’” <i>Bioinformatics</i>, vol. 25, no. 1, Oxford University Press, 2009, pp. 147–49, doi:<a href=\"https://doi.org/10.1093/bioinformatics/btn539\">10.1093/bioinformatics/btn539</a>."},"language":[{"iso":"eng"}],"author":[{"last_name":"Kupczok","full_name":"Kupczok, Anne","first_name":"Anne","id":"2BB22BC2-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Von Haeseler","full_name":"Von Haeseler, Arndt","first_name":"Arndt"}],"status":"public","doi":"10.1093/bioinformatics/btn539","intvolume":"        25","publist_id":"2459","page":"147 - 149","_id":"3768","day":"14","publication":"Bioinformatics","title":"Comment on 'A congruence index for testing topological similarity between trees'","issue":"1"},{"volume":259,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","date_created":"2018-12-11T12:05:06Z","language":[{"iso":"eng"}],"external_id":{"isi":["000267176100013"]},"author":[{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","last_name":"Barton","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H","first_name":"Nicholas H"},{"last_name":"Coe","full_name":"Coe, Jason","first_name":"Jason"}],"intvolume":"       259","status":"public","page":"317 - 324","quality_controlled":"1","title":"On the application of statistical physics to evolutionary biology","date_published":"2009-07-21T00:00:00Z","main_file_link":[{"url":"https://hal.archives-ouvertes.fr/hal-00554594/document","open_access":"1"}],"publisher":"Elsevier","abstract":[{"text":"There is a close analogy between statistical thermodynamics and the evolution of allele frequencies under mutation, selection and random drift. Wright's formula for the stationary distribution of allele frequencies is analogous to the Boltzmann distribution in statistical physics. Population size, 2N, plays the role of the inverse temperature, 1/kT, and determines the magnitude of random fluctuations. Log mean fitness, View the MathML source, tends to increase under selection, and is analogous to a (negative) energy; a potential function, U, increases under mutation in a similar way. An entropy, SH, can be defined which measures the deviation from the distribution of allele frequencies expected under random drift alone; the sum View the MathML source gives a free fitness that increases as the population evolves towards its stationary distribution. Usually, we observe the distribution of a few quantitative traits that depend on the frequencies of very many alleles. The mean and variance of such traits are analogous to observable quantities in statistical thermodynamics. Thus, we can define an entropy, SΩ, which measures the volume of allele frequency space that is consistent with the observed trait distribution. The stationary distribution of the traits is View the MathML source; this applies with arbitrary epistasis and dominance. The entropies SΩ, SH are distinct, but converge when there are so many alleles that traits fluctuate close to their expectations. Populations tend to evolve towards states that can be realised in many ways (i.e., large SΩ), which may lead to a substantial drop below the adaptive peak; we illustrate this point with a simple model of genetic redundancy. This analogy with statistical thermodynamics brings together previous ideas in a general framework, and justifies a maximum entropy approximation to the dynamics of quantitative traits.","lang":"eng"}],"year":"2009","scopus_import":"1","date_updated":"2025-09-30T09:56:01Z","month":"07","isi":1,"oa_version":"Submitted Version","publication_status":"published","article_processing_charge":"No","oa":1,"department":[{"_id":"NiBa"}],"citation":{"chicago":"Barton, Nicholas H, and Jason Coe. “On the Application of Statistical Physics to Evolutionary Biology.” <i>Journal of Theoretical Biology</i>. Elsevier, 2009. <a href=\"https://doi.org/10.1016/j.jtbi.2009.03.019\">https://doi.org/10.1016/j.jtbi.2009.03.019</a>.","ieee":"N. H. Barton and J. Coe, “On the application of statistical physics to evolutionary biology,” <i>Journal of Theoretical Biology</i>, vol. 259, no. 2. Elsevier, pp. 317–324, 2009.","apa":"Barton, N. H., &#38; Coe, J. (2009). On the application of statistical physics to evolutionary biology. <i>Journal of Theoretical Biology</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jtbi.2009.03.019\">https://doi.org/10.1016/j.jtbi.2009.03.019</a>","ista":"Barton NH, Coe J. 2009. On the application of statistical physics to evolutionary biology. Journal of Theoretical Biology. 259(2), 317–324.","short":"N.H. Barton, J. Coe, Journal of Theoretical Biology 259 (2009) 317–324.","ama":"Barton NH, Coe J. On the application of statistical physics to evolutionary biology. <i>Journal of Theoretical Biology</i>. 2009;259(2):317-324. doi:<a href=\"https://doi.org/10.1016/j.jtbi.2009.03.019\">10.1016/j.jtbi.2009.03.019</a>","mla":"Barton, Nicholas H., and Jason Coe. “On the Application of Statistical Physics to Evolutionary Biology.” <i>Journal of Theoretical Biology</i>, vol. 259, no. 2, Elsevier, 2009, pp. 317–24, doi:<a href=\"https://doi.org/10.1016/j.jtbi.2009.03.019\">10.1016/j.jtbi.2009.03.019</a>."},"type":"journal_article","doi":"10.1016/j.jtbi.2009.03.019","acknowledgement":"This work was supported by a Royal Society/Wolfson Award, and by grants EP/T11753/01, EP/C546318/01 from the EPSRC.\r\nWe are grateful to M. Cates, H.P. de Vladar and G. Sella, and to two anonymous referees, for their helpful comments.","_id":"3775","day":"21","publist_id":"2452","issue":"2","publication":"Journal of Theoretical Biology"},{"ddc":["570"],"date_created":"2018-12-11T12:05:08Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","volume":22,"has_accepted_license":"1","title":"The effect of chirality phenotype and genotype on the fecundity and viability of Partula suturalis and Lymnaea stagnalis: Implications for the evolution of sinistral snails","quality_controlled":"1","page":"1624 - 1635","intvolume":"        22","status":"public","external_id":{"isi":["000268029800006"]},"author":[{"full_name":"Davison, Angus","first_name":"Angus","last_name":"Davison"},{"last_name":"Barton","orcid":"0000-0002-8548-5240","first_name":"Nicholas H","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Bryan","full_name":"Clarke, Bryan","last_name":"Clarke"}],"language":[{"iso":"eng"}],"publication_status":"published","article_processing_charge":"No","file":[{"file_id":"6044","access_level":"open_access","creator":"dernst","date_created":"2019-02-22T09:21:44Z","relation":"main_file","content_type":"application/pdf","file_name":"Davison_JEB_v31_2009.pdf","checksum":"f70c15c6ab9306121d4153a3be0d2346","file_size":2583812,"date_updated":"2020-07-14T12:46:15Z"}],"oa_version":"Submitted Version","year":"2009","abstract":[{"text":"Why are sinistral snails so rare? Two main hypotheses are that selection acts against the establishment of new coiling morphs, because dextral and sinistral snails have trouble mating, or else a developmental constraint prevents the establishment of sinistrals. We therefore used an isolate of the snail Lymnaea stagnalis, in which sinistrals are rare, and populations of Partula suturalis, in which sinistrals are common, as well as a mathematical model, to understand the circumstances by which new morphs evolve. The main finding is that the sinistral genotype is associated with reduced egg viability in L. stagnalis, but in P. suturalis individuals of sinistral and dextral genotype appear equally fecund, implying a lack of a constraint. As positive frequency-dependent selection against the rare chiral morph in P. suturalis also operates over a narrow range (&lt; 3%), the results suggest a model for chiral evolution in snails in which weak positive frequency-dependent selection may be overcome by a negative frequency-dependent selection, such as reproductive character displacement. In snails, there is not always a developmental constraint. As the direction of cleavage, and thus the directional asymmetry of the entire body, does not generally vary in other Spiralia (annelids, echiurans, vestimentiferans, sipunculids and nemerteans), it remains an open question as to whether this is because of a constraint and/or because most taxa do not have a conspicuous external asymmetry (like a shell) upon which selection can act.","lang":"eng"}],"scopus_import":"1","isi":1,"month":"08","date_updated":"2025-09-30T09:55:32Z","publisher":"Wiley","date_published":"2009-08-01T00:00:00Z","pubrep_id":"553","issue":"8","file_date_updated":"2020-07-14T12:46:15Z","publication":"Journal of Evolutionary Biology","_id":"3780","day":"01","publist_id":"2447","acknowledgement":"We owe a great debt to Jim Murray for his many contributions to the study of Partula, in the field, in the laboratory, in the interpretation of data, and in generating new ideas about evolution. With pleasure and respect we dedicate this paper to him. Jim Murray played a leading role in making the collections used here. We are very grateful also to Ann Clarke and Elizabeth Murray for help with collecting, to Lorna Stewart for snail dissections, to Joris Koene for the gift of snails, to Natasha Constant for entering the data, and Takahiro Asami, Edmund Gittenberger and Gerhard Falkner for establishing the sinistral stock of L. stagnalis. Comments from an anonymous referee, A. Richard Palmer and the editorial board improved the manuscript. Work in the field was supported by the Royal Society, The Carnegie Trust, the Percy Sladen Trust and the National Science Foundation. The Science Research Council (B/SR/4144), the National Science Foundation (GB-4188), the Royal Society and the University of Nottingham supported work in the laboratory.","doi":"10.1111/j.1420-9101.2009.01770.x","oa":1,"department":[{"_id":"NiBa"}],"type":"journal_article","citation":{"ista":"Davison A, Barton NH, Clarke B. 2009. The effect of chirality phenotype and genotype on the fecundity and viability of Partula suturalis and Lymnaea stagnalis: Implications for the evolution of sinistral snails. Journal of Evolutionary Biology. 22(8), 1624–1635.","apa":"Davison, A., Barton, N. H., &#38; Clarke, B. (2009). The effect of chirality phenotype and genotype on the fecundity and viability of Partula suturalis and Lymnaea stagnalis: Implications for the evolution of sinistral snails. <i>Journal of Evolutionary Biology</i>. Wiley. <a href=\"https://doi.org/10.1111/j.1420-9101.2009.01770.x\">https://doi.org/10.1111/j.1420-9101.2009.01770.x</a>","ama":"Davison A, Barton NH, Clarke B. The effect of chirality phenotype and genotype on the fecundity and viability of Partula suturalis and Lymnaea stagnalis: Implications for the evolution of sinistral snails. <i>Journal of Evolutionary Biology</i>. 2009;22(8):1624-1635. doi:<a href=\"https://doi.org/10.1111/j.1420-9101.2009.01770.x\">10.1111/j.1420-9101.2009.01770.x</a>","mla":"Davison, Angus, et al. “The Effect of Chirality Phenotype and Genotype on the Fecundity and Viability of Partula Suturalis and Lymnaea Stagnalis: Implications for the Evolution of Sinistral Snails.” <i>Journal of Evolutionary Biology</i>, vol. 22, no. 8, Wiley, 2009, pp. 1624–35, doi:<a href=\"https://doi.org/10.1111/j.1420-9101.2009.01770.x\">10.1111/j.1420-9101.2009.01770.x</a>.","short":"A. Davison, N.H. Barton, B. Clarke, Journal of Evolutionary Biology 22 (2009) 1624–1635.","chicago":"Davison, Angus, Nicholas H Barton, and Bryan Clarke. “The Effect of Chirality Phenotype and Genotype on the Fecundity and Viability of Partula Suturalis and Lymnaea Stagnalis: Implications for the Evolution of Sinistral Snails.” <i>Journal of Evolutionary Biology</i>. Wiley, 2009. <a href=\"https://doi.org/10.1111/j.1420-9101.2009.01770.x\">https://doi.org/10.1111/j.1420-9101.2009.01770.x</a>.","ieee":"A. Davison, N. H. Barton, and B. Clarke, “The effect of chirality phenotype and genotype on the fecundity and viability of Partula suturalis and Lymnaea stagnalis: Implications for the evolution of sinistral snails,” <i>Journal of Evolutionary Biology</i>, vol. 22, no. 8. Wiley, pp. 1624–1635, 2009."}},{"quality_controlled":0,"publication":"Science","title":"Functional proteomics identify cornichon proteins as auxiliary subunits of AMPA receptors","issue":"5919","publist_id":"2382","page":"1313 - 9","day":"01","_id":"3828","status":"public","intvolume":"       323","doi":"10.1126/science.1167852","citation":{"apa":"Schwenk, J., Harmel, N., Zolles, G., Bildl, W., Kulik, Á., Heimrich, B., … Klocker, N. (2009). Functional proteomics identify cornichon proteins as auxiliary subunits of AMPA receptors. <i>Science</i>. American Association for the Advancement of Science. <a href=\"https://doi.org/10.1126/science.1167852\">https://doi.org/10.1126/science.1167852</a>","ista":"Schwenk J, Harmel N, Zolles G, Bildl W, Kulik Á, Heimrich B, Chisaka O, Jonas PM, Schulte U, Fakler B, Klocker N. 2009. Functional proteomics identify cornichon proteins as auxiliary subunits of AMPA receptors. Science. 323(5919), 1313–9.","short":"J. Schwenk, N. Harmel, G. Zolles, W. Bildl, Á. Kulik, B. Heimrich, O. Chisaka, P.M. Jonas, U. Schulte, B. Fakler, N. Klocker, Science 323 (2009) 1313–9.","ama":"Schwenk J, Harmel N, Zolles G, et al. Functional proteomics identify cornichon proteins as auxiliary subunits of AMPA receptors. <i>Science</i>. 2009;323(5919):1313-1319. doi:<a href=\"https://doi.org/10.1126/science.1167852\">10.1126/science.1167852</a>","mla":"Schwenk, Jochen, et al. “Functional Proteomics Identify Cornichon Proteins as Auxiliary Subunits of AMPA Receptors.” <i>Science</i>, vol. 323, no. 5919, American Association for the Advancement of Science, 2009, pp. 1313–19, doi:<a href=\"https://doi.org/10.1126/science.1167852\">10.1126/science.1167852</a>.","chicago":"Schwenk, Jochen, Nadine Harmel, Gerd Zolles, Wolfgang Bildl, Ákos Kulik, Bernd Heimrich, Osamu Chisaka, et al. “Functional Proteomics Identify Cornichon Proteins as Auxiliary Subunits of AMPA Receptors.” <i>Science</i>. American Association for the Advancement of Science, 2009. <a href=\"https://doi.org/10.1126/science.1167852\">https://doi.org/10.1126/science.1167852</a>.","ieee":"J. Schwenk <i>et al.</i>, “Functional proteomics identify cornichon proteins as auxiliary subunits of AMPA receptors,” <i>Science</i>, vol. 323, no. 5919. American Association for the Advancement of Science, pp. 1313–9, 2009."},"type":"journal_article","author":[{"full_name":"Schwenk, Jochen","first_name":"Jochen","last_name":"Schwenk"},{"last_name":"Harmel","first_name":"Nadine","full_name":"Harmel, Nadine"},{"last_name":"Zolles","full_name":"Zolles, Gerd","first_name":"Gerd"},{"last_name":"Bildl","first_name":"Wolfgang","full_name":"Bildl, Wolfgang"},{"last_name":"Kulik","full_name":"Kulik, Ákos","first_name":"Ákos"},{"last_name":"Heimrich","full_name":"Heimrich, Bernd","first_name":"Bernd"},{"last_name":"Chisaka","full_name":"Chisaka, Osamu","first_name":"Osamu"},{"id":"353C1B58-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5001-4804","last_name":"Jonas","first_name":"Peter M","full_name":"Peter Jonas"},{"full_name":"Schulte, Uwe","first_name":"Uwe","last_name":"Schulte"},{"last_name":"Fakler","full_name":"Fakler, Bernd","first_name":"Bernd"},{"full_name":"Klocker, Nikolaj","first_name":"Nikolaj","last_name":"Klocker"}],"date_created":"2018-12-11T12:05:23Z","publication_status":"published","date_updated":"2021-01-12T07:52:29Z","month":"01","volume":323,"abstract":[{"lang":"eng","text":"Glutamate receptors of the AMPA-subtype (AMPARs), together with the transmembrane AMPAR regulatory proteins (TARPs), mediate fast excitatory synaptic transmission in the mammalian brain. Here, we show by proteomic analysis that the majority of AMPARs in the rat brain are coassembled with two members of the cornichon family of transmembrane proteins, rather than with the TARPs. Coassembly with cornichon homologs 2 and 3 affects AMPARs in two ways: Cornichons increase surface expression of AMPARs, and they alter channel gating by markedly slowing deactivation and desensitization kinetics. These results demonstrate that cornichons are intrinsic auxiliary subunits of native AMPARs and provide previously unknown molecular determinants for glutamatergic neurotransmission in the central nervous system."}],"year":"2009","extern":1,"date_published":"2009-01-01T00:00:00Z","publisher":"American Association for the Advancement of Science"},{"citation":{"ista":"Bloem R, Greimel K, Henzinger TA, Jobstmann B. 2009. Synthesizing robust systems. FMCAD: Formal Methods in Computer-Aided Design, 85–92.","apa":"Bloem, R., Greimel, K., Henzinger, T. A., &#38; Jobstmann, B. (2009). Synthesizing robust systems (pp. 85–92). Presented at the FMCAD: Formal Methods in Computer-Aided Design, Springer. <a href=\"https://doi.org/10.1109/FMCAD.2009.5351139\">https://doi.org/10.1109/FMCAD.2009.5351139</a>","short":"R. Bloem, K. Greimel, T.A. Henzinger, B. Jobstmann, in:, Springer, 2009, pp. 85–92.","ama":"Bloem R, Greimel K, Henzinger TA, Jobstmann B. Synthesizing robust systems. In: Springer; 2009:85-92. doi:<a href=\"https://doi.org/10.1109/FMCAD.2009.5351139\">10.1109/FMCAD.2009.5351139</a>","mla":"Bloem, Roderick, et al. <i>Synthesizing Robust Systems</i>. Springer, 2009, pp. 85–92, doi:<a href=\"https://doi.org/10.1109/FMCAD.2009.5351139\">10.1109/FMCAD.2009.5351139</a>.","chicago":"Bloem, Roderick, Karin Greimel, Thomas A Henzinger, and Barbara Jobstmann. “Synthesizing Robust Systems,” 85–92. Springer, 2009. <a href=\"https://doi.org/10.1109/FMCAD.2009.5351139\">https://doi.org/10.1109/FMCAD.2009.5351139</a>.","ieee":"R. Bloem, K. Greimel, T. A. Henzinger, and B. Jobstmann, “Synthesizing robust systems,” presented at the FMCAD: Formal Methods in Computer-Aided Design, 2009, pp. 85–92."},"type":"conference","author":[{"last_name":"Bloem","first_name":"Roderick","full_name":"Bloem, Roderick"},{"last_name":"Greimel","full_name":"Greimel, Karin","first_name":"Karin"},{"last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Barbara","full_name":"Jobstmann, Barbara","last_name":"Jobstmann"}],"language":[{"iso":"eng"}],"status":"public","acknowledgement":"This research was supported in part by the Swiss National Science Foundation under the Indo-Swiss Joint Research Programme, by the European Network of Excellence on Embedded Systems Design (ArtistDesign), by the European Combest, Quasimodo, and Gasics projects, by the PAI program Moves funded by the Belgian Federal Government, and by the CFV (Federated Center in Verification) funded by the F.R.S.-FNRS.","doi":"10.1109/FMCAD.2009.5351139","page":"85 - 92","publist_id":"2373","_id":"3835","day":"11","title":"Synthesizing robust systems","quality_controlled":"1","publisher":"Springer","date_published":"2009-12-11T00:00:00Z","month":"12","date_updated":"2022-03-21T08:25:44Z","year":"2009","scopus_import":"1","extern":"1","abstract":[{"text":"Many specifications include assumptions on the environment. If the environment satisfies the assumptions then a correct system reacts as intended. However, when the environment deviates from its expected behavior, a correct system can behave arbitrarily. We want to synthesize robust systems that degrade gracefully, i.e., a small number of environment failures should induce a small number of system failures. We define ratio games and show that an optimal robust system corresponds to the winning strategy of a ratio game, where the system minimizes the ratio of system errors to environment errors. We show that ratio games can be solved in pseudopolynomial time.","lang":"eng"}],"conference":{"name":"FMCAD: Formal Methods in Computer-Aided Design"},"oa_version":"None","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T12:05:26Z","article_processing_charge":"No","publication_status":"published"},{"project":[{"name":"COMponent-Based Embedded Systems design Techniques","_id":"25EFB36C-B435-11E9-9278-68D0E5697425","grant_number":"215543","call_identifier":"FP7"},{"name":"Design for Embedded Systems","_id":"25F1337C-B435-11E9-9278-68D0E5697425","grant_number":"214373","call_identifier":"FP7"}],"publication_status":"published","file":[{"checksum":"3a70e21527dfaad2f198549ae5710786","file_name":"IST-2012-70-v1+1_On_Relational_Interfaces.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:16Z","file_size":310902,"file_id":"5045","relation":"main_file","date_created":"2018-12-12T10:13:57Z","creator":"system","access_level":"open_access"}],"oa_version":"Submitted Version","month":"01","date_updated":"2024-10-21T06:03:06Z","scopus_import":"1","year":"2009","abstract":[{"lang":"eng","text":"In this paper we extend the work of Alfaro, Henzinger et al. on interface theories for component-based design. Existing interface theories often fail to capture functional relations between the inputs and outputs of an interface. For example, a simple synchronous interface that takes as input a number n ≥ 0 and returns, at the same time, as output n + 1, cannot be expressed in existing theories. In this paper we provide a theory of relational interfaces, where such input-output relations can be captured. Our theory supports synchronous interfaces, both stateless and stateful. It includes explicit notions of environments and pluggability, and satisfies fundamental properties such as preservation of refinement by composition, and characterization of pluggability by refinement. We achieve these properties by making reasonable restrictions on feedback loops in interface compositions."}],"pubrep_id":"70","publisher":"ACM","date_published":"2009-01-01T00:00:00Z","publication":"EMSOFT '09 Proceedings of the seventh ACM international conference on Embedded software","file_date_updated":"2020-07-14T12:46:16Z","publist_id":"2360","day":"01","_id":"3837","acknowledgement":"This work is supported by the Center for Hybrid and Embedded Software Systems (CHESS) at UC Berkeley, which receives support from the National Science Foundation (NSF awards #0720882 (CSR-EHS: PRET) and #0720841 (CSR-CPS)), the U.S. Army Research Office (ARO #W911NF-07-2-0019), the U.S. Air Force Office of Scientific Research (MURI #FA9550-06-0312), the Air Force Research Lab (AFRL), the State of California Micro Program, and the following companies: Agilent, Bosch, Lockheed-Martin, National Instruments, Thales and Toyota. This work is also supported by the COMBEST and ArtistDesign projects of the European Union, and the Swiss National Science Foundation. ","doi":"10.1145/1629335.1629346","department":[{"_id":"ToHe"}],"citation":{"chicago":"Tripakis, Stavros, Ben Lickly, Thomas A Henzinger, and Edward Lee. “On Relational Interfaces.” In <i>EMSOFT ’09 Proceedings of the Seventh ACM International Conference on Embedded Software</i>, 67–76. ACM, 2009. <a href=\"https://doi.org/10.1145/1629335.1629346\">https://doi.org/10.1145/1629335.1629346</a>.","ieee":"S. Tripakis, B. Lickly, T. A. Henzinger, and E. Lee, “On relational interfaces,” in <i>EMSOFT ’09 Proceedings of the seventh ACM international conference on Embedded software</i>, Grenoble, France, 2009, pp. 67–76.","ista":"Tripakis S, Lickly B, Henzinger TA, Lee E. 2009. On relational interfaces. EMSOFT ’09 Proceedings of the seventh ACM international conference on Embedded software. EMSOFT: Embedded Software , 67–76.","apa":"Tripakis, S., Lickly, B., Henzinger, T. A., &#38; Lee, E. (2009). On relational interfaces. In <i>EMSOFT ’09 Proceedings of the seventh ACM international conference on Embedded software</i> (pp. 67–76). Grenoble, France: ACM. <a href=\"https://doi.org/10.1145/1629335.1629346\">https://doi.org/10.1145/1629335.1629346</a>","mla":"Tripakis, Stavros, et al. “On Relational Interfaces.” <i>EMSOFT ’09 Proceedings of the Seventh ACM International Conference on Embedded Software</i>, ACM, 2009, pp. 67–76, doi:<a href=\"https://doi.org/10.1145/1629335.1629346\">10.1145/1629335.1629346</a>.","ama":"Tripakis S, Lickly B, Henzinger TA, Lee E. On relational interfaces. In: <i>EMSOFT ’09 Proceedings of the Seventh ACM International Conference on Embedded Software</i>. ACM; 2009:67-76. doi:<a href=\"https://doi.org/10.1145/1629335.1629346\">10.1145/1629335.1629346</a>","short":"S. Tripakis, B. Lickly, T.A. Henzinger, E. Lee, in:, EMSOFT ’09 Proceedings of the Seventh ACM International Conference on Embedded Software, ACM, 2009, pp. 67–76."},"type":"conference","oa":1,"ddc":["004"],"date_created":"2018-12-11T12:05:26Z","conference":{"end_date":"2009-10-16","name":"EMSOFT: Embedded Software ","start_date":"2009-10-12","location":"Grenoble, France"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"has_accepted_license":"1","title":"On relational interfaces","quality_controlled":"1","page":"67 - 76","status":"public","author":[{"first_name":"Stavros","full_name":"Tripakis, Stavros","last_name":"Tripakis"},{"last_name":"Lickly","first_name":"Ben","full_name":"Lickly, Ben"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Lee","first_name":"Edward","full_name":"Lee, Edward"}],"language":[{"iso":"eng"}]},{"publication_status":"published","file":[{"file_size":222840,"date_updated":"2020-07-14T12:46:16Z","content_type":"application/pdf","file_name":"IST-2012-67-v1+1_Formalisms_for_specifying_Markovian_population_models.pdf","checksum":"df88431872586c773fbcfea37d7b36a2","access_level":"open_access","creator":"system","date_created":"2018-12-12T10:08:41Z","relation":"main_file","file_id":"4702"}],"oa_version":"Submitted Version","date_updated":"2025-09-30T08:49:00Z","month":"09","alternative_title":["LNCS"],"scopus_import":1,"year":"2009","abstract":[{"lang":"eng","text":"We compare several languages for specifying Markovian population models such as queuing networks and chemical reaction networks. These languages —matrix descriptions, stochastic Petri nets, stoichiometric equations, stochastic process algebras, and guarded command models— all describe continuous-time Markov chains, but they differ according to important properties, such as compositionality, expressiveness and succinctness, executability, ease of use, and the support they provide for checking the well-formedness of a model and for analyzing a model. "}],"pubrep_id":"67","date_published":"2009-09-07T00:00:00Z","publisher":"Springer","file_date_updated":"2020-07-14T12:46:16Z","publist_id":"2352","_id":"3841","day":"07","doi":"10.1007/978-3-642-04420-5_2","acknowledgement":"This research was supported in part by the Excellence Cluster on Multimodal Computing and Interaction and the Swiss National Science Foundation.","type":"conference","department":[{"_id":"ToHe"}],"citation":{"chicago":"Henzinger, Thomas A, Barbara Jobstmann, and Verena Wolf. “Formalisms for Specifying Markovian Population Models,” 5797:3–23. Springer, 2009. <a href=\"https://doi.org/10.1007/978-3-642-04420-5_2\">https://doi.org/10.1007/978-3-642-04420-5_2</a>.","ieee":"T. A. Henzinger, B. Jobstmann, and V. Wolf, “Formalisms for specifying Markovian population models,” presented at the RP: Reachability Problems, Palaiseau, France, 2009, vol. 5797, pp. 3–23.","apa":"Henzinger, T. A., Jobstmann, B., &#38; Wolf, V. (2009). Formalisms for specifying Markovian population models (Vol. 5797, pp. 3–23). Presented at the RP: Reachability Problems, Palaiseau, France: Springer. <a href=\"https://doi.org/10.1007/978-3-642-04420-5_2\">https://doi.org/10.1007/978-3-642-04420-5_2</a>","ista":"Henzinger TA, Jobstmann B, Wolf V. 2009. Formalisms for specifying Markovian population models. RP: Reachability Problems, LNCS, vol. 5797, 3–23.","mla":"Henzinger, Thomas A., et al. <i>Formalisms for Specifying Markovian Population Models</i>. Vol. 5797, Springer, 2009, pp. 3–23, doi:<a href=\"https://doi.org/10.1007/978-3-642-04420-5_2\">10.1007/978-3-642-04420-5_2</a>.","ama":"Henzinger TA, Jobstmann B, Wolf V. Formalisms for specifying Markovian population models. In: Vol 5797. Springer; 2009:3-23. doi:<a href=\"https://doi.org/10.1007/978-3-642-04420-5_2\">10.1007/978-3-642-04420-5_2</a>","short":"T.A. Henzinger, B. Jobstmann, V. Wolf, in:, Springer, 2009, pp. 3–23."},"oa":1,"date_created":"2018-12-11T12:05:28Z","ddc":["005"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Palaiseau, France","start_date":"2009-09-23","end_date":"2009-09-25","name":"RP: Reachability Problems"},"volume":5797,"related_material":{"record":[{"relation":"later_version","status":"public","id":"3381"}]},"has_accepted_license":"1","quality_controlled":"1","title":"Formalisms for specifying Markovian population models","page":"3 - 23","status":"public","intvolume":"      5797","language":[{"iso":"eng"}],"author":[{"last_name":"Henzinger","orcid":"0000−0002−2985−7724","first_name":"Thomas A","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Jobstmann, Barbara","first_name":"Barbara","last_name":"Jobstmann"},{"last_name":"Wolf","first_name":"Verena","full_name":"Wolf, Verena"}]},{"related_material":{"record":[{"relation":"later_version","status":"public","id":"3842"}]},"volume":4,"has_accepted_license":"1","ddc":["000"],"date_created":"2018-12-11T12:05:28Z","conference":{"name":"HIBI: High-Performance Computational Systems Biology","end_date":"2009-10-16","start_date":"2009-10-14","location":"Trento, Italy"},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","status":"public","intvolume":"         4","author":[{"last_name":"Didier","first_name":"Frédéric","full_name":"Didier, Frédéric"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","first_name":"Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger"},{"id":"3B43276C-F248-11E8-B48F-1D18A9856A87","last_name":"Mateescu","first_name":"Maria","full_name":"Mateescu, Maria"},{"last_name":"Wolf","first_name":"Verena","full_name":"Wolf, Verena"}],"external_id":{"isi":["000275038300017"]},"language":[{"iso":"eng"}],"title":"Fast adaptive uniformization of the chemical master equation","quality_controlled":"1","page":"118 - 127","month":"10","isi":1,"date_updated":"2025-09-30T09:54:51Z","abstract":[{"lang":"eng","text":"Within systems biology there is an increasing interest in the stochastic behavior of biochemical reaction networks. An appropriate stochastic description is provided by the chemical master equation, which represents a continuous- time Markov chain (CTMC).\r\nStandard Uniformization (SU) is an efficient method for the transient analysis of CTMCs. For systems with very different time scales, such as biochemical reaction networks, SU is computationally expensive. In these cases, a variant of SU, called adaptive uniformization (AU), is known to reduce the large number of iterations needed by SU. The additional difficulty of AU is that it requires the solution of a birth process.\r\nIn this paper we present an on-the-fly variant of AU, where we improve the original algorithm for AU at the cost of a small approximation error. By means of several examples, we show that our approach is particularly well-suited for biochemical reaction networks."}],"scopus_import":"1","year":"2009","publisher":"IEEE","date_published":"2009-10-30T00:00:00Z","article_processing_charge":"No","publication_status":"published","oa_version":"Submitted Version","file":[{"file_size":222890,"date_updated":"2020-07-14T12:46:17Z","content_type":"application/pdf","checksum":"9a3bde48f43203991a0b3c6a277c2f5b","file_name":"2009_HIBI_Didier.pdf","creator":"dernst","access_level":"open_access","relation":"main_file","date_created":"2020-05-19T16:33:55Z","file_id":"7874"}],"acknowledgement":"This research has been partially funded by the Swiss National Science Foundation under grant 205321-111840 and by the Cluster of Excellence on Multimodal Computing and Interaction at Saarland University.","doi":"10.1109/HiBi.2009.23","department":[{"_id":"ToHe"},{"_id":"CaGu"}],"type":"conference","citation":{"ama":"Didier F, Henzinger TA, Mateescu M, Wolf V. Fast adaptive uniformization of the chemical master equation. In: Vol 4. IEEE; 2009:118-127. doi:<a href=\"https://doi.org/10.1109/HiBi.2009.23\">10.1109/HiBi.2009.23</a>","mla":"Didier, Frédéric, et al. <i>Fast Adaptive Uniformization of the Chemical Master Equation</i>. Vol. 4, no. 6, IEEE, 2009, pp. 118–27, doi:<a href=\"https://doi.org/10.1109/HiBi.2009.23\">10.1109/HiBi.2009.23</a>.","short":"F. Didier, T.A. Henzinger, M. Mateescu, V. Wolf, in:, IEEE, 2009, pp. 118–127.","apa":"Didier, F., Henzinger, T. A., Mateescu, M., &#38; Wolf, V. (2009). Fast adaptive uniformization of the chemical master equation (Vol. 4, pp. 118–127). Presented at the HIBI: High-Performance Computational Systems Biology, Trento, Italy: IEEE. <a href=\"https://doi.org/10.1109/HiBi.2009.23\">https://doi.org/10.1109/HiBi.2009.23</a>","ista":"Didier F, Henzinger TA, Mateescu M, Wolf V. 2009. Fast adaptive uniformization of the chemical master equation. HIBI: High-Performance Computational Systems Biology vol. 4, 118–127.","ieee":"F. Didier, T. A. Henzinger, M. Mateescu, and V. Wolf, “Fast adaptive uniformization of the chemical master equation,” presented at the HIBI: High-Performance Computational Systems Biology, Trento, Italy, 2009, vol. 4, no. 6, pp. 118–127.","chicago":"Didier, Frédéric, Thomas A Henzinger, Maria Mateescu, and Verena Wolf. “Fast Adaptive Uniformization of the Chemical Master Equation,” 4:118–27. IEEE, 2009. <a href=\"https://doi.org/10.1109/HiBi.2009.23\">https://doi.org/10.1109/HiBi.2009.23</a>."},"oa":1,"issue":"6","file_date_updated":"2020-07-14T12:46:17Z","publist_id":"2348","_id":"3843","day":"30"},{"project":[{"name":"Design for Embedded Systems","_id":"25F1337C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"214373"},{"_id":"25EFB36C-B435-11E9-9278-68D0E5697425","name":"COMponent-Based Embedded Systems design Techniques","grant_number":"215543","call_identifier":"FP7"}],"article_processing_charge":"No","publication_status":"published","oa_version":"Submitted Version","file":[{"file_id":"4655","creator":"system","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T10:07:56Z","content_type":"application/pdf","checksum":"b2b15a5ef71eb50d62eaa5aea7efd8c4","file_name":"IST-2012-65-v1+1_Distributed_modular_Htl.pdf","file_size":526458,"date_updated":"2020-07-14T12:46:17Z"}],"month":"01","isi":1,"date_updated":"2025-09-30T09:54:22Z","scopus_import":"1","year":"2009","abstract":[{"lang":"eng","text":"The Hierarchical Timing Language (HTL) is a real-time coordination language for distributed control systems. HTL programs must be checked for well-formedness, race freedom, transmission safety (schedulability of inter-host communication), and time safety (schedulability of host computation). We present a modular abstract syntax and semantics for HTL, modular checks of well-formedness, race freedom, and transmission safety, and modular code distribution. Our contributions here complement previous results on HTL time safety and modular code generation. Modularity in HTL can be utilized in easy program composition as well as fast program analysis and code generation, but also in so-called runtime patching, where program components may be modified at runtime."}],"pubrep_id":"65","publisher":"IEEE","date_published":"2009-01-01T00:00:00Z","file_date_updated":"2020-07-14T12:46:17Z","publist_id":"2346","day":"01","_id":"3844","acknowledgement":"Supported by the EU ArtistDesign Network of Excellence on Embedded Systems Design, the EU project COMBEST, the Austrian Science Funds P18913-N15 and V00125, and Fundacao para a Ciencia e Tecnologia funds SFRH/BD/29461/2006 and PTDC/EIA/71462/2006","doi":"10.1109/RTSS.2009.9","type":"conference","department":[{"_id":"ToHe"}],"citation":{"ieee":"T. A. Henzinger, C. Kirsch, E. Marques, and A. Sokolova, “Distributed, modular HTL,” presented at the RTSS: Real-Time Systems Symposium, Washington, DC, United States, 2009, pp. 171–180.","chicago":"Henzinger, Thomas A, Christoph Kirsch, Eduardo Marques, and Ana Sokolova. “Distributed, Modular HTL,” 171–80. IEEE, 2009. <a href=\"https://doi.org/10.1109/RTSS.2009.9\">https://doi.org/10.1109/RTSS.2009.9</a>.","ama":"Henzinger TA, Kirsch C, Marques E, Sokolova A. Distributed, modular HTL. In: IEEE; 2009:171-180. doi:<a href=\"https://doi.org/10.1109/RTSS.2009.9\">10.1109/RTSS.2009.9</a>","mla":"Henzinger, Thomas A., et al. <i>Distributed, Modular HTL</i>. IEEE, 2009, pp. 171–80, doi:<a href=\"https://doi.org/10.1109/RTSS.2009.9\">10.1109/RTSS.2009.9</a>.","short":"T.A. Henzinger, C. Kirsch, E. Marques, A. Sokolova, in:, IEEE, 2009, pp. 171–180.","ista":"Henzinger TA, Kirsch C, Marques E, Sokolova A. 2009. Distributed, modular HTL. RTSS: Real-Time Systems Symposium, 171–180.","apa":"Henzinger, T. A., Kirsch, C., Marques, E., &#38; Sokolova, A. (2009). Distributed, modular HTL (pp. 171–180). Presented at the RTSS: Real-Time Systems Symposium, Washington, DC, United States: IEEE. <a href=\"https://doi.org/10.1109/RTSS.2009.9\">https://doi.org/10.1109/RTSS.2009.9</a>"},"oa":1,"ddc":["000"],"date_created":"2018-12-11T12:05:28Z","conference":{"location":"Washington, DC, United States","start_date":"2009-12-01","end_date":"2009-12-04","name":"RTSS: Real-Time Systems Symposium"},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"has_accepted_license":"1","title":"Distributed, modular HTL","quality_controlled":"1","page":"171 - 180","status":"public","author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A"},{"last_name":"Kirsch","full_name":"Kirsch, Christoph","first_name":"Christoph"},{"full_name":"Marques, Eduardo","first_name":"Eduardo","last_name":"Marques"},{"full_name":"Sokolova, Ana","first_name":"Ana","last_name":"Sokolova"}],"external_id":{"isi":["000277465500016"]},"language":[{"iso":"eng"}]},{"publication_status":"published","date_created":"2018-12-11T12:05:37Z","extern":1,"abstract":[{"text":"We investigate logics and equivalence relations that capture the qualitative behavior of Markov Decision Processes (MDPs). We present Qualitative Randomized CTL (QRCTL): formulas of this logic can express the fact that certain temporal properties hold over all paths, or with probability 0 or 1, but they do not distinguish among intermediate probability values. We present a symbolic, polynomial time model-checking algorithm for QRCTL on MDPs. The logic QRCTL induces an equivalence relation over states of an MDP that we call qualitative equivalence: informally, two states are qualitatively equivalent if the sets of formulas that hold with probability 0 or 1 at the two states are the same. We show that for finite alternating MDPs, where nondeterministic and probabilistic choices occur in different states, qualitative equivalence coincides with alternating bisimulation, and can thus be computed via efficient partition-refinement algorithms. On the other hand, in non-alternating MDPs the equivalence relations cannot be computed via partition-refinement algorithms, but rather, they require non-local computation. Finally, we consider QRCTL*, that extends QRCTL with nested temporal operators in the same manner in which CTL* extends CTL. We show that QRCTL and QRCTL* induce the same qualitative equivalence on alternating MDPs, while on non-alternating MDPs, the equivalence arising from QRCTL* can be strictly finer. We also provide a full characterization of the relation between qualitative equivalence, bisimulation, and alternating bisimulation, according to whether the MDPs are finite, and to whether their transition relations are finitely-branching.","lang":"eng"}],"year":"2009","volume":5,"month":"05","date_updated":"2021-01-12T07:52:49Z","publisher":"International Federation of Computational Logic","date_published":"2009-05-04T00:00:00Z","issue":"2","title":"Qualitative logics and equivalences for probabilistic systems","publication":"Logical Methods in Computer Science","quality_controlled":0,"_id":"3869","day":"04","publist_id":"2308","acknowledgement":"A preliminary version of this paper appeared in the proceedings of the 4th International Conference on the Quantitative Evaluation of Systems (QEST 2007).","intvolume":"         5","doi":"10.2168/LMCS-5(2:7)2009","status":"public","author":[{"first_name":"Krishnendu","full_name":"Krishnendu Chatterjee","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"De Alfaro","first_name":"Luca","full_name":"de Alfaro, Luca"},{"full_name":"Faella, Marco","first_name":"Marco","last_name":"Faella"},{"first_name":"Axel","full_name":"Legay, Axel","last_name":"Legay"}],"citation":{"chicago":"Chatterjee, Krishnendu, Luca De Alfaro, Marco Faella, and Axel Legay. “Qualitative Logics and Equivalences for Probabilistic Systems.” <i>Logical Methods in Computer Science</i>. International Federation of Computational Logic, 2009. <a href=\"https://doi.org/10.2168/LMCS-5(2:7)2009\">https://doi.org/10.2168/LMCS-5(2:7)2009</a>.","ieee":"K. Chatterjee, L. De Alfaro, M. Faella, and A. Legay, “Qualitative logics and equivalences for probabilistic systems,” <i>Logical Methods in Computer Science</i>, vol. 5, no. 2. International Federation of Computational Logic, 2009.","apa":"Chatterjee, K., De Alfaro, L., Faella, M., &#38; Legay, A. (2009). Qualitative logics and equivalences for probabilistic systems. <i>Logical Methods in Computer Science</i>. International Federation of Computational Logic. <a href=\"https://doi.org/10.2168/LMCS-5(2:7)2009\">https://doi.org/10.2168/LMCS-5(2:7)2009</a>","ista":"Chatterjee K, De Alfaro L, Faella M, Legay A. 2009. Qualitative logics and equivalences for probabilistic systems. Logical Methods in Computer Science. 5(2).","short":"K. Chatterjee, L. De Alfaro, M. Faella, A. Legay, Logical Methods in Computer Science 5 (2009).","ama":"Chatterjee K, De Alfaro L, Faella M, Legay A. Qualitative logics and equivalences for probabilistic systems. <i>Logical Methods in Computer Science</i>. 2009;5(2). doi:<a href=\"https://doi.org/10.2168/LMCS-5(2:7)2009\">10.2168/LMCS-5(2:7)2009</a>","mla":"Chatterjee, Krishnendu, et al. “Qualitative Logics and Equivalences for Probabilistic Systems.” <i>Logical Methods in Computer Science</i>, vol. 5, no. 2, International Federation of Computational Logic, 2009, doi:<a href=\"https://doi.org/10.2168/LMCS-5(2:7)2009\">10.2168/LMCS-5(2:7)2009</a>."},"type":"journal_article"},{"has_accepted_license":"1","ec_funded":1,"volume":11,"article_number":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ddc":["004"],"date_created":"2018-12-11T12:05:37Z","corr_author":"1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"37327ACE-F248-11E8-B48F-1D18A9856A87","full_name":"Horn, Florian","first_name":"Florian","last_name":"Horn"}],"external_id":{"isi":["000272039900001"]},"language":[{"iso":"eng"}],"status":"public","intvolume":"        11","title":"Finitary winning in omega-regular games","quality_controlled":"1","pubrep_id":"53","publisher":"ACM","date_published":"2009-10-01T00:00:00Z","month":"10","isi":1,"date_updated":"2025-09-30T09:53:52Z","scopus_import":"1","abstract":[{"text":"Games on graphs with omega-regular objectives provide a model for the control and synthesis of reactive systems. Every omega-regular objective can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens “eventually.” Two main strengths of the classical, infinite-limit formulation of liveness are robustness (independence from the granularity of transitions) and simplicity (abstraction of complicated time bounds). However, the classical liveness formulation suffers from the drawback that the time until something good happens may be unbounded. A stronger formulation of liveness, so-called finitary liveness, overcomes this drawback, while still retaining robustness and simplicity. Finitary liveness requires that there exists an unknown, fixed bound b such that something good happens within b transitions. While for one-shot liveness (reachability) objectives, classical and finitary liveness coincide, for repeated liveness (Buchi) objectives, the finitary formulation is strictly stronger. In this work we study games with finitary parity and Streett objectives. We prove the determinacy of these games, present algorithms for solving these games, and characterize the memory requirements of winning strategies. We show that finitary parity games can be solved in polynomial time, which is not known for infinitary parity games. For finitary Streett games, we give an EXPTIME algorithm and show that the problem is NP-hard. Our algorithms can be used, for example, for synthesizing controllers that do not let the response time of a system increase without bound.","lang":"eng"}],"year":"2009","file":[{"date_created":"2018-12-12T10:15:08Z","relation":"main_file","access_level":"open_access","creator":"system","file_id":"5125","date_updated":"2020-07-14T12:46:20Z","file_size":180082,"file_name":"IST-2012-53-v1+1_Finitary_winning_in_omega-regular_games.pdf","checksum":"139c4586d24f11e5da31fb3a0cf96ef4","content_type":"application/pdf"}],"oa_version":"Submitted Version","article_processing_charge":"No","project":[{"call_identifier":"FP7","grant_number":"215543","name":"COMponent-Based Embedded Systems design Techniques","_id":"25EFB36C-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","type":"journal_article","department":[{"_id":"KrCh"}],"citation":{"ama":"Chatterjee K, Henzinger TA, Horn F. Finitary winning in omega-regular games. <i>ACM Transactions on Computational Logic (TOCL)</i>. 2009;11(1). doi:<a href=\"https://doi.org/10.1145/1614431.1614432\">10.1145/1614431.1614432</a>","mla":"Chatterjee, Krishnendu, et al. “Finitary Winning in Omega-Regular Games.” <i>ACM Transactions on Computational Logic (TOCL)</i>, vol. 11, no. 1, 1, ACM, 2009, doi:<a href=\"https://doi.org/10.1145/1614431.1614432\">10.1145/1614431.1614432</a>.","short":"K. Chatterjee, T.A. Henzinger, F. Horn, ACM Transactions on Computational Logic (TOCL) 11 (2009).","apa":"Chatterjee, K., Henzinger, T. A., &#38; Horn, F. (2009). Finitary winning in omega-regular games. <i>ACM Transactions on Computational Logic (TOCL)</i>. ACM. <a href=\"https://doi.org/10.1145/1614431.1614432\">https://doi.org/10.1145/1614431.1614432</a>","ista":"Chatterjee K, Henzinger TA, Horn F. 2009. Finitary winning in omega-regular games. ACM Transactions on Computational Logic (TOCL). 11(1), 1.","ieee":"K. Chatterjee, T. A. Henzinger, and F. Horn, “Finitary winning in omega-regular games,” <i>ACM Transactions on Computational Logic (TOCL)</i>, vol. 11, no. 1. ACM, 2009.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Florian Horn. “Finitary Winning in Omega-Regular Games.” <i>ACM Transactions on Computational Logic (TOCL)</i>. ACM, 2009. <a href=\"https://doi.org/10.1145/1614431.1614432\">https://doi.org/10.1145/1614431.1614432</a>."},"oa":1,"acknowledgement":"This research was supported in part by the AFOSR MURI grant F49620-00-1-0327, the NSF grants CCR-0132780, CNS-0720884, and CCR- 225610, by the Swiss National Science Foundation, by the COMBEST project of the European Union, and EU-TMR network Games.\r\nWe thank anonymous reviewers for useful comments.","doi":"10.1145/1614431.1614432","publist_id":"2309","day":"01","_id":"3870","publication":"ACM Transactions on Computational Logic (TOCL)","issue":"1","file_date_updated":"2020-07-14T12:46:20Z"},{"oa_version":"Submitted Version","file":[{"content_type":"application/pdf","checksum":"af973ddbcf131b8810c6bff2c055ff56","file_name":"IST-2012-52-v1+1_Probabilistic_Weighted_Automata.pdf","file_size":200161,"date_updated":"2020-07-14T12:46:20Z","file_id":"4771","creator":"system","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T10:09:46Z"}],"project":[{"grant_number":"214373","call_identifier":"FP7","_id":"25F1337C-B435-11E9-9278-68D0E5697425","name":"Design for Embedded Systems"},{"name":"COMponent-Based Embedded Systems design Techniques","_id":"25EFB36C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"215543"}],"publication_status":"published","pubrep_id":"52","date_published":"2009-09-01T00:00:00Z","publisher":"Springer","date_updated":"2024-10-09T20:53:56Z","month":"09","alternative_title":["LNCS"],"year":"2009","scopus_import":1,"abstract":[{"lang":"eng","text":"Nondeterministic weighted automata are finite automata with numerical weights oil transitions. They define quantitative languages 1, that assign to each word v; a real number L(w). The value of ail infinite word w is computed as the maximal value of all runs over w, and the value of a run as the supremum, limsup liminf, limit average, or discounted sum of the transition weights. We introduce probabilistic weighted antomata, in which the transitions are chosen in a randomized (rather than nondeterministic) fashion. Under almost-sure semantics (resp. positive semantics), the value of a word v) is the largest real v such that the runs over w have value at least v with probability I (resp. positive probability). We study the classical questions of automata theory for probabilistic weighted automata: emptiness and universality, expressiveness, and closure under various operations oil languages. For quantitative languages, emptiness university axe defined as whether the value of some (resp. every) word exceeds a given threshold. We prove some, of these questions to he decidable, and others undecidable. Regarding expressive power, we show that probabilities allow its to define a wide variety of new classes of quantitative languages except for discounted-sum automata, where probabilistic choice is no more expressive than nondeterminism. Finally we live ail almost complete picture of the closure of various classes of probabilistic weighted automata for the following, provide, is operations oil quantitative languages: maximum, sum. and numerical complement."}],"publist_id":"2304","day":"01","_id":"3871","file_date_updated":"2020-07-14T12:46:20Z","department":[{"_id":"KrCh"}],"type":"conference","citation":{"apa":"Chatterjee, K., Doyen, L., &#38; Henzinger, T. A. (2009). Probabilistic weighted automata (Vol. 5710, pp. 244–258). Presented at the CONCUR: Concurrency Theory, Bologna, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-642-04081-8_17\">https://doi.org/10.1007/978-3-642-04081-8_17</a>","ista":"Chatterjee K, Doyen L, Henzinger TA. 2009. Probabilistic weighted automata. CONCUR: Concurrency Theory, LNCS, vol. 5710, 244–258.","short":"K. Chatterjee, L. Doyen, T.A. Henzinger, in:, Springer, 2009, pp. 244–258.","mla":"Chatterjee, Krishnendu, et al. <i>Probabilistic Weighted Automata</i>. Vol. 5710, Springer, 2009, pp. 244–58, doi:<a href=\"https://doi.org/10.1007/978-3-642-04081-8_17\">10.1007/978-3-642-04081-8_17</a>.","ama":"Chatterjee K, Doyen L, Henzinger TA. Probabilistic weighted automata. In: Vol 5710. Springer; 2009:244-258. doi:<a href=\"https://doi.org/10.1007/978-3-642-04081-8_17\">10.1007/978-3-642-04081-8_17</a>","chicago":"Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Probabilistic Weighted Automata,” 5710:244–58. Springer, 2009. <a href=\"https://doi.org/10.1007/978-3-642-04081-8_17\">https://doi.org/10.1007/978-3-642-04081-8_17</a>.","ieee":"K. Chatterjee, L. Doyen, and T. A. Henzinger, “Probabilistic weighted automata,” presented at the CONCUR: Concurrency Theory, Bologna, Italy, 2009, vol. 5710, pp. 244–258."},"oa":1,"doi":"10.1007/978-3-642-04081-8_17","acknowledgement":"This research was supported in part by the Swiss National Science Foundation under the Indo-Swiss Joint Research Programme, by the European Network of Excellence on Embedded Systems Design (ArtistDesign), by the European projects Combest, Quasimodo, and Gasics, by the PAI program Moves funded by the Belgian Federal Government, and by the CFV (Federated Center in Verification ) funded by the F.R.S.-FNRS.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Bologna, Italy","start_date":"2009-09-01","name":"CONCUR: Concurrency Theory","end_date":"2009-09-04"},"date_created":"2018-12-11T12:05:37Z","ddc":["000","005"],"corr_author":"1","has_accepted_license":"1","ec_funded":1,"volume":5710,"page":"244 - 258","quality_controlled":"1","title":"Probabilistic weighted automata","language":[{"iso":"eng"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"}],"status":"public","intvolume":"      5710"},{"month":"01","date_updated":"2021-01-12T07:53:23Z","abstract":[{"text":"We compare anti-parasite defences at the level of multicellular organisms and insect societies, and find that selection by parasites at these two organisational levels is often very similar and has created a number of parallel evolutionary solutions in the host's immune response. The defence mechanisms of both individuals and insect colonies start with border defences to prevent parasite intake and are followed by soma defences that prevent the establishment and spread of the parasite between the body's cells or the social insect workers. Lastly, germ line defences are employed to inhibit infection of the reproductive tissue of organisms or the reproductive individuals in colonies. We further find sophisticated self/non-self-recognition systems operating at both levels, which appear to be vital in maintaining the integrity of the body or colony as a reproductive entity. We then expand on the regulation of immune responses and end with a contemplation of how evolution may shape the different immune components, both within and between levels. The aim of this review is to highlight common evolutionary principles acting in disease defence at the level of both individual organisms and societies, thereby linking the fields of physiological and ecological immunology.","lang":"eng"}],"year":"2009","extern":"1","volume":364,"publisher":"Royal Society, The","date_published":"2009-01-12T00:00:00Z","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2666697/","open_access":"1"}],"date_created":"2018-12-11T12:06:02Z","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"None","status":"public","doi":"10.1098/rstb.2008.0166","intvolume":"       364","type":"journal_article","citation":{"ieee":"S. Cremer and M. K. Sixt, “Analogies in the evolution of individual and social immunity,” <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>, vol. 364, no. 1513. Royal Society, The, pp. 129–142, 2009.","chicago":"Cremer, Sylvia, and Michael K Sixt. “Analogies in the Evolution of Individual and Social Immunity.” <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>. Royal Society, The, 2009. <a href=\"https://doi.org/10.1098/rstb.2008.0166\">https://doi.org/10.1098/rstb.2008.0166</a>.","short":"S. Cremer, M.K. Sixt, Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences 364 (2009) 129–142.","mla":"Cremer, Sylvia, and Michael K. Sixt. “Analogies in the Evolution of Individual and Social Immunity.” <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>, vol. 364, no. 1513, Royal Society, The, 2009, pp. 129–42, doi:<a href=\"https://doi.org/10.1098/rstb.2008.0166\">10.1098/rstb.2008.0166</a>.","ama":"Cremer S, Sixt MK. Analogies in the evolution of individual and social immunity. <i>Philosophical Transactions of the Royal Society of London Series B, Biological Sciences</i>. 2009;364(1513):129-142. doi:<a href=\"https://doi.org/10.1098/rstb.2008.0166\">10.1098/rstb.2008.0166</a>","apa":"Cremer, S., &#38; Sixt, M. K. (2009). Analogies in the evolution of individual and social immunity. <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.2008.0166\">https://doi.org/10.1098/rstb.2008.0166</a>","ista":"Cremer S, Sixt MK. 2009. Analogies in the evolution of individual and social immunity. Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences. 364(1513), 129–142."},"author":[{"last_name":"Cremer","orcid":"0000-0002-2193-3868","first_name":"Sylvia","full_name":"Cremer, Sylvia","id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87"},{"id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","last_name":"Sixt","orcid":"0000-0002-6620-9179","full_name":"Sixt, Michael K","first_name":"Michael K"}],"language":[{"iso":"eng"}],"oa":1,"title":"Analogies in the evolution of individual and social immunity","publication":"Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences","issue":"1513","page":"129 - 142","publist_id":"2181","_id":"3946","day":"12"}]