--- _id: '5406' abstract: - lang: eng 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.' alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 citation: 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 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 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. 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. mla: Chatterjee, Krishnendu, et al. Distributed Synthesis for LTL Fragments. IST Austria, 2013, doi: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. date_created: 2018-12-12T11:39:09Z date_published: 2013-07-08T00:00:00Z date_updated: 2023-02-21T17:01:26Z day: '08' ddc: - '005' department: - _id: KrCh - _id: ToHe doi: 10.15479/AT:IST-2013-130-v1-1 file: - access_level: open_access checksum: 855513ebaf6f72228800c5fdb522f93c content_type: application/pdf creator: system date_created: 2018-12-12T11:54:18Z date_updated: 2020-07-14T12:46:45Z file_id: '5540' file_name: IST-2013-130-v1+1_Distributed_Synthesis.pdf file_size: 467895 relation: main_file file_date_updated: 2020-07-14T12:46:45Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '11' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '130' related_material: record: - id: '1376' relation: later_version status: public status: public title: Distributed synthesis for LTL Fragments type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '2327' abstract: - lang: eng text: 'We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M′ within distance ρ from M satisfy (or violate) φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata. The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification. We show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved. We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications.' alternative_title: - LNCS author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop citation: ama: Henzinger TA, Otop J. From model checking to model measuring. 2013;8052:273-287. doi:10.1007/978-3-642-40184-8_20 apa: 'Henzinger, T. A., & Otop, J. (2013). From model checking to model measuring. Presented at the CONCUR: Concurrency Theory, Buenos Aires, Argentina: Springer. https://doi.org/10.1007/978-3-642-40184-8_20' chicago: Henzinger, Thomas A, and Jan Otop. “From Model Checking to Model Measuring.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40184-8_20. ieee: T. A. Henzinger and J. Otop, “From model checking to model measuring,” vol. 8052. Springer, pp. 273–287, 2013. ista: Henzinger TA, Otop J. 2013. From model checking to model measuring. 8052, 273–287. mla: Henzinger, Thomas A., and Jan Otop. From Model Checking to Model Measuring. Vol. 8052, Springer, 2013, pp. 273–87, doi:10.1007/978-3-642-40184-8_20. short: T.A. Henzinger, J. Otop, 8052 (2013) 273–287. conference: end_date: 2013-08-30 location: Buenos Aires, Argentina name: 'CONCUR: Concurrency Theory' start_date: 2013-08-27 date_created: 2018-12-11T11:57:00Z date_published: 2013-08-01T00:00:00Z date_updated: 2023-02-23T12:25:26Z day: '01' ddc: - '005' - '000' department: - _id: ToHe doi: 10.1007/978-3-642-40184-8_20 file: - access_level: open_access checksum: 4c04695c4bfdf2119cd4f5d1babc3e8a content_type: application/pdf creator: system date_created: 2018-12-12T10:17:45Z date_updated: 2020-07-14T12:45:38Z file_id: '5301' file_name: IST-2013-129-v1+1_concur.pdf file_size: 378587 relation: main_file file_date_updated: 2020-07-14T12:45:38Z has_accepted_license: '1' intvolume: ' 8052' language: - iso: eng month: '08' oa: 1 oa_version: Submitted Version page: 273 - 287 publication_status: published publisher: Springer publist_id: '4599' pubrep_id: '129' quality_controlled: '1' related_material: record: - id: '5417' relation: earlier_version status: public series_title: Lecture Notes in Computer Science status: public title: From model checking to model measuring type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8052 year: '2013' ... --- _id: '6440' abstract: - lang: eng text: In order to guarantee that each method of a data structure updates the logical state exactly once, al-most all non-blocking implementations employ Compare-And-Swap (CAS) based synchronization. For FIFO queue implementations this translates into concurrent enqueue or dequeue methods competing among themselves to update the same variable, the tail or the head, respectively, leading to high contention and poor scalability. Recent non-blocking queue implementations try to alleviate high contentionby increasing the number of contention points, all the while using CAS-based synchronization. Furthermore, obtaining a wait-free implementation with competition is achieved by additional synchronization which leads to further degradation of performance.In this paper we formalize the notion of competitiveness of a synchronizing statement which can beused as a measure for the scalability of concurrent implementations. We present a new queue implementation, the Speculative Pairing (SP) queue, which, as we show, decreases competitiveness by using Fetch-And-Increment (FAI) instead of CAS. We prove that the SP queue is linearizable and lock-free.We also show that replacing CAS with FAI leads to wait-freedom for dequeue methods without an adverse effect on performance. In fact, our experiments suggest that the SP queue can perform and scale better than the state-of-the-art queue implementations. alternative_title: - IST Austria Technical Report author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Hannes full_name: Payer, Hannes last_name: Payer - first_name: Ali full_name: Sezgin, Ali id: 4C7638DA-F248-11E8-B48F-1D18A9856A87 last_name: Sezgin citation: ama: Henzinger TA, Payer H, Sezgin A. Replacing Competition with Cooperation to Achieve Scalable Lock-Free FIFO Queues . IST Austria; 2013. doi:10.15479/AT:IST-2013-124-v1-1 apa: Henzinger, T. A., Payer, H., & Sezgin, A. (2013). Replacing competition with cooperation to achieve scalable lock-free FIFO queues . IST Austria. https://doi.org/10.15479/AT:IST-2013-124-v1-1 chicago: Henzinger, Thomas A, Hannes Payer, and Ali Sezgin. Replacing Competition with Cooperation to Achieve Scalable Lock-Free FIFO Queues . IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-124-v1-1. ieee: T. A. Henzinger, H. Payer, and A. Sezgin, Replacing competition with cooperation to achieve scalable lock-free FIFO queues . IST Austria, 2013. ista: Henzinger TA, Payer H, Sezgin A. 2013. Replacing competition with cooperation to achieve scalable lock-free FIFO queues , IST Austria, 23p. mla: Henzinger, Thomas A., et al. Replacing Competition with Cooperation to Achieve Scalable Lock-Free FIFO Queues . IST Austria, 2013, doi:10.15479/AT:IST-2013-124-v1-1. short: T.A. Henzinger, H. Payer, A. Sezgin, Replacing Competition with Cooperation to Achieve Scalable Lock-Free FIFO Queues , IST Austria, 2013. date_created: 2019-05-13T14:13:27Z date_published: 2013-06-13T00:00:00Z date_updated: 2020-07-14T23:06:19Z day: '13' ddc: - '000' - '005' department: - _id: ToHe doi: 10.15479/AT:IST-2013-124-v1-1 file: - access_level: open_access checksum: a219ba4eada6cd62befed52262ee15d4 content_type: application/pdf creator: dernst date_created: 2019-05-13T14:11:39Z date_updated: 2020-07-14T12:47:30Z file_id: '6441' file_name: 2013_TechRep_Henzinger.pdf file_size: 549684 relation: main_file file_date_updated: 2020-07-14T12:47:30Z has_accepted_license: '1' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: '23' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '124' status: public title: 'Replacing competition with cooperation to achieve scalable lock-free FIFO queues ' type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5747' article_processing_charge: No author: - first_name: Cezara full_name: Dragoi, Cezara id: 2B2B5ED0-F248-11E8-B48F-1D18A9856A87 last_name: Dragoi - first_name: Ashutosh full_name: Gupta, Ashutosh id: 335E5684-F248-11E8-B48F-1D18A9856A87 last_name: Gupta - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 citation: ama: 'Dragoi C, Gupta A, Henzinger TA. Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates. In: Computer Aided Verification. Vol 8044. CAV. Berlin, Heidelberg: Springer Berlin Heidelberg; 2013:174-190. doi:10.1007/978-3-642-39799-8_11' apa: 'Dragoi, C., Gupta, A., & Henzinger, T. A. (2013). Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates. In Computer Aided Verification (Vol. 8044, pp. 174–190). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-39799-8_11' chicago: 'Dragoi, Cezara, Ashutosh Gupta, and Thomas A Henzinger. “Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates.” In Computer Aided Verification, 8044:174–90. CAV. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. https://doi.org/10.1007/978-3-642-39799-8_11.' ieee: 'C. Dragoi, A. Gupta, and T. A. Henzinger, “Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates,” in Computer Aided Verification, vol. 8044, Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 174–190.' ista: 'Dragoi C, Gupta A, Henzinger TA. 2013.Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates. In: Computer Aided Verification. vol. 8044, 174–190.' mla: Dragoi, Cezara, et al. “Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates.” Computer Aided Verification, vol. 8044, Springer Berlin Heidelberg, 2013, pp. 174–90, doi:10.1007/978-3-642-39799-8_11. short: C. Dragoi, A. Gupta, T.A. Henzinger, in:, Computer Aided Verification, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 174–190. conference: end_date: 2013-07-19 location: Saint Petersburg, Russia name: CAV 2013 start_date: 2013-07-13 date_created: 2018-12-18T13:10:21Z date_published: 2013-01-01T00:00:00Z date_updated: 2023-09-05T14:16:07Z ddc: - '005' department: - _id: ToHe doi: 10.1007/978-3-642-39799-8_11 ec_funded: 1 file: - access_level: open_access checksum: a901cc6b71db08b61c0d4c0cbacc6287 content_type: application/pdf creator: dernst date_created: 2018-12-18T13:13:33Z date_updated: 2020-07-14T12:47:10Z file_id: '5748' file_name: 2013_CAV_Dragoi.pdf file_size: 236480 relation: main_file file_date_updated: 2020-07-14T12:47:10Z has_accepted_license: '1' intvolume: ' 8044' language: - iso: eng oa: 1 oa_version: None page: 174-190 place: Berlin, Heidelberg project: - _id: 25EE3708-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '267989' name: Quantitative Reactive Modeling - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering publication: Computer Aided Verification publication_identifier: eissn: - 1611-3349 isbn: - '9783642397981' - '9783642397998' issn: - 0302-9743 publication_status: published publisher: Springer Berlin Heidelberg pubrep_id: '195' quality_controlled: '1' scopus_import: '1' series_title: CAV status: public title: Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates type: book_chapter user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 8044 year: '2013' ... --- _id: '1405' abstract: - lang: eng text: "Motivated by the analysis of highly dynamic message-passing systems, i.e. unbounded thread creation, mobility, etc. we present a framework for the analysis of depth-bounded systems. Depth-bounded systems are one of the most expressive known fragment of the π-calculus for which interesting verification problems are still decidable. Even though they are infinite state systems depth-bounded systems are well-structured, thus can be analyzed algorithmically. We give an interpretation of depth-bounded systems as graph-rewriting systems. This gives more flexibility and ease of use to apply depth-bounded systems to other type of systems like shared memory concurrency.\r\n\r\nFirst, we develop an adequate domain of limits for depth-bounded systems, a prerequisite for the effective representation of downward-closed sets. Downward-closed sets are needed by forward saturation-based algorithms to represent potentially infinite sets of states. Then, we present an abstract interpretation framework to compute the covering set of well-structured transition systems. Because, in general, the covering set is not computable, our abstraction over-approximates the actual covering set. Our abstraction captures the essence of acceleration based-algorithms while giving up enough precision to ensure convergence. We have implemented the analysis in the PICASSO tool and show that it is accurate in practice. Finally, we build some further analyses like termination using the covering set as starting point." acknowledgement: "This work was supported in part by the Austrian Science Fund NFN RiSE (Rigorous Systems Engineering) and by the ERC Advanced Grant QUAREM (Quantitative Reactve Modeling).\r\nChapter 2, 3, and 4 are joint work with Thomas A. Henzinger and Thomas Wies. Chapter 2 was published in FoSSaCS 2010 as “Forward Analysis of Depth-Bounded Processes” [112]. Chapter 3 was published in VMCAI 2012 as “Ideal Abstractions for Well-Structured Transition Systems” [114]. Chap- ter 5.1 is joint work with Kshitij Bansal, Eric Koskinen, and Thomas Wies. It was published in TACAS 2013 as “Structural Counter Abstraction” [13]. The author’s contribution in this part is mostly related to the implementation. The theory required to understand the method and its implementation is quickly recalled to make the thesis self-contained, but should not be considered as a contribution. For the details of the methods, we refer the reader to the orig- inal publication [13] and the corresponding technical report [14]. Chapter 5.2 is ongoing work with Shahram Esmaeilsabzali, Rupak Majumdar, and Thomas Wies. I also would like to thank the people who supported over the past 4 years. My advisor Thomas A. Henzinger who gave me a lot of freedom to work on projects I was interested in. My collaborators, especially Thomas Wies with whom I worked since the beginning. The members of my thesis committee, Viktor Kun- cak and Rupak Majumdar, who also agreed to advise me. Simon Aeschbacher, Pavol Cerny, Cezara Dragoi, Arjun Radhakrishna, my family, friends and col- leagues who created an enjoyable environment. " alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Damien full_name: Zufferey, Damien id: 4397AC76-F248-11E8-B48F-1D18A9856A87 last_name: Zufferey orcid: 0000-0002-3197-8736 citation: ama: Zufferey D. Analysis of dynamic message passing programs. 2013. doi:10.15479/at:ista:1405 apa: Zufferey, D. (2013). Analysis of dynamic message passing programs. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:1405 chicago: Zufferey, Damien. “Analysis of Dynamic Message Passing Programs.” Institute of Science and Technology Austria, 2013. https://doi.org/10.15479/at:ista:1405. ieee: D. Zufferey, “Analysis of dynamic message passing programs,” Institute of Science and Technology Austria, 2013. ista: Zufferey D. 2013. Analysis of dynamic message passing programs. Institute of Science and Technology Austria. mla: Zufferey, Damien. Analysis of Dynamic Message Passing Programs. Institute of Science and Technology Austria, 2013, doi:10.15479/at:ista:1405. short: D. Zufferey, Analysis of Dynamic Message Passing Programs, Institute of Science and Technology Austria, 2013. date_created: 2018-12-11T11:51:50Z date_published: 2013-09-05T00:00:00Z date_updated: 2023-09-07T11:36:37Z day: '05' ddc: - '000' degree_awarded: PhD department: - _id: ToHe - _id: GradSch doi: 10.15479/at:ista:1405 ec_funded: 1 file: - access_level: open_access checksum: ed2d7b52933d134e8dc69d569baa284e content_type: application/pdf creator: dernst date_created: 2021-02-22T11:28:36Z date_updated: 2021-02-22T11:28:36Z file_id: '9176' file_name: 2013_Zufferey_thesis_final.pdf file_size: 1514906 relation: main_file success: 1 - access_level: closed checksum: cecc4c4b14225bee973d32e3dba91a55 content_type: application/pdf creator: cchlebak date_created: 2021-11-16T14:42:52Z date_updated: 2021-11-17T13:47:58Z file_id: '10298' file_name: 2013_Zufferey_thesis_final_pdfa.pdf file_size: 1378313 relation: main_file file_date_updated: 2021-11-17T13:47:58Z has_accepted_license: '1' language: - iso: eng main_file_link: - url: http://dzufferey.github.io/files/2013_thesis.pdf month: '09' oa: 1 oa_version: Published Version page: '134' project: - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 25EE3708-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '267989' name: Quantitative Reactive Modeling publication_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria publist_id: '5802' related_material: record: - id: '2847' relation: part_of_dissertation status: public - id: '3251' relation: part_of_dissertation status: public - id: '4361' relation: part_of_dissertation status: public status: public supervisor: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 title: Analysis of dynamic message passing programs type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2013' ...