[{"day":"26","publication":"BMC Plant Biology","has_accepted_license":"1","year":"2012","date_published":"2012-07-26T00:00:00Z","doi":"10.1186/1471-2229-12-116","date_created":"2018-12-11T11:46:46Z","quality_controlled":"1","publisher":"BioMed Central","oa":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Galkovskyi, Taras, et al. “GiA Roots: Software for the High Throughput Analysis of Plant Root System Architecture.” BMC Plant Biology, vol. 12, 116, BioMed Central, 2012, doi:10.1186/1471-2229-12-116.","apa":"Galkovskyi, T., Mileyko, Y., Bucksch, A., Moore, B., Symonova, O., Price, C., … Weitz, J. (2012). GiA Roots: Software for the high throughput analysis of plant root system architecture. BMC Plant Biology. BioMed Central. https://doi.org/10.1186/1471-2229-12-116","ama":"Galkovskyi T, Mileyko Y, Bucksch A, et al. GiA Roots: Software for the high throughput analysis of plant root system architecture. BMC Plant Biology. 2012;12. doi:10.1186/1471-2229-12-116","short":"T. Galkovskyi, Y. Mileyko, A. Bucksch, B. Moore, O. Symonova, C. Price, C. Topp, A. Iyer Pascuzzi, P. Zurek, S. Fang, J. Harer, P. Benfey, J. Weitz, BMC Plant Biology 12 (2012).","ieee":"T. Galkovskyi et al., “GiA Roots: Software for the high throughput analysis of plant root system architecture,” BMC Plant Biology, vol. 12. BioMed Central, 2012.","chicago":"Galkovskyi, Taras, Yuriy Mileyko, Alexander Bucksch, Brad Moore, Olga Symonova, Charles Price, Chrostopher Topp, et al. “GiA Roots: Software for the High Throughput Analysis of Plant Root System Architecture.” BMC Plant Biology. BioMed Central, 2012. https://doi.org/10.1186/1471-2229-12-116.","ista":"Galkovskyi T, Mileyko Y, Bucksch A, Moore B, Symonova O, Price C, Topp C, Iyer Pascuzzi A, Zurek P, Fang S, Harer J, Benfey P, Weitz J. 2012. GiA Roots: Software for the high throughput analysis of plant root system architecture. BMC Plant Biology. 12, 116."},"title":"GiA Roots: Software for the high throughput analysis of plant root system architecture","publist_id":"7328","author":[{"full_name":"Galkovskyi, Taras","last_name":"Galkovskyi","first_name":"Taras"},{"first_name":"Yuriy","full_name":"Mileyko, Yuriy","last_name":"Mileyko"},{"first_name":"Alexander","last_name":"Bucksch","full_name":"Bucksch, Alexander"},{"first_name":"Brad","last_name":"Moore","full_name":"Moore, Brad"},{"id":"3C0C7BC6-F248-11E8-B48F-1D18A9856A87","first_name":"Olga","last_name":"Symonova","full_name":"Symonova, Olga"},{"first_name":"Charles","full_name":"Price, Charles","last_name":"Price"},{"full_name":"Topp, Chrostopher","last_name":"Topp","first_name":"Chrostopher"},{"last_name":"Iyer Pascuzzi","full_name":"Iyer Pascuzzi, Anjali","first_name":"Anjali"},{"full_name":"Zurek, Paul","last_name":"Zurek","first_name":"Paul"},{"full_name":"Fang, Suqin","last_name":"Fang","first_name":"Suqin"},{"first_name":"John","last_name":"Harer","full_name":"Harer, John"},{"first_name":"Philip","last_name":"Benfey","full_name":"Benfey, Philip"},{"first_name":"Joshua","last_name":"Weitz","full_name":"Weitz, Joshua"}],"article_processing_charge":"No","article_number":"116","file":[{"creator":"system","file_size":1691436,"date_updated":"2020-07-14T12:46:35Z","file_name":"IST-2018-946-v1+1_2012_Symonova_GiA_Roots.pdf","date_created":"2018-12-12T10:12:35Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"4953","checksum":"0c629e36acd5f2878ff7dd088d67d494"}],"language":[{"iso":"eng"}],"publication_status":"published","volume":12,"oa_version":"Published Version","abstract":[{"lang":"eng","text":"Background: Characterizing root system architecture (RSA) is essential to understanding the development and function of vascular plants. Identifying RSA-associated genes also represents an underexplored opportunity for crop improvement. Software tools are needed to accelerate the pace at which quantitative traits of RSA are estimated from images of root networks.Results: We have developed GiA Roots (General Image Analysis of Roots), a semi-automated software tool designed specifically for the high-throughput analysis of root system images. GiA Roots includes user-assisted algorithms to distinguish root from background and a fully automated pipeline that extracts dozens of root system phenotypes. Quantitative information on each phenotype, along with intermediate steps for full reproducibility, is returned to the end-user for downstream analysis. GiA Roots has a GUI front end and a command-line interface for interweaving the software into large-scale workflows. GiA Roots can also be extended to estimate novel phenotypes specified by the end-user.Conclusions: We demonstrate the use of GiA Roots on a set of 2393 images of rice roots representing 12 genotypes from the species Oryza sativa. We validate trait measurements against prior analyses of this image set that demonstrated that RSA traits are likely heritable and associated with genotypic differences. Moreover, we demonstrate that GiA Roots is extensible and an end-user can add functionality so that GiA Roots can estimate novel RSA traits. In summary, we show that the software can function as an efficient tool as part of a workflow to move from large numbers of root images to downstream analysis."}],"month":"07","intvolume":" 12","scopus_import":"1","extern":"1","ddc":["005","514","516"],"date_updated":"2022-08-25T14:59:17Z","file_date_updated":"2020-07-14T12:46:35Z","_id":"492","status":"public","pubrep_id":"946","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"}},{"_id":"493","status":"public","pubrep_id":"945","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["004"],"date_updated":"2021-01-12T08:01:03Z","file_date_updated":"2020-07-14T12:46:35Z","department":[{"_id":"ScienComp"},{"_id":"PeJo"}],"oa_version":"Published Version","abstract":[{"text":"The BCI competition IV stands in the tradition of prior BCI competitions that aim to provide high quality neuroscientific data for open access to the scientific community. As experienced already in prior competitions not only scientists from the narrow field of BCI compete, but scholars with a broad variety of backgrounds and nationalities. They include high specialists as well as students.The goals of all BCI competitions have always been to challenge with respect to novel paradigms and complex data. We report on the following challenges: (1) asynchronous data, (2) synthetic, (3) multi-class continuous data, (4) sessionto-session transfer, (5) directionally modulated MEG, (6) finger movements recorded by ECoG. As after past competitions, our hope is that winning entries may enhance the analysis methods of future BCIs.","lang":"eng"}],"month":"07","intvolume":" 6","scopus_import":1,"file":[{"creator":"system","date_updated":"2020-07-14T12:46:35Z","file_size":2693701,"date_created":"2018-12-12T10:18:34Z","file_name":"IST-2018-945-v1+1_2012_Schloegl_Review_of.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"5356","checksum":"195238221c4b0b0f4035f6f6c16ea17c"}],"language":[{"iso":"eng"}],"publication_status":"published","volume":6,"article_number":"55","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Tangermann, Michael, et al. “Review of the BCI Competition IV.” Frontiers in Neuroscience, vol. 6, 55, Frontiers Research Foundation, 2012, doi:10.3389/fnins.2012.00055.","apa":"Tangermann, M., Müller, K., Aertsen, A., Birbaumer, N., Braun, C., Brunner, C., … Blankertz, B. (2012). Review of the BCI competition IV. Frontiers in Neuroscience. Frontiers Research Foundation. https://doi.org/10.3389/fnins.2012.00055","ama":"Tangermann M, Müller K, Aertsen A, et al. Review of the BCI competition IV. Frontiers in Neuroscience. 2012;6. doi:10.3389/fnins.2012.00055","short":"M. Tangermann, K. Müller, A. Aertsen, N. Birbaumer, C. Braun, C. Brunner, R. Leeb, C. Mehring, K. Miller, G. Müller Putz, G. Nolte, G. Pfurtscheller, H. Preissl, G. Schalk, A. Schlögl, C. Vidaurre, S. Waldert, B. Blankertz, Frontiers in Neuroscience 6 (2012).","ieee":"M. Tangermann et al., “Review of the BCI competition IV,” Frontiers in Neuroscience, vol. 6. Frontiers Research Foundation, 2012.","chicago":"Tangermann, Michael, Klaus Müller, Ad Aertsen, Niels Birbaumer, Christoph Braun, Clemens Brunner, Robert Leeb, et al. “Review of the BCI Competition IV.” Frontiers in Neuroscience. Frontiers Research Foundation, 2012. https://doi.org/10.3389/fnins.2012.00055.","ista":"Tangermann M, Müller K, Aertsen A, Birbaumer N, Braun C, Brunner C, Leeb R, Mehring C, Miller K, Müller Putz G, Nolte G, Pfurtscheller G, Preissl H, Schalk G, Schlögl A, Vidaurre C, Waldert S, Blankertz B. 2012. Review of the BCI competition IV. Frontiers in Neuroscience. 6, 55."},"title":"Review of the BCI competition IV","publist_id":"7327","author":[{"full_name":"Tangermann, Michael","last_name":"Tangermann","first_name":"Michael"},{"first_name":"Klaus","full_name":"Müller, Klaus","last_name":"Müller"},{"first_name":"Ad","full_name":"Aertsen, Ad","last_name":"Aertsen"},{"first_name":"Niels","full_name":"Birbaumer, Niels","last_name":"Birbaumer"},{"full_name":"Braun, Christoph","last_name":"Braun","first_name":"Christoph"},{"full_name":"Brunner, Clemens","last_name":"Brunner","first_name":"Clemens"},{"full_name":"Leeb, Robert","last_name":"Leeb","first_name":"Robert"},{"full_name":"Mehring, Carsten","last_name":"Mehring","first_name":"Carsten"},{"first_name":"Kai","full_name":"Miller, Kai","last_name":"Miller"},{"first_name":"Gernot","full_name":"Müller Putz, Gernot","last_name":"Müller Putz"},{"full_name":"Nolte, Guido","last_name":"Nolte","first_name":"Guido"},{"last_name":"Pfurtscheller","full_name":"Pfurtscheller, Gert","first_name":"Gert"},{"full_name":"Preissl, Hubert","last_name":"Preissl","first_name":"Hubert"},{"first_name":"Gerwin","full_name":"Schalk, Gerwin","last_name":"Schalk"},{"id":"45BF87EE-F248-11E8-B48F-1D18A9856A87","first_name":"Alois","last_name":"Schlögl","full_name":"Schlögl, Alois","orcid":"0000-0002-5621-8100"},{"first_name":"Carmen","last_name":"Vidaurre","full_name":"Vidaurre, Carmen"},{"full_name":"Waldert, Stephan","last_name":"Waldert","first_name":"Stephan"},{"first_name":"Benjamin","full_name":"Blankertz, Benjamin","last_name":"Blankertz"}],"acknowledgement":"The studies were in part or completely supported by the Bundesministerium für Bildung und Forschung (BMBF), Fkz 01IB001A, 01GQ0850, by the German Science Foundation (DFG, contract MU 987/3-2), by the European ICT Programme Projects FP7-224631 and 216886, the World Class University Program through the National Research Foundation of Korea funded by the Ministry of Education, Science, and Technology (Grant R31-10008), the US Army Research Office [W911NF-08-1-0216 (Gerwin Schalk) and W911NF-07-1-0415 (Gerwin Schalk)] and the NIH [EB006356 (Gerwin Schalk) and EB000856 (Gerwin Schalk), the WIN-Kolleg of the Heidelberg Academy of Sciences and Humanities, German Federal Ministry of Education and Research grants 01GQ0420, 01GQ0761, 01GQ0762, and 01GQ0830, German Research Foundation grants 550/B5 and C6, and by a scholarship from the German National Academic Foundation. This paper only reflects the authors’ views and funding agencies are not liable for any use that may be made of the information contained herein.\r\n","quality_controlled":"1","publisher":"Frontiers Research Foundation","oa":1,"day":"13","publication":"Frontiers in Neuroscience","has_accepted_license":"1","year":"2012","date_published":"2012-07-13T00:00:00Z","doi":"10.3389/fnins.2012.00055","date_created":"2018-12-11T11:46:46Z"},{"project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"publist_id":"7325","author":[{"first_name":"Alex","full_name":"Kruckman, Alex","last_name":"Kruckman"},{"first_name":"Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","full_name":"Rubin, Sasha","last_name":"Rubin"},{"first_name":"John","last_name":"Sheridan","full_name":"Sheridan, John"},{"first_name":"Ben","full_name":"Zax, Ben","last_name":"Zax"}],"title":"A Myhill Nerode theorem for automata with advice","citation":{"apa":"Kruckman, A., Rubin, S., Sheridan, J., & Zax, B. (2012). A Myhill Nerode theorem for automata with advice. In Proceedings GandALF 2012 (Vol. 96, pp. 238–246). Napoli, Italy: Open Publishing Association. https://doi.org/10.4204/EPTCS.96.18","ama":"Kruckman A, Rubin S, Sheridan J, Zax B. A Myhill Nerode theorem for automata with advice. In: Proceedings GandALF 2012. Vol 96. Open Publishing Association; 2012:238-246. doi:10.4204/EPTCS.96.18","short":"A. Kruckman, S. Rubin, J. Sheridan, B. Zax, in:, Proceedings GandALF 2012, Open Publishing Association, 2012, pp. 238–246.","ieee":"A. Kruckman, S. Rubin, J. Sheridan, and B. Zax, “A Myhill Nerode theorem for automata with advice,” in Proceedings GandALF 2012, Napoli, Italy, 2012, vol. 96, pp. 238–246.","mla":"Kruckman, Alex, et al. “A Myhill Nerode Theorem for Automata with Advice.” Proceedings GandALF 2012, vol. 96, Open Publishing Association, 2012, pp. 238–46, doi:10.4204/EPTCS.96.18.","ista":"Kruckman A, Rubin S, Sheridan J, Zax B. 2012. A Myhill Nerode theorem for automata with advice. Proceedings GandALF 2012. GandALF: Games, Automata, Logics and Formal Verification, EPTCS, vol. 96, 238–246.","chicago":"Kruckman, Alex, Sasha Rubin, John Sheridan, and Ben Zax. “A Myhill Nerode Theorem for Automata with Advice.” In Proceedings GandALF 2012, 96:238–46. Open Publishing Association, 2012. https://doi.org/10.4204/EPTCS.96.18."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa":1,"publisher":"Open Publishing Association","quality_controlled":"1","page":"238 - 246","date_created":"2018-12-11T11:46:47Z","date_published":"2012-10-07T00:00:00Z","doi":"10.4204/EPTCS.96.18","year":"2012","has_accepted_license":"1","publication":"Proceedings GandALF 2012","day":"07","conference":{"location":"Napoli, Italy","end_date":"2012-09-08","start_date":"2012-09-06","name":"GandALF: Games, Automata, Logics and Formal Verification"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"conference","pubrep_id":"944","status":"public","_id":"495","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:35Z","date_updated":"2021-01-12T08:01:04Z","ddc":["004"],"scopus_import":1,"alternative_title":["EPTCS"],"intvolume":" 96","month":"10","abstract":[{"text":"An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.","lang":"eng"}],"oa_version":"Published Version","ec_funded":1,"volume":96,"publication_status":"published","language":[{"iso":"eng"}],"file":[{"checksum":"56277f95edc9d531fa3bdc5f9579fda8","file_id":"5152","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"IST-2018-944-v1+1_2012_Rubin_A_Myhill.pdf","date_created":"2018-12-12T10:15:31Z","file_size":97736,"date_updated":"2020-07-14T12:46:35Z","creator":"system"}]},{"date_created":"2018-12-11T11:46:48Z","date_published":"2012-12-01T00:00:00Z","doi":"10.1111/j.1752-4571.2012.00284.x","page":"913 - 924","publication":"Evolutionary Applications","day":"01","year":"2012","has_accepted_license":"1","oa":1,"quality_controlled":"1","publisher":"Wiley-Blackwell","acknowledgement":"We thank Graham Pickup, David Steer, Linda Broadhurst, Lan Li and Carole Elliott for technical assistance. The New\r\nSouth Wales Department of Environment and Climate Change, ACT Parks, Conservation and Lands and the\r\nDepartment of Sustainability and Environment in Victoria provided permits for seed and soil collection. We thank\r\nSpencer C. H. Barrett for comments that improved the quality of the manuscript.\r\n","title":"Predicting local adaptation in fragmented plant populations: Implications for restoration genetics","author":[{"last_name":"Pickup","full_name":"Pickup, Melinda","orcid":"0000-0001-6118-0541","first_name":"Melinda","id":"2C78037E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"David","id":"419049E2-F248-11E8-B48F-1D18A9856A87","full_name":"Field, David","orcid":"0000-0002-4014-8478","last_name":"Field"},{"last_name":"Rowell","full_name":"Rowell, David","first_name":"David"},{"last_name":"Young","full_name":"Young, Andrew","first_name":"Andrew"}],"publist_id":"7322","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Pickup, M., Field, D., Rowell, D., & Young, A. (2012). Predicting local adaptation in fragmented plant populations: Implications for restoration genetics. Evolutionary Applications. Wiley-Blackwell. https://doi.org/10.1111/j.1752-4571.2012.00284.x","ama":"Pickup M, Field D, Rowell D, Young A. Predicting local adaptation in fragmented plant populations: Implications for restoration genetics. Evolutionary Applications. 2012;5(8):913-924. doi:10.1111/j.1752-4571.2012.00284.x","short":"M. Pickup, D. Field, D. Rowell, A. Young, Evolutionary Applications 5 (2012) 913–924.","ieee":"M. Pickup, D. Field, D. Rowell, and A. Young, “Predicting local adaptation in fragmented plant populations: Implications for restoration genetics,” Evolutionary Applications, vol. 5, no. 8. Wiley-Blackwell, pp. 913–924, 2012.","mla":"Pickup, Melinda, et al. “Predicting Local Adaptation in Fragmented Plant Populations: Implications for Restoration Genetics.” Evolutionary Applications, vol. 5, no. 8, Wiley-Blackwell, 2012, pp. 913–24, doi:10.1111/j.1752-4571.2012.00284.x.","ista":"Pickup M, Field D, Rowell D, Young A. 2012. Predicting local adaptation in fragmented plant populations: Implications for restoration genetics. Evolutionary Applications. 5(8), 913–924.","chicago":"Pickup, Melinda, David Field, David Rowell, and Andrew Young. “Predicting Local Adaptation in Fragmented Plant Populations: Implications for Restoration Genetics.” Evolutionary Applications. Wiley-Blackwell, 2012. https://doi.org/10.1111/j.1752-4571.2012.00284.x."},"license":"https://creativecommons.org/licenses/by-nc/4.0/","volume":5,"issue":"8","language":[{"iso":"eng"}],"file":[{"creator":"system","file_size":396136,"date_updated":"2020-07-14T12:46:35Z","file_name":"IST-2018-942-v1+1_Pickup_et_al-2012-Evolutionary_Applications.pdf","date_created":"2018-12-12T10:10:33Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"4821","checksum":"233007138606aca5a2f75f7ae1742f43"}],"publication_status":"published","intvolume":" 5","month":"12","oa_version":"Published Version","abstract":[{"text":"Understanding patterns and correlates of local adaptation in heterogeneous landscapes can provide important information in the selection of appropriate seed sources for restoration. We assessed the extent of local adaptation of fitness components in 12 population pairs of the perennial herb Rutidosis leptorrhynchoides (Asteraceae) and examined whether spatial scale (0.7-600 km), environmental distance, quantitative (QST) and neutral (FST) genetic differentiation, and size of the local and foreign populations could predict patterns of adaptive differentiation. Local adaptation varied among populations and fitness components. Including all population pairs, local adaptation was observed for seedling survival, but not for biomass, while foreign genotype advantage was observed for reproduction (number of inflorescences). Among population pairs, local adaptation increased with QST and local population size for biomass. QST was associated with environmental distance, suggesting ecological selection for phenotypic divergence. However, low FST and variation in population structure in small populations demonstrates the interaction of gene flow and drift in constraining local adaptation in R. leptorrhynchoides. Our study indicates that for species in heterogeneous landscapes, collecting seed from large populations from similar environments to candidate sites is likely to provide the most appropriate seed sources for restoration.","lang":"eng"}],"department":[{"_id":"NiBa"}],"file_date_updated":"2020-07-14T12:46:35Z","ddc":["576"],"date_updated":"2021-01-12T08:01:06Z","pubrep_id":"942","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)"},"type":"journal_article","_id":"498"},{"_id":"496","article_number":"6280474","conference":{"location":"Dubrovnik, Croatia","end_date":"2012-06-28","start_date":"2012-06-25","name":"LICS: Symposium on Logic in Computer Science"},"type":"conference","status":"public","project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"date_updated":"2021-01-12T08:01:05Z","citation":{"short":"A. Rabinovich, S. Rubin, in:, IEEE, 2012.","ieee":"A. Rabinovich and S. Rubin, “Interpretations in trees with countably many branches,” presented at the LICS: Symposium on Logic in Computer Science, Dubrovnik, Croatia, 2012.","apa":"Rabinovich, A., & Rubin, S. (2012). Interpretations in trees with countably many branches. Presented at the LICS: Symposium on Logic in Computer Science, Dubrovnik, Croatia: IEEE. https://doi.org/10.1109/LICS.2012.65","ama":"Rabinovich A, Rubin S. Interpretations in trees with countably many branches. In: IEEE; 2012. doi:10.1109/LICS.2012.65","mla":"Rabinovich, Alexander, and Sasha Rubin. Interpretations in Trees with Countably Many Branches. 6280474, IEEE, 2012, doi:10.1109/LICS.2012.65.","ista":"Rabinovich A, Rubin S. 2012. Interpretations in trees with countably many branches. LICS: Symposium on Logic in Computer Science, LICS, , 6280474.","chicago":"Rabinovich, Alexander, and Sasha Rubin. “Interpretations in Trees with Countably Many Branches.” IEEE, 2012. https://doi.org/10.1109/LICS.2012.65."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Alexander","last_name":"Rabinovich","full_name":"Rabinovich, Alexander"},{"first_name":"Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","last_name":"Rubin","full_name":"Rubin, Sasha"}],"publist_id":"7324","title":"Interpretations in trees with countably many branches","department":[{"_id":"KrCh"}],"abstract":[{"lang":"eng","text":"We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations."}],"oa_version":"Preprint","oa":1,"main_file_link":[{"url":"https://arise.or.at/pubpdf/Interpretations_in_Trees_with_Countably_Many_Branches.pdf","open_access":"1"}],"alternative_title":["LICS"],"publisher":"IEEE","scopus_import":1,"quality_controlled":"1","month":"01","year":"2012","publication_status":"published","language":[{"iso":"eng"}],"day":"01","date_created":"2018-12-11T11:46:47Z","ec_funded":1,"date_published":"2012-01-01T00:00:00Z","doi":"10.1109/LICS.2012.65"},{"publication_status":"published","year":"2012","language":[{"iso":"eng"}],"publication":"ACM Transactions on Computational Logic (TOCL)","day":"01","date_created":"2018-12-11T11:46:47Z","issue":"4","doi":"10.1145/2362355.2362357","date_published":"2012-10-01T00:00:00Z","volume":13,"abstract":[{"text":"We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is 2o(nlog n) and the lower bound is 1.5n. We improve the upper bound to n2n and describe a matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We continue and solve the open problems of translating nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to DCW. Going via an intermediate NBW is not optimal and we describe direct, simple, and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions are variants of the subset construction, providing a unified approach for translating all common classes of automata to NCW and DCW. Beyond the theoretical importance of the results, we point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation, when possible, of LTL to deterministic Büchi word automata.","lang":"eng"}],"oa_version":"None","publisher":"ACM","scopus_import":1,"quality_controlled":"1","intvolume":" 13","month":"10","date_updated":"2021-01-12T08:01:03Z","citation":{"short":"U. Boker, O. Kupferman, ACM Transactions on Computational Logic (TOCL) 13 (2012).","ieee":"U. Boker and O. Kupferman, “Translating to Co-Büchi made tight, unified, and useful,” ACM Transactions on Computational Logic (TOCL), vol. 13, no. 4. ACM, 2012.","apa":"Boker, U., & Kupferman, O. (2012). Translating to Co-Büchi made tight, unified, and useful. ACM Transactions on Computational Logic (TOCL). ACM. https://doi.org/10.1145/2362355.2362357","ama":"Boker U, Kupferman O. Translating to Co-Büchi made tight, unified, and useful. ACM Transactions on Computational Logic (TOCL). 2012;13(4). doi:10.1145/2362355.2362357","mla":"Boker, Udi, and Orna Kupferman. “Translating to Co-Büchi Made Tight, Unified, and Useful.” ACM Transactions on Computational Logic (TOCL), vol. 13, no. 4, 29, ACM, 2012, doi:10.1145/2362355.2362357.","ista":"Boker U, Kupferman O. 2012. Translating to Co-Büchi made tight, unified, and useful. ACM Transactions on Computational Logic (TOCL). 13(4), 29.","chicago":"Boker, Udi, and Orna Kupferman. “Translating to Co-Büchi Made Tight, Unified, and Useful.” ACM Transactions on Computational Logic (TOCL). ACM, 2012. https://doi.org/10.1145/2362355.2362357."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"id":"31E297B6-F248-11E8-B48F-1D18A9856A87","first_name":"Udi","full_name":"Boker, Udi","last_name":"Boker"},{"full_name":"Kupferman, Orna","last_name":"Kupferman","first_name":"Orna"}],"publist_id":"7326","department":[{"_id":"ToHe"}],"title":"Translating to Co-Büchi made tight, unified, and useful","_id":"494","article_number":"29","type":"journal_article","status":"public"},{"citation":{"ama":"Sixt MK. Cell migration: Fibroblasts find a new way to get ahead. Journal of Cell Biology. 2012;197(3):347-349. doi:10.1083/jcb.201204039","apa":"Sixt, M. K. (2012). Cell migration: Fibroblasts find a new way to get ahead. Journal of Cell Biology. Rockefeller University Press. https://doi.org/10.1083/jcb.201204039","short":"M.K. Sixt, Journal of Cell Biology 197 (2012) 347–349.","ieee":"M. K. Sixt, “Cell migration: Fibroblasts find a new way to get ahead,” Journal of Cell Biology, vol. 197, no. 3. Rockefeller University Press, pp. 347–349, 2012.","mla":"Sixt, Michael K. “Cell Migration: Fibroblasts Find a New Way to Get Ahead.” Journal of Cell Biology, vol. 197, no. 3, Rockefeller University Press, 2012, pp. 347–49, doi:10.1083/jcb.201204039.","ista":"Sixt MK. 2012. Cell migration: Fibroblasts find a new way to get ahead. Journal of Cell Biology. 197(3), 347–349.","chicago":"Sixt, Michael K. “Cell Migration: Fibroblasts Find a New Way to Get Ahead.” Journal of Cell Biology. Rockefeller University Press, 2012. https://doi.org/10.1083/jcb.201204039."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"7314","author":[{"orcid":"0000-0002-6620-9179","full_name":"Sixt, Michael K","last_name":"Sixt","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","first_name":"Michael K"}],"article_processing_charge":"No","title":"Cell migration: Fibroblasts find a new way to get ahead","quality_controlled":"1","publisher":"Rockefeller University Press","oa":1,"has_accepted_license":"1","year":"2012","day":"30","publication":"Journal of Cell Biology","page":"347 - 349","date_published":"2012-04-30T00:00:00Z","doi":"10.1083/jcb.201204039","date_created":"2018-12-11T11:46:51Z","_id":"506","article_type":"original","type":"journal_article","tmp":{"name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","image":"/images/cc_by_nc_sa.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","short":"CC BY-NC-SA (4.0)"},"status":"public","date_updated":"2021-01-12T08:01:11Z","ddc":["570"],"department":[{"_id":"MiSi"}],"file_date_updated":"2020-07-14T12:46:36Z","oa_version":"Published Version","scopus_import":1,"month":"04","intvolume":" 197","publication_status":"published","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"45c02be33ebd99fc3077d60b9c90bdfa","file_id":"5957","creator":"kschuh","date_updated":"2020-07-14T12:46:36Z","file_size":986566,"date_created":"2019-02-12T09:03:09Z","file_name":"2012_CellBiology_Sixt.pdf"}],"language":[{"iso":"eng"}],"issue":"3","volume":197,"license":"https://creativecommons.org/licenses/by-nc-sa/4.0/"},{"date_created":"2018-12-11T11:46:48Z","doi":"10.4230/LIPIcs.CSL.2012.167","date_published":"2012-09-01T00:00:00Z","page":"167 - 182","day":"01","year":"2012","has_accepted_license":"1","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","title":"Faster algorithms for alternating refinement relations","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Siddhesh","last_name":"Chaubal","full_name":"Chaubal, Siddhesh"},{"last_name":"Kamath","full_name":"Kamath, Pritish","first_name":"Pritish"}],"publist_id":"7323","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Chatterjee K, Chaubal S, Kamath P. 2012. Faster algorithms for alternating refinement relations. EACSL: European Association for Computer Science Logic, LIPIcs, vol. 16, 167–182.","chicago":"Chatterjee, Krishnendu, Siddhesh Chaubal, and Pritish Kamath. “Faster Algorithms for Alternating Refinement Relations,” 16:167–82. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. https://doi.org/10.4230/LIPIcs.CSL.2012.167.","ieee":"K. Chatterjee, S. Chaubal, and P. Kamath, “Faster algorithms for alternating refinement relations,” presented at the EACSL: European Association for Computer Science Logic, Fontainebleau, France, 2012, vol. 16, pp. 167–182.","short":"K. Chatterjee, S. Chaubal, P. Kamath, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 167–182.","apa":"Chatterjee, K., Chaubal, S., & Kamath, P. (2012). Faster algorithms for alternating refinement relations (Vol. 16, pp. 167–182). Presented at the EACSL: European Association for Computer Science Logic, Fontainebleau, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CSL.2012.167","ama":"Chatterjee K, Chaubal S, Kamath P. Faster algorithms for alternating refinement relations. In: Vol 16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2012:167-182. doi:10.4230/LIPIcs.CSL.2012.167","mla":"Chatterjee, Krishnendu, et al. Faster Algorithms for Alternating Refinement Relations. Vol. 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 167–82, doi:10.4230/LIPIcs.CSL.2012.167."},"project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"ec_funded":1,"volume":16,"related_material":{"record":[{"id":"5378","status":"public","relation":"earlier_version"}]},"language":[{"iso":"eng"}],"file":[{"checksum":"f1b0dd99240800db2d7dbf9b5131fe5e","file_id":"4712","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"IST-2018-943-v1+1_2012_Chatterjee_Faster_Algorithms.pdf","date_created":"2018-12-12T10:08:50Z","file_size":471236,"date_updated":"2020-07-14T12:46:35Z","creator":"system"}],"publication_status":"published","intvolume":" 16","month":"09","scopus_import":1,"alternative_title":["LIPIcs"],"oa_version":"Published Version","abstract":[{"lang":"eng","text":"One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. © Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath."}],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:35Z","ddc":["004"],"date_updated":"2023-02-23T12:23:32Z","pubrep_id":"943","status":"public","conference":{"end_date":"2012-09-06","location":"Fontainebleau, France","start_date":"2012-09-03","name":"EACSL: European Association for Computer Science Logic"},"tmp":{"short":"CC BY-NC-ND (4.0)","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","image":"/images/cc_by_nc_nd.png"},"type":"conference","_id":"497"},{"project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chatterjee, Krishnendu, and Monika H Henzinger. “An O(N2) Time Algorithm for Alternating Büchi Games.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 1386–99. SIAM, 2012. https://doi.org/10.1137/1.9781611973099.109.","ista":"Chatterjee K, Henzinger MH. 2012. An O(n2) time algorithm for alternating Büchi games. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1386–1399.","mla":"Chatterjee, Krishnendu, and Monika H. Henzinger. “An O(N2) Time Algorithm for Alternating Büchi Games.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, pp. 1386–99, doi:10.1137/1.9781611973099.109.","apa":"Chatterjee, K., & Henzinger, M. H. (2012). An O(n2) time algorithm for alternating Büchi games. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1386–1399). Kyoto, Japan: SIAM. https://doi.org/10.1137/1.9781611973099.109","ama":"Chatterjee K, Henzinger MH. An O(n2) time algorithm for alternating Büchi games. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM; 2012:1386-1399. doi:10.1137/1.9781611973099.109","short":"K. Chatterjee, M.H. Henzinger, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, pp. 1386–1399.","ieee":"K. Chatterjee and M. H. Henzinger, “An O(n2) time algorithm for alternating Büchi games,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan, 2012, pp. 1386–1399."},"title":"An O(n2) time algorithm for alternating Büchi games","publist_id":"3519","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"}],"external_id":{"arxiv":["1109.5018"]},"article_processing_charge":"No","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, Vienna Science and Technology Fund (WWTF) Grant ICT10-002, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","quality_controlled":"1","publisher":"SIAM","oa":1,"day":"01","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","year":"2012","date_published":"2012-01-01T00:00:00Z","doi":"10.1137/1.9781611973099.109","date_created":"2018-12-11T12:01:46Z","page":"1386 - 1399","_id":"3165","status":"public","pubrep_id":"15","type":"conference","conference":{"start_date":"2012-01-17","end_date":"2012-01-19","location":"Kyoto, Japan","name":"SODA: Symposium on Discrete Algorithms"},"date_updated":"2023-02-23T12:23:35Z","department":[{"_id":"KrCh"}],"oa_version":"None","abstract":[{"lang":"eng","text":"Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is Õ(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n·m) boundary by presenting a new technique that reduces the running time to O(n 2). This bound also leads to O(n 2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n 3)), and (3) in Markov decision processes (improving for m > n 4/3 an earlier bound of O(min(m 1.5, m·n 2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n 2), which is an improvement over earlier bounds for m > n 4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem."}],"month":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1109.5018"}],"language":[{"iso":"eng"}],"publication_status":"published","related_material":{"record":[{"relation":"later_version","status":"public","id":"2141"},{"relation":"earlier_version","id":"5379","status":"public"}]},"ec_funded":1},{"date_created":"2018-12-11T12:00:32Z","ec_funded":1,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5377"}]},"date_published":"2012-08-23T00:00:00Z","doi":"10.1109/LICS.2012.30","publication_status":"published","year":"2012","language":[{"iso":"eng"}],"publication":"Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science","day":"23","scopus_import":1,"publisher":"IEEE","quality_controlled":"1","month":"08","abstract":[{"text":"Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and parity objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two-player pushdown games. Finally we also show that all the problems have the same computational complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.","lang":"eng"}],"acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), Microsoft faculty fellows award, the Israeli Centers of Research Excellence (ICORE) program, (Center No. 4/11), the RICH Model Toolkit (ICT COST Action IC0901), and was carried out in partial fulfillment of the requirements for the Ph.D. degree of the second author.\r\nA Technical Report of this paper is available via internal link.","oa_version":"None","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"full_name":"Velner, Yaron","last_name":"Velner","first_name":"Yaron"}],"publist_id":"3770","department":[{"_id":"KrCh"}],"title":"Mean payoff pushdown games","citation":{"ama":"Chatterjee K, Velner Y. Mean payoff pushdown games. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE; 2012. doi:10.1109/LICS.2012.30","apa":"Chatterjee, K., & Velner, Y. (2012). Mean payoff pushdown games. In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. Dubrovnik, Croatia : IEEE. https://doi.org/10.1109/LICS.2012.30","short":"K. Chatterjee, Y. Velner, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.","ieee":"K. Chatterjee and Y. Velner, “Mean payoff pushdown games,” in Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, Dubrovnik, Croatia , 2012.","mla":"Chatterjee, Krishnendu, and Yaron Velner. “Mean Payoff Pushdown Games.” Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, 6280438, IEEE, 2012, doi:10.1109/LICS.2012.30.","ista":"Chatterjee K, Velner Y. 2012. Mean payoff pushdown games. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6280438.","chicago":"Chatterjee, Krishnendu, and Yaron Velner. “Mean Payoff Pushdown Games.” In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.30."},"date_updated":"2023-02-23T12:23:30Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2012-06-25","end_date":"2012-06-28","location":"Dubrovnik, Croatia ","name":"LICS: Logic in Computer Science"},"type":"conference","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"status":"public","_id":"2956","article_number":"6280438"},{"pubrep_id":"10","status":"public","type":"technical_report","_id":"5377","file_date_updated":"2020-07-14T12:46:38Z","title":"Mean-payoff pushdown games","department":[{"_id":"KrCh"}],"author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Velner","full_name":"Velner, Yaron","first_name":"Yaron"}],"ddc":["000","005"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T11:05:50Z","citation":{"chicago":"Chatterjee, Krishnendu, and Yaron Velner. Mean-Payoff Pushdown Games. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0002.","ista":"Chatterjee K, Velner Y. 2012. Mean-payoff pushdown games, IST Austria, 33p.","mla":"Chatterjee, Krishnendu, and Yaron Velner. Mean-Payoff Pushdown Games. IST Austria, 2012, doi:10.15479/AT:IST-2012-0002.","apa":"Chatterjee, K., & Velner, Y. (2012). Mean-payoff pushdown games. IST Austria. https://doi.org/10.15479/AT:IST-2012-0002","ama":"Chatterjee K, Velner Y. Mean-Payoff Pushdown Games. IST Austria; 2012. doi:10.15479/AT:IST-2012-0002","ieee":"K. Chatterjee and Y. Velner, Mean-payoff pushdown games. IST Austria, 2012.","short":"K. Chatterjee, Y. Velner, Mean-Payoff Pushdown Games, IST Austria, 2012."},"month":"07","oa":1,"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","oa_version":"Published Version","abstract":[{"lang":"eng","text":"Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and ω-regular objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean-payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two- player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP- hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two- player pushdown games. Finally we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded."}],"date_created":"2018-12-12T11:38:59Z","related_material":{"record":[{"relation":"later_version","id":"2956","status":"public"}]},"doi":"10.15479/AT:IST-2012-0002","date_published":"2012-07-02T00:00:00Z","page":"33","language":[{"iso":"eng"}],"file":[{"date_created":"2018-12-12T11:54:00Z","file_name":"IST-2012-002_IST-2012-0002.pdf","date_updated":"2020-07-14T12:46:38Z","file_size":592098,"creator":"system","file_id":"5522","checksum":"a03c08c1589dbb0c96183a8bcf3ab240","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"day":"02","publication_status":"published","year":"2012","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]}},{"citation":{"ieee":"K. Chatterjee, S. Chaubal, and P. Kamath, Faster algorithms for alternating refinement relations. IST Austria, 2012.","short":"K. Chatterjee, S. Chaubal, P. Kamath, Faster Algorithms for Alternating Refinement Relations, IST Austria, 2012.","apa":"Chatterjee, K., Chaubal, S., & Kamath, P. (2012). Faster algorithms for alternating refinement relations. IST Austria. https://doi.org/10.15479/AT:IST-2012-0001","ama":"Chatterjee K, Chaubal S, Kamath P. Faster Algorithms for Alternating Refinement Relations. IST Austria; 2012. doi:10.15479/AT:IST-2012-0001","mla":"Chatterjee, Krishnendu, et al. Faster Algorithms for Alternating Refinement Relations. IST Austria, 2012, doi:10.15479/AT:IST-2012-0001.","ista":"Chatterjee K, Chaubal S, Kamath P. 2012. Faster algorithms for alternating refinement relations, IST Austria, 21p.","chicago":"Chatterjee, Krishnendu, Siddhesh Chaubal, and Pritish Kamath. Faster Algorithms for Alternating Refinement Relations. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0001."},"date_updated":"2023-02-23T12:21:38Z","ddc":["000","005"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Siddhesh","last_name":"Chaubal","full_name":"Chaubal, Siddhesh"},{"last_name":"Kamath","full_name":"Kamath, Pritish","first_name":"Pritish"}],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:39Z","title":"Faster algorithms for alternating refinement relations","_id":"5378","type":"technical_report","pubrep_id":"14","status":"public","year":"2012","publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","language":[{"iso":"eng"}],"day":"04","file":[{"date_updated":"2020-07-14T12:46:39Z","file_size":394256,"creator":"system","date_created":"2018-12-12T11:53:28Z","file_name":"IST-2012-0001_IST-2012-0001.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"ec8d1857cc7095d3de5107a0162ced37","file_id":"5489"}],"page":"21","date_created":"2018-12-12T11:38:59Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"497"}]},"doi":"10.15479/AT:IST-2012-0001","date_published":"2012-07-04T00:00:00Z","abstract":[{"lang":"eng","text":"One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm."}],"oa_version":"Published Version","oa":1,"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"month":"07"},{"acknowledgement":"This work was partially supported by FWF Grant No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","oa":1,"quality_controlled":"1","publisher":"IEEE","publication":"Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science","day":"23","year":"2012","date_created":"2018-12-11T12:00:32Z","doi":"10.1109/LICS.2012.28","date_published":"2012-08-23T00:00:00Z","article_number":"6280436","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Chatterjee K, Doyen L. 2012. Partial-observation stochastic games: How to win when belief fails. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6280436.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.28.","ieee":"K. Chatterjee and L. Doyen, “Partial-observation stochastic games: How to win when belief fails,” in Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, Dubrovnik, Croatia, 2012.","short":"K. Chatterjee, L. Doyen, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.","ama":"Chatterjee K, Doyen L. Partial-observation stochastic games: How to win when belief fails. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE; 2012. doi:10.1109/LICS.2012.28","apa":"Chatterjee, K., & Doyen, L. (2012). Partial-observation stochastic games: How to win when belief fails. In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. Dubrovnik, Croatia: IEEE. https://doi.org/10.1109/LICS.2012.28","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, 6280436, IEEE, 2012, doi:10.1109/LICS.2012.28."},"title":"Partial-observation stochastic games: How to win when belief fails","external_id":{"arxiv":["1107.2141"]},"publist_id":"3771","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"We consider two-player stochastic games played on finite graphs with reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1), or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two-sided with (c) both players having partial observation. On the basis of randomization, the players (a) may not be allowed to use randomization (pure strategies), or (b) may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) may use full randomization. Our main results for pure strategies are as follows. (1) For one-sided games with player 1 having partial observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almostsure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete. (2) For one-sided games with player 2 having partial observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and positive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least non-elementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibits serious flaws in previous results of the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed."}],"month":"08","main_file_link":[{"url":"http://arxiv.org/abs/1107.2141","open_access":"1"}],"scopus_import":1,"language":[{"iso":"eng"}],"publication_status":"published","ec_funded":1,"related_material":{"record":[{"relation":"later_version","status":"public","id":"2211"},{"status":"public","id":"5381","relation":"earlier_version"}]},"_id":"2955","status":"public","conference":{"name":"LICS: Logic in Computer Science","location":"Dubrovnik, Croatia","end_date":"2012-06-28","start_date":"2012-06-25"},"type":"conference","date_updated":"2023-02-23T12:23:43Z","department":[{"_id":"KrCh"}]},{"status":"public","type":"conference","conference":{"end_date":"2012-04-01","location":"Tallinn, Estonia","start_date":"2012-03-24","name":"FoSSaCS: Foundations of Software Science and Computation Structures"},"_id":"3341","department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:23:46Z","month":"03","intvolume":" 7213","scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1107.2009"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with \\omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal)."}],"volume":7213,"related_material":{"record":[{"relation":"earlier_version","id":"5382","status":"public"}]},"ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"title":"Robustness of structurally equivalent concurrent parity games","publist_id":"3284","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"}],"external_id":{"arxiv":["1107.2009"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Chatterjee, Krishnendu. Robustness of Structurally Equivalent Concurrent Parity Games. Vol. 7213, Springer, 2012, pp. 270–85, doi:10.1007/978-3-642-28729-9_18.","apa":"Chatterjee, K. (2012). Robustness of structurally equivalent concurrent parity games (Vol. 7213, pp. 270–285). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia: Springer. https://doi.org/10.1007/978-3-642-28729-9_18","ama":"Chatterjee K. Robustness of structurally equivalent concurrent parity games. In: Vol 7213. Springer; 2012:270-285. doi:10.1007/978-3-642-28729-9_18","short":"K. Chatterjee, in:, Springer, 2012, pp. 270–285.","ieee":"K. Chatterjee, “Robustness of structurally equivalent concurrent parity games,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia, 2012, vol. 7213, pp. 270–285.","chicago":"Chatterjee, Krishnendu. “Robustness of Structurally Equivalent Concurrent Parity Games,” 7213:270–85. Springer, 2012. https://doi.org/10.1007/978-3-642-28729-9_18.","ista":"Chatterjee K. 2012. Robustness of structurally equivalent concurrent parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 7213, 270–285."},"quality_controlled":"1","publisher":"Springer","oa":1,"date_published":"2012-03-22T00:00:00Z","doi":"10.1007/978-3-642-28729-9_18","date_created":"2018-12-11T12:02:46Z","page":"270 - 285","day":"22","year":"2012"},{"related_material":{"record":[{"relation":"earlier_version","id":"5384","status":"public"}]},"ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","month":"08","scopus_import":1,"main_file_link":[{"url":"https://arxiv.org/abs/1107.2091","open_access":"1"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether words are accepted with probability arbitrarily close to 1. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound."}],"department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:23:51Z","status":"public","type":"conference","conference":{"name":"LICS: Logic in Computer Science","location":"Dubrovnik, Croatia ","end_date":"2012-06-28","start_date":"2012-06-25"},"_id":"2957","date_published":"2012-08-23T00:00:00Z","doi":"10.1109/LICS.2012.29","date_created":"2018-12-11T12:00:33Z","day":"23","publication":"Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science","year":"2012","publisher":"IEEE","quality_controlled":"1","oa":1,"title":"Decidable problems for probabilistic automata on infinite words","publist_id":"3769","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Tracol","full_name":"Tracol, Mathieu","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87","first_name":"Mathieu"}],"external_id":{"arxiv":["1107.2091"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic Automata on Infinite Words.” In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.29.","ista":"Chatterjee K, Tracol M. 2012. Decidable problems for probabilistic automata on infinite words. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6280437.","mla":"Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic Automata on Infinite Words.” Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, 6280437, IEEE, 2012, doi:10.1109/LICS.2012.29.","apa":"Chatterjee, K., & Tracol, M. (2012). Decidable problems for probabilistic automata on infinite words. In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. Dubrovnik, Croatia : IEEE. https://doi.org/10.1109/LICS.2012.29","ama":"Chatterjee K, Tracol M. Decidable problems for probabilistic automata on infinite words. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE; 2012. doi:10.1109/LICS.2012.29","short":"K. Chatterjee, M. Tracol, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.","ieee":"K. Chatterjee and M. Tracol, “Decidable problems for probabilistic automata on infinite words,” in Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, Dubrovnik, Croatia , 2012."},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"article_number":"6280437"},{"quality_controlled":"1","publisher":"Elsevier","acknowledgement":"This work was partially supported by the ERC Advanced Grant QUAREM, the FWF NFN Grant S11402-N23 (RiSE), the European Union project COMBEST and the European Network of Excellence Artist Design.","date_created":"2018-12-11T12:02:15Z","doi":"10.1016/j.tcs.2011.08.002","date_published":"2012-01-06T00:00:00Z","page":"21 - 35","publication":"Theoretical Computer Science","day":"06","year":"2012","project":[{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"name":"COMponent-Based Embedded Systems design Techniques","grant_number":"215543","call_identifier":"FP7","_id":"25EFB36C-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","_id":"25F1337C-B435-11E9-9278-68D0E5697425","name":"Design for Embedded Systems","grant_number":"214373"}],"title":"Simulation distances","author":[{"first_name":"Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","full_name":"Cerny, Pavol","last_name":"Cerny"},{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87","first_name":"Arjun","full_name":"Radhakrishna, Arjun","last_name":"Radhakrishna"}],"publist_id":"3408","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Cerny, Pavol, Thomas A Henzinger, and Arjun Radhakrishna. “Simulation Distances.” Theoretical Computer Science. Elsevier, 2012. https://doi.org/10.1016/j.tcs.2011.08.002.","ista":"Cerny P, Henzinger TA, Radhakrishna A. 2012. Simulation distances. Theoretical Computer Science. 413(1), 21–35.","mla":"Cerny, Pavol, et al. “Simulation Distances.” Theoretical Computer Science, vol. 413, no. 1, Elsevier, 2012, pp. 21–35, doi:10.1016/j.tcs.2011.08.002.","ama":"Cerny P, Henzinger TA, Radhakrishna A. Simulation distances. Theoretical Computer Science. 2012;413(1):21-35. doi:10.1016/j.tcs.2011.08.002","apa":"Cerny, P., Henzinger, T. A., & Radhakrishna, A. (2012). Simulation distances. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2011.08.002","short":"P. Cerny, T.A. Henzinger, A. Radhakrishna, Theoretical Computer Science 413 (2012) 21–35.","ieee":"P. Cerny, T. A. Henzinger, and A. Radhakrishna, “Simulation distances,” Theoretical Computer Science, vol. 413, no. 1. Elsevier, pp. 21–35, 2012."},"intvolume":" 413","month":"01","scopus_import":1,"oa_version":"None","abstract":[{"text":"Boolean notions of correctness are formalized by preorders on systems. Quantitative measures of correctness can be formalized by real-valued distance functions between systems, where the distance between implementation and specification provides a measure of "fit" or "desirability". We extend the simulation preorder to the quantitative setting by making each player of a simulation game pay a certain price for her choices. We use the resulting games with quantitative objectives to define three different simulation distances. The correctness distance measures how much the specification must be changed in order to be satisfied by the implementation. The coverage distance measures how much the implementation restricts the degrees of freedom offered by the specification. The robustness distance measures how much a system can deviate from the implementation description without violating the specification. We consider these distances for safety as well as liveness specifications. The distances can be computed in polynomial time for safety specifications, and for liveness specifications given by weak fairness constraints. We show that the distance functions satisfy the triangle inequality, that the distance between two systems does not increase under parallel composition with a third system, and that the distance between two systems can be bounded from above and below by distances between abstractions of the two systems. These properties suggest that our simulation distances provide an appropriate basis for a quantitative theory of discrete systems. We also demonstrate how the robustness distance can be used to measure how many transmission errors are tolerated by error correcting codes.","lang":"eng"}],"ec_funded":1,"volume":413,"issue":"1","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"4393"},{"status":"public","id":"5389","relation":"earlier_version"}]},"language":[{"iso":"eng"}],"publication_status":"published","pubrep_id":"42","status":"public","type":"journal_article","_id":"3249","department":[{"_id":"ToHe"}],"date_updated":"2023-02-23T12:24:04Z"},{"type":"conference","conference":{"name":"ICML: International Conference on Machine Learning","location":"Edinburgh, Scotland","end_date":"2012-07-01","start_date":"2012-06-26"},"status":"public","pubrep_id":"565","_id":"3124","author":[{"full_name":"Korc, Filip","last_name":"Korc","first_name":"Filip","id":"476A2FD6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","last_name":"Lampert"}],"publist_id":"3575","title":"Approximating marginals using discrete energy minimization","department":[{"_id":"ChLa"},{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:46:00Z","citation":{"mla":"Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization. ICML, 2012.","ama":"Korc F, Kolmogorov V, Lampert C. Approximating marginals using discrete energy minimization. In: ICML; 2012.","apa":"Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals using discrete energy minimization. Presented at the ICML: International Conference on Machine Learning, Edinburgh, Scotland: ICML.","short":"F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012.","ieee":"F. Korc, V. Kolmogorov, and C. Lampert, “Approximating marginals using discrete energy minimization,” presented at the ICML: International Conference on Machine Learning, Edinburgh, Scotland, 2012.","chicago":"Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. “Approximating Marginals Using Discrete Energy Minimization.” ICML, 2012.","ista":"Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization. ICML: International Conference on Machine Learning, Inferning 2012, ."},"date_updated":"2023-02-23T12:24:24Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"alternative_title":["Inferning 2012"],"publisher":"ICML","quality_controlled":"1","oa":1,"month":"06","abstract":[{"text":"We consider the problem of inference in a graphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pairwise terms over a discretized domain. This allows the use of techniques originally developed for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can outperform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.\r\n","lang":"eng"}],"oa_version":"Submitted Version","date_published":"2012-06-30T00:00:00Z","related_material":{"record":[{"status":"public","id":"5396","relation":"later_version"}]},"date_created":"2018-12-11T12:01:31Z","has_accepted_license":"1","publication_status":"published","year":"2012","file":[{"date_updated":"2020-07-14T12:46:00Z","file_size":305836,"creator":"system","date_created":"2018-12-12T10:11:34Z","file_name":"IST-2016-565-v1+1_DM-inferning2012.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"3d0d4246548c736857302aadb2ff5d15","file_id":"4889"}],"day":"30","language":[{"iso":"eng"}]},{"month":"07","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","oa":1,"oa_version":"Published Version","abstract":[{"text":"We consider the problem of inference in agraphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can out-perform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.","lang":"eng"}],"related_material":{"record":[{"relation":"earlier_version","id":"3124","status":"public"}]},"doi":"10.15479/AT:IST-2012-0003","date_published":"2012-07-23T00:00:00Z","date_created":"2018-12-12T11:39:06Z","page":"13","day":"23","file":[{"checksum":"7e0ba85ad123b13223aaf6cdde2d288c","file_id":"5490","content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:53:29Z","file_name":"IST-2012-0003_IST-2012-0003.pdf","date_updated":"2020-07-14T12:46:44Z","file_size":618744,"creator":"system"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"year":"2012","publication_status":"published","status":"public","pubrep_id":"36","type":"technical_report","_id":"5396","title":"Approximating marginals using discrete energy minimization","department":[{"_id":"VlKo"},{"_id":"ChLa"}],"file_date_updated":"2020-07-14T12:46:44Z","author":[{"full_name":"Korc, Filip","last_name":"Korc","first_name":"Filip","id":"476A2FD6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","last_name":"Lampert"}],"ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T11:13:22Z","citation":{"chicago":"Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. Approximating Marginals Using Discrete Energy Minimization. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0003.","ista":"Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization, IST Austria, 13p.","mla":"Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization. IST Austria, 2012, doi:10.15479/AT:IST-2012-0003.","ieee":"F. Korc, V. Kolmogorov, and C. Lampert, Approximating marginals using discrete energy minimization. IST Austria, 2012.","short":"F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete Energy Minimization, IST Austria, 2012.","apa":"Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals using discrete energy minimization. IST Austria. https://doi.org/10.15479/AT:IST-2012-0003","ama":"Korc F, Kolmogorov V, Lampert C. Approximating Marginals Using Discrete Energy Minimization. IST Austria; 2012. doi:10.15479/AT:IST-2012-0003"}},{"_id":"5398","pubrep_id":"103","status":"public","type":"report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["020"],"citation":{"mla":"Porsche, Jana. Actual State of Research Data @ ISTAustria. IST Austria, 2012.","ieee":"J. Porsche, Actual state of research data @ ISTAustria. IST Austria, 2012.","short":"J. Porsche, Actual State of Research Data @ ISTAustria, IST Austria, 2012.","apa":"Porsche, J. (2012). Actual state of research data @ ISTAustria. IST Austria.","ama":"Porsche J. Actual State of Research Data @ ISTAustria. IST Austria; 2012.","chicago":"Porsche, Jana. Actual State of Research Data @ ISTAustria. IST Austria, 2012.","ista":"Porsche J. 2012. Actual state of research data @ ISTAustria, IST Austria,p."},"date_updated":"2020-07-14T23:04:49Z","title":"Actual state of research data @ ISTAustria","department":[{"_id":"E-Lib"}],"file_date_updated":"2020-07-14T12:46:44Z","author":[{"first_name":"Jana","id":"3252EDC2-F248-11E8-B48F-1D18A9856A87","full_name":"Porsche, Jana","last_name":"Porsche"}],"oa_version":"Published Version","abstract":[{"lang":"eng","text":"This document is created as a part of the project “Repository for Research Data on IST Austria”. It summarises the actual state of research data at IST Austria, based on survey results. It supports the choice of appropriate software, which would best fit the requirements of their users, the researchers."}],"month":"11","oa":1,"publisher":"IST Austria","language":[{"iso":"eng"}],"day":"12","file":[{"date_updated":"2020-07-14T12:46:44Z","file_size":238544,"creator":"system","date_created":"2018-12-12T11:53:11Z","file_name":"IST-2012-103-v1+1_Actual_state_of_research_data_@_IST_Austria.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"5472","checksum":"e0a7c041eea1ca4b70ab6f9ec5177f4e"}],"year":"2012","publication_status":"published","has_accepted_license":"1","date_created":"2018-12-12T11:39:06Z","date_published":"2012-11-12T00:00:00Z"},{"author":[{"full_name":"Biswas, Ranita","orcid":"0000-0002-5372-7890","last_name":"Biswas","first_name":"Ranita","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jaya","full_name":"Sil, Jaya","last_name":"Sil"}],"title":"An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets","citation":{"ama":"Biswas R, Sil J. An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets. Procedia Technology. 2012;4:820-824. doi:10.1016/j.protcy.2012.05.134","apa":"Biswas, R., & Sil, J. (2012). An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets. Procedia Technology. Elsevier. https://doi.org/10.1016/j.protcy.2012.05.134","ieee":"R. Biswas and J. Sil, “An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets,” Procedia Technology, vol. 4. Elsevier, pp. 820–824, 2012.","short":"R. Biswas, J. Sil, Procedia Technology 4 (2012) 820–824.","mla":"Biswas, Ranita, and Jaya Sil. “An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets.” Procedia Technology, vol. 4, Elsevier, 2012, pp. 820–24, doi:10.1016/j.protcy.2012.05.134.","ista":"Biswas R, Sil J. 2012. An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets. Procedia Technology. 4, 820–824.","chicago":"Biswas, Ranita, and Jaya Sil. “An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets.” Procedia Technology. Elsevier, 2012. https://doi.org/10.1016/j.protcy.2012.05.134."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"820-824","doi":"10.1016/j.protcy.2012.05.134","date_published":"2012-05-01T00:00:00Z","date_created":"2019-01-17T11:54:21Z","has_accepted_license":"1","year":"2012","day":"01","publication":"Procedia Technology","quality_controlled":"1","publisher":"Elsevier","oa":1,"file_date_updated":"2020-07-14T12:47:12Z","date_updated":"2021-01-12T08:03:43Z","extern":"1","ddc":["000"],"type":"journal_article","tmp":{"short":"CC BY-NC-ND (4.0)","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","image":"/images/cc_by_nc_nd.png"},"status":"public","_id":"5839","volume":4,"publication_identifier":{"issn":["2212-0173"]},"publication_status":"published","file":[{"creator":"dernst","file_size":305426,"date_updated":"2020-07-14T12:47:12Z","file_name":"2012_Procedia_Biswas.pdf","date_created":"2019-01-21T07:28:06Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"ba0185986b151d8c11201f48cd505ceb","file_id":"5863"}],"language":[{"iso":"eng"}],"month":"05","intvolume":" 4","abstract":[{"text":"Canny's edge detection algorithm is a classical and robust method for edge detection in gray-scale images. The two \r\nsignificant features of this method are introduction of NMS (Non-Maximum Suppression) and double thresholding of \r\nthe gradient image. Due to poor illumination, the region boundaries in an image may become vague, creating \r\nuncertainties in the gradient image. In this paper, we have proposed an algorithm based on the concept of type-2 fuzzy sets to handle uncertainties that automatically selects the threshold values needed to segment the gradient image using classical Canny’s edge detection algorithm. The results show that our algorithm works significantly well on different benchmark images as well as medical images (hand radiography images). ","lang":"eng"}],"oa_version":"Published Version"}]