[{"publication_status":"published","status":"public","title":"Edit distance for timed automata","ddc":["000"],"department":[{"_id":"KrCh"}],"publisher":"IST Austria","year":"2013","_id":"5409","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-12T11:39:10Z","date_updated":"2023-02-23T10:33:18Z","file":[{"relation":"main_file","file_id":"5469","checksum":"0f7633081ba8299c543322f0ad08571f","date_created":"2018-12-12T11:53:08Z","date_updated":"2020-07-14T12:46:46Z","access_level":"open_access","file_name":"IST-2013-144-v1+1_main.pdf","content_type":"application/pdf","file_size":336377,"creator":"system"}],"oa_version":"Published Version","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Majumdar, Rupak","first_name":"Rupak","last_name":"Majumdar"}],"pubrep_id":"144","related_material":{"record":[{"id":"2216","status":"public","relation":"later_version"}]},"alternative_title":["IST Austria Technical Report"],"type":"technical_report","abstract":[{"lang":"eng","text":"The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition. \r\nIn this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in timestamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than delta away from the parameter, for delta>0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and we show analogous decidability results for rectangular automata."}],"file_date_updated":"2020-07-14T12:46:46Z","page":"12","oa":1,"citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Majumdar R. Edit Distance for Timed Automata. IST Austria; 2013. doi:10.15479/AT:IST-2013-144-v1-1","ista":"Chatterjee K, Ibsen-Jensen R, Majumdar R. 2013. Edit distance for timed automata, IST Austria, 12p.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and R. Majumdar, Edit distance for timed automata. IST Austria, 2013.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Majumdar, R. (2013). Edit distance for timed automata. IST Austria. https://doi.org/10.15479/AT:IST-2013-144-v1-1","mla":"Chatterjee, Krishnendu, et al. Edit Distance for Timed Automata. IST Austria, 2013, doi:10.15479/AT:IST-2013-144-v1-1.","short":"K. Chatterjee, R. Ibsen-Jensen, R. Majumdar, Edit Distance for Timed Automata, IST Austria, 2013.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Rupak Majumdar. Edit Distance for Timed Automata. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-144-v1-1."},"language":[{"iso":"eng"}],"date_published":"2013-10-30T00:00:00Z","doi":"10.15479/AT:IST-2013-144-v1-1","month":"10","day":"30","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1"},{"conference":{"name":"FMCAD: Formal Methods in Computer-Aided Design","end_date":"2013-10-23","start_date":"2013-10-20","location":"Portland, OR, United States"},"doi":"10.1109/FMCAD.2013.6679386","date_published":"2013-12-11T00:00:00Z","language":[{"iso":"eng"}],"publication":"13th International Conference on Formal Methods in Computer-Aided Design","citation":{"ista":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis for LTL fragments. 13th International Conference on Formal Methods in Computer-Aided Design. FMCAD: Formal Methods in Computer-Aided Design, 18–25.","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, “Distributed synthesis for LTL fragments,” in 13th International Conference on Formal Methods in Computer-Aided Design, Portland, OR, United States, 2013, pp. 18–25.","apa":"Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013). Distributed synthesis for LTL fragments. In 13th International Conference on Formal Methods in Computer-Aided Design (pp. 18–25). Portland, OR, United States: IEEE. https://doi.org/10.1109/FMCAD.2013.6679386","ama":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed synthesis for LTL fragments. In: 13th International Conference on Formal Methods in Computer-Aided Design. IEEE; 2013:18-25. doi:10.1109/FMCAD.2013.6679386","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis. “Distributed Synthesis for LTL Fragments.” In 13th International Conference on Formal Methods in Computer-Aided Design, 18–25. IEEE, 2013. https://doi.org/10.1109/FMCAD.2013.6679386.","mla":"Chatterjee, Krishnendu, et al. “Distributed Synthesis for LTL Fragments.” 13th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25, doi:10.1109/FMCAD.2013.6679386.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, in:, 13th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25."},"quality_controlled":"1","page":"18 - 25","project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"month":"12","day":"11","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","last_name":"Otop","first_name":"Jan"},{"last_name":"Pavlogiannis","first_name":"Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas"}],"related_material":{"record":[{"id":"5406","relation":"earlier_version","status":"public"}]},"date_updated":"2023-02-23T12:24:53Z","date_created":"2018-12-11T11:51:40Z","oa_version":"None","_id":"1376","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2013","status":"public","publication_status":"published","title":"Distributed synthesis for LTL fragments","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"IEEE","abstract":[{"text":"We consider the distributed synthesis problem for temporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTL and our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3) Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.","lang":"eng"}],"publist_id":"5835","ec_funded":1,"type":"conference"},{"oa":1,"citation":{"apa":"Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013). Distributed synthesis for LTL Fragments. IST Austria. https://doi.org/10.15479/AT:IST-2013-130-v1-1","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, Distributed synthesis for LTL Fragments. IST Austria, 2013.","ista":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis for LTL Fragments, IST Austria, 11p.","ama":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed Synthesis for LTL Fragments. IST Austria; 2013. doi:10.15479/AT:IST-2013-130-v1-1","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis. Distributed Synthesis for LTL Fragments. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-130-v1-1.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, Distributed Synthesis for LTL Fragments, IST Austria, 2013.","mla":"Chatterjee, Krishnendu, et al. Distributed Synthesis for LTL Fragments. IST Austria, 2013, doi:10.15479/AT:IST-2013-130-v1-1."},"page":"11","date_published":"2013-07-08T00:00:00Z","doi":"10.15479/AT:IST-2013-130-v1-1","language":[{"iso":"eng"}],"has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"day":"08","month":"07","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5406","year":"2013","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"IST Austria","publication_status":"published","title":"Distributed synthesis for LTL Fragments","ddc":["005"],"status":"public","related_material":{"record":[{"id":"1376","relation":"later_version","status":"public"}]},"pubrep_id":"130","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A"},{"last_name":"Otop","first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan"},{"full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","first_name":"Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"oa_version":"Published Version","file":[{"file_id":"5540","relation":"main_file","checksum":"855513ebaf6f72228800c5fdb522f93c","date_created":"2018-12-12T11:54:18Z","date_updated":"2020-07-14T12:46:45Z","access_level":"open_access","file_name":"IST-2013-130-v1+1_Distributed_Synthesis.pdf","creator":"system","content_type":"application/pdf","file_size":467895}],"date_created":"2018-12-12T11:39:09Z","date_updated":"2023-02-21T17:01:26Z","type":"technical_report","alternative_title":["IST Austria Technical Report"],"abstract":[{"text":"We consider the distributed synthesis problem fortemporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTLand our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3)Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:45Z"},{"file":[{"content_type":"application/pdf","file_size":300481,"creator":"system","file_name":"IST-2013-141-v1+1_main-tech-rpt.pdf","access_level":"open_access","date_created":"2018-12-12T11:53:16Z","date_updated":"2020-07-14T12:46:46Z","checksum":"226bc791124f8d3138379778ce834e86","relation":"main_file","file_id":"5477"}],"oa_version":"Published Version","date_created":"2018-12-12T11:39:10Z","date_updated":"2023-02-23T10:33:11Z","pubrep_id":"141","related_material":{"record":[{"status":"public","relation":"later_version","id":"2213"}]},"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"},{"full_name":"Nain, Sumit","first_name":"Sumit","last_name":"Nain"},{"first_name":"Moshe","last_name":"Vardi","full_name":"Vardi, Moshe"}],"publisher":"IST Austria","department":[{"_id":"KrCh"}],"title":"The complexity of partial-observation stochastic parity games with finite-memory strategies","publication_status":"published","ddc":["000","005"],"status":"public","_id":"5408","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2013","abstract":[{"text":"We consider two-player partial-observation stochastic games where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are omega-regular conditions specified as parity objectives. The qualitative analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, they were shown to be decidable in 2EXPTIME under finite-memory strategies. We improve the complexity and show that the qualitative analysis problems for partial-observation stochastic parity games under finite-memory strategies are \r\nEXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis. ","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:46Z","alternative_title":["IST Austria Technical Report"],"type":"technical_report","language":[{"iso":"eng"}],"date_published":"2013-09-12T00:00:00Z","doi":"10.15479/AT:IST-2013-141-v1-1","page":"17","citation":{"ama":"Chatterjee K, Doyen L, Nain S, Vardi M. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria; 2013. doi:10.15479/AT:IST-2013-141-v1-1","ista":"Chatterjee K, Doyen L, Nain S, Vardi M. 2013. The complexity of partial-observation stochastic parity games with finite-memory strategies, IST Austria, 17p.","apa":"Chatterjee, K., Doyen, L., Nain, S., & Vardi, M. (2013). The complexity of partial-observation stochastic parity games with finite-memory strategies. IST Austria. https://doi.org/10.15479/AT:IST-2013-141-v1-1","ieee":"K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, The complexity of partial-observation stochastic parity games with finite-memory strategies. IST Austria, 2013.","mla":"Chatterjee, Krishnendu, et al. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria, 2013, doi:10.15479/AT:IST-2013-141-v1-1.","short":"K. Chatterjee, L. Doyen, S. Nain, M. Vardi, The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies, IST Austria, 2013.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Sumit Nain, and Moshe Vardi. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-141-v1-1."},"oa":1,"publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","month":"09","day":"12"},{"citation":{"apa":"Porsche, J. (2013). Technical requirements and features. IST Austria.","ieee":"J. Porsche, Technical requirements and features. IST Austria, 2013.","ista":"Porsche J. 2013. Technical requirements and features, IST Austria,p.","ama":"Porsche J. Technical Requirements and Features. IST Austria; 2013.","chicago":"Porsche, Jana. Technical Requirements and Features. IST Austria, 2013.","short":"J. Porsche, Technical Requirements and Features, IST Austria, 2013.","mla":"Porsche, Jana. Technical Requirements and Features. IST Austria, 2013."},"oa":1,"date_published":"2013-07-13T00:00:00Z","language":[{"iso":"eng"}],"day":"13","month":"07","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5407","year":"2013","status":"public","title":"Technical requirements and features","ddc":["020"],"publication_status":"published","department":[{"_id":"E-Lib"}],"publisher":"IST Austria","author":[{"full_name":"Porsche, Jana","last_name":"Porsche","first_name":"Jana","id":"3252EDC2-F248-11E8-B48F-1D18A9856A87"}],"pubrep_id":"135","date_updated":"2020-07-14T23:07:51Z","date_created":"2018-12-12T11:39:09Z","file":[{"creator":"system","file_size":90311,"content_type":"application/pdf","file_name":"IST-2013-135-v1+1_Features.pdf","access_level":"open_access","date_updated":"2020-07-14T12:46:46Z","date_created":"2018-12-12T11:53:02Z","checksum":"9e4f9abf79a56f651f0012a34909880f","file_id":"5463","relation":"main_file"}],"oa_version":"Published Version","type":"report","file_date_updated":"2020-07-14T12:46:46Z","abstract":[{"lang":"eng","text":"This document is created as a part of the project “Repository for Research Data at IST Austria”. It summarises the mandatory features, which need to be fulfilled to provide an institutional repository as a platform and also a service to the scientists at the institute. It also includes optional features, which would be of strong benefit for the scientists and would increase the usage of the repository, and hence the visibility of research at IST Austria."}]}]