--- _id: '6005' abstract: - lang: eng text: Network games are widely used as a model for selfish resource-allocation problems. In the classicalmodel, each player selects a path connecting her source and target vertices. The cost of traversingan edge depends on theload; namely, number of players that traverse it. Thus, it abstracts the factthat different users may use a resource at different times and for different durations, which playsan important role in determining the costs of the users in reality. For example, when transmittingpackets in a communication network, routing traffic in a road network, or processing a task in aproduction system, actual sharing and congestion of resources crucially depends on time.In [13], we introducedtimed network games, which add a time component to network games.Each vertexvin the network is associated with a cost function, mapping the load onvto theprice that a player pays for staying invfor one time unit with this load. Each edge in thenetwork is guarded by the time intervals in which it can be traversed, which forces the players tospend time in the vertices. In this work we significantly extend the way time can be referred toin timed network games. In the model we study, the network is equipped withclocks, and, as intimed automata, edges are guarded by constraints on the values of the clocks, and their traversalmay involve a reset of some clocks. We argue that the stronger model captures many realisticnetworks. The addition of clocks breaks the techniques we developed in [13] and we developnew techniques in order to show that positive results on classic network games carry over to thestronger timed setting. alternative_title: - LIPIcs article_number: '23' article_processing_charge: No author: - first_name: Guy full_name: Avni, Guy id: 463C8BC2-F248-11E8-B48F-1D18A9856A87 last_name: Avni orcid: 0000-0001-5588-8287 - first_name: Shibashis full_name: Guha, Shibashis last_name: Guha - first_name: Orna full_name: Kupferman, Orna last_name: Kupferman citation: ama: 'Avni G, Guha S, Kupferman O. Timed network games with clocks. In: Vol 117. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.MFCS.2018.23' apa: 'Avni, G., Guha, S., & Kupferman, O. (2018). Timed network games with clocks (Vol. 117). Presented at the MFCS: Mathematical Foundations of Computer Science, Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.MFCS.2018.23' chicago: Avni, Guy, Shibashis Guha, and Orna Kupferman. “Timed Network Games with Clocks,” Vol. 117. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.MFCS.2018.23. ieee: 'G. Avni, S. Guha, and O. Kupferman, “Timed network games with clocks,” presented at the MFCS: Mathematical Foundations of Computer Science, Liverpool, United Kingdom, 2018, vol. 117.' ista: 'Avni G, Guha S, Kupferman O. 2018. Timed network games with clocks. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 117, 23.' mla: Avni, Guy, et al. Timed Network Games with Clocks. Vol. 117, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPICS.MFCS.2018.23. short: G. Avni, S. Guha, O. Kupferman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. conference: end_date: 2018-08-31 location: Liverpool, United Kingdom name: 'MFCS: Mathematical Foundations of Computer Science' start_date: 2018-08-27 date_created: 2019-02-14T14:12:09Z date_published: 2018-08-01T00:00:00Z date_updated: 2023-02-23T14:02:58Z day: '01' ddc: - '000' department: - _id: ToHe doi: 10.4230/LIPICS.MFCS.2018.23 file: - access_level: open_access checksum: 41ab2ae9b63f5eb49fa995250c0ba128 content_type: application/pdf creator: dernst date_created: 2019-02-14T14:22:04Z date_updated: 2020-07-14T12:47:15Z file_id: '6007' file_name: 2018_LIPIcs_Avni.pdf file_size: 542889 relation: main_file file_date_updated: 2020-07-14T12:47:15Z has_accepted_license: '1' intvolume: ' 117' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '08' oa: 1 oa_version: Published Version project: - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize - _id: 264B3912-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: M02369 name: Formal Methods meets Algorithmic Game Theory publication_identifier: issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '963' relation: earlier_version status: public scopus_import: '1' status: public title: Timed network games with clocks tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 117 year: '2018' ... --- _id: '133' abstract: - lang: eng text: Synchronous programs are easy to specify because the side effects of an operation are finished by the time the invocation of the operation returns to the caller. Asynchronous programs, on the other hand, are difficult to specify because there are side effects due to pending computation scheduled as a result of the invocation of an operation. They are also difficult to verify because of the large number of possible interleavings of concurrent computation threads. We present synchronization, a new proof rule that simplifies the verification of asynchronous programs by introducing the fiction, for proof purposes, that asynchronous operations complete synchronously. Synchronization summarizes an asynchronous computation as immediate atomic effect. Modular verification is enabled via pending asynchronous calls in atomic summaries, and a complementary proof rule that eliminates pending asynchronous calls when components and their specifications are composed. We evaluate synchronization in the context of a multi-layer refinement verification methodology on a collection of benchmark programs. alternative_title: - LIPIcs article_number: '21' author: - first_name: Bernhard full_name: Kragl, Bernhard id: 320FC952-F248-11E8-B48F-1D18A9856A87 last_name: Kragl orcid: 0000-0001-7745-9117 - first_name: Shaz full_name: Qadeer, Shaz last_name: Qadeer - 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: 'Kragl B, Qadeer S, Henzinger TA. Synchronizing the asynchronous. In: Vol 118. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.CONCUR.2018.21' apa: 'Kragl, B., Qadeer, S., & Henzinger, T. A. (2018). Synchronizing the asynchronous (Vol. 118). Presented at the CONCUR: International Conference on Concurrency Theory, Beijing, China: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2018.21' chicago: Kragl, Bernhard, Shaz Qadeer, and Thomas A Henzinger. “Synchronizing the Asynchronous,” Vol. 118. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.CONCUR.2018.21. ieee: 'B. Kragl, S. Qadeer, and T. A. Henzinger, “Synchronizing the asynchronous,” presented at the CONCUR: International Conference on Concurrency Theory, Beijing, China, 2018, vol. 118.' ista: 'Kragl B, Qadeer S, Henzinger TA. 2018. Synchronizing the asynchronous. CONCUR: International Conference on Concurrency Theory, LIPIcs, vol. 118, 21.' mla: Kragl, Bernhard, et al. Synchronizing the Asynchronous. Vol. 118, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.CONCUR.2018.21. short: B. Kragl, S. Qadeer, T.A. Henzinger, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. conference: end_date: 2018-09-07 location: Beijing, China name: 'CONCUR: International Conference on Concurrency Theory' start_date: 2018-09-04 date_created: 2018-12-11T11:44:48Z date_published: 2018-08-13T00:00:00Z date_updated: 2023-09-07T13:18:00Z day: '13' ddc: - '000' department: - _id: ToHe doi: 10.4230/LIPIcs.CONCUR.2018.21 file: - access_level: open_access checksum: c90895f4c5fafc18ddc54d1c8848077e content_type: application/pdf creator: system date_created: 2018-12-12T10:18:46Z date_updated: 2020-07-14T12:44:44Z file_id: '5368' file_name: IST-2018-853-v2+2_concur2018.pdf file_size: 745438 relation: main_file file_date_updated: 2020-07-14T12:44:44Z has_accepted_license: '1' intvolume: ' 118' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 25F2ACDE-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11402-N23 name: Rigorous Systems Engineering - _id: 25F5A88A-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11402-N23 name: Moderne Concurrency Paradigms publication_identifier: issn: - '18688969' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '7790' pubrep_id: '1039' quality_controlled: '1' related_material: record: - id: '6426' relation: earlier_version status: public - id: '8332' relation: dissertation_contains status: public scopus_import: 1 status: public title: Synchronizing the asynchronous tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 118 year: '2018' ... --- _id: '299' abstract: - lang: eng text: We introduce in this paper AMT 2.0 , a tool for qualitative and quantitative analysis of hybrid continuous and Boolean signals that combine numerical values and discrete events. The evaluation of the signals is based on rich temporal specifications expressed in extended Signal Temporal Logic (xSTL), which integrates Timed Regular Expressions (TRE) within Signal Temporal Logic (STL). The tool features qualitative monitoring (property satisfaction checking), trace diagnostics for explaining and justifying property violations and specification-driven measurement of quantitative features of the signal. alternative_title: - LNCS article_processing_charge: No author: - first_name: Dejan full_name: Nickovic, Dejan id: 41BCEE5C-F248-11E8-B48F-1D18A9856A87 last_name: Nickovic - first_name: Olivier full_name: Lebeltel, Olivier last_name: Lebeltel - first_name: Oded full_name: Maler, Oded last_name: Maler - first_name: Thomas full_name: Ferrere, Thomas id: 40960E6E-F248-11E8-B48F-1D18A9856A87 last_name: Ferrere orcid: 0000-0001-5199-3143 - first_name: Dogan full_name: Ulus, Dogan last_name: Ulus citation: ama: 'Nickovic D, Lebeltel O, Maler O, Ferrere T, Ulus D. AMT 2.0: Qualitative and quantitative trace analysis with extended signal temporal logic. In: Beyer D, Huisman M, eds. Vol 10806. Springer; 2018:303-319. doi:10.1007/978-3-319-89963-3_18' apa: 'Nickovic, D., Lebeltel, O., Maler, O., Ferrere, T., & Ulus, D. (2018). AMT 2.0: Qualitative and quantitative trace analysis with extended signal temporal logic. In D. Beyer & M. Huisman (Eds.) (Vol. 10806, pp. 303–319). Presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, Thessaloniki, Greece: Springer. https://doi.org/10.1007/978-3-319-89963-3_18' chicago: 'Nickovic, Dejan, Olivier Lebeltel, Oded Maler, Thomas Ferrere, and Dogan Ulus. “AMT 2.0: Qualitative and Quantitative Trace Analysis with Extended Signal Temporal Logic.” edited by Dirk Beyer and Marieke Huisman, 10806:303–19. Springer, 2018. https://doi.org/10.1007/978-3-319-89963-3_18.' ieee: 'D. Nickovic, O. Lebeltel, O. Maler, T. Ferrere, and D. Ulus, “AMT 2.0: Qualitative and quantitative trace analysis with extended signal temporal logic,” presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, Thessaloniki, Greece, 2018, vol. 10806, pp. 303–319.' ista: 'Nickovic D, Lebeltel O, Maler O, Ferrere T, Ulus D. 2018. AMT 2.0: Qualitative and quantitative trace analysis with extended signal temporal logic. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 10806, 303–319.' mla: 'Nickovic, Dejan, et al. AMT 2.0: Qualitative and Quantitative Trace Analysis with Extended Signal Temporal Logic. Edited by Dirk Beyer and Marieke Huisman, vol. 10806, Springer, 2018, pp. 303–19, doi:10.1007/978-3-319-89963-3_18.' short: D. Nickovic, O. Lebeltel, O. Maler, T. Ferrere, D. Ulus, in:, D. Beyer, M. Huisman (Eds.), Springer, 2018, pp. 303–319. conference: end_date: 2018-04-20 location: Thessaloniki, Greece name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems' start_date: 2018-04-14 date_created: 2018-12-11T11:45:41Z date_published: 2018-04-14T00:00:00Z date_updated: 2023-09-08T11:52:02Z day: '14' ddc: - '000' department: - _id: ToHe doi: 10.1007/978-3-319-89963-3_18 editor: - first_name: Dirk full_name: Beyer, Dirk last_name: Beyer - first_name: Marieke full_name: Huisman, Marieke last_name: Huisman external_id: isi: - '00445822600018' file: - access_level: open_access checksum: e11db3b9c8e27a1c7d1c738cc5e4d25a content_type: application/pdf creator: dernst date_created: 2019-02-06T07:33:05Z date_updated: 2020-07-14T12:45:58Z file_id: '5928' file_name: 2018_LNCS_Nickovic.pdf file_size: 3267209 relation: main_file file_date_updated: 2020-07-14T12:45:58Z has_accepted_license: '1' intvolume: ' 10806' isi: 1 language: - iso: eng month: '04' oa: 1 oa_version: Published Version page: 303 - 319 publication_status: published publisher: Springer publist_id: '7582' quality_controlled: '1' related_material: record: - id: '10861' relation: later_version status: public scopus_import: '1' status: public title: 'AMT 2.0: Qualitative and quantitative trace analysis with extended signal temporal logic' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 10806 year: '2018' ... --- _id: '144' abstract: - lang: eng text: The task of a monitor is to watch, at run-time, the execution of a reactive system, and signal the occurrence of a safety violation in the observed sequence of events. While finite-state monitors have been studied extensively, in practice, monitoring software also makes use of unbounded memory. We define a model of automata equipped with integer-valued registers which can execute only a bounded number of instructions between consecutive events, and thus can form the theoretical basis for the study of infinite-state monitors. We classify these register monitors according to the number k of available registers, and the type of register instructions. In stark contrast to the theory of computability for register machines, we prove that for every k 1, monitors with k + 1 counters (with instruction set 〈+1, =〉) are strictly more expressive than monitors with k counters. We also show that adder monitors (with instruction set 〈1, +, =〉) are strictly more expressive than counter monitors, but are complete for monitoring all computable safety -languages for k = 6. Real-time monitors are further required to signal the occurrence of a safety violation as soon as it occurs. The expressiveness hierarchy for counter monitors carries over to real-time monitors. We then show that 2 adders cannot simulate 3 counters in real-time. Finally, we show that real-time adder monitors with inequalities are as expressive as real-time Turing machines. alternative_title: - ACM/IEEE Symposium on Logic in Computer Science article_processing_charge: No author: - first_name: Thomas full_name: Ferrere, Thomas id: 40960E6E-F248-11E8-B48F-1D18A9856A87 last_name: Ferrere orcid: 0000-0001-5199-3143 - 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: Ege full_name: Saraç, Ege last_name: Saraç citation: ama: 'Ferrere T, Henzinger TA, Saraç E. A theory of register monitors. In: Vol Part F138033. IEEE; 2018:394-403. doi:10.1145/3209108.3209194' apa: 'Ferrere, T., Henzinger, T. A., & Saraç, E. (2018). A theory of register monitors (Vol. Part F138033, pp. 394–403). Presented at the LICS: Logic in Computer Science, Oxford, UK: IEEE. https://doi.org/10.1145/3209108.3209194' chicago: Ferrere, Thomas, Thomas A Henzinger, and Ege Saraç. “A Theory of Register Monitors,” Part F138033:394–403. IEEE, 2018. https://doi.org/10.1145/3209108.3209194. ieee: 'T. Ferrere, T. A. Henzinger, and E. Saraç, “A theory of register monitors,” presented at the LICS: Logic in Computer Science, Oxford, UK, 2018, vol. Part F138033, pp. 394–403.' ista: 'Ferrere T, Henzinger TA, Saraç E. 2018. A theory of register monitors. LICS: Logic in Computer Science, ACM/IEEE Symposium on Logic in Computer Science, vol. Part F138033, 394–403.' mla: Ferrere, Thomas, et al. A Theory of Register Monitors. Vol. Part F138033, IEEE, 2018, pp. 394–403, doi:10.1145/3209108.3209194. short: T. Ferrere, T.A. Henzinger, E. Saraç, in:, IEEE, 2018, pp. 394–403. conference: end_date: 2018-07-12 location: Oxford, UK name: 'LICS: Logic in Computer Science' start_date: 2018-07-09 date_created: 2018-12-11T11:44:52Z date_published: 2018-07-09T00:00:00Z date_updated: 2023-09-08T11:49:13Z day: '09' department: - _id: ToHe doi: 10.1145/3209108.3209194 external_id: isi: - '000545262800041' isi: 1 language: - iso: eng month: '07' oa_version: None page: 394 - 403 publication_status: published publisher: IEEE publist_id: '7779' quality_controlled: '1' scopus_import: '1' status: public title: A theory of register monitors type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: Part F138033 year: '2018' ... --- _id: '182' abstract: - lang: eng text: We describe a new algorithm for the parametric identification problem for signal temporal logic (STL), stated as follows. Given a densetime real-valued signal w and a parameterized temporal logic formula φ, compute the subset of the parameter space that renders the formula satisfied by the signal. Unlike previous solutions, which were based on search in the parameter space or quantifier elimination, our procedure works recursively on φ and computes the evolution over time of the set of valid parameter assignments. This procedure is similar to that of monitoring or computing the robustness of φ relative to w. Our implementation and experiments demonstrate that this approach can work well in practice. alternative_title: - HSCC Proceedings article_processing_charge: No author: - first_name: Alexey full_name: Bakhirkin, Alexey last_name: Bakhirkin - first_name: Thomas full_name: Ferrere, Thomas id: 40960E6E-F248-11E8-B48F-1D18A9856A87 last_name: Ferrere orcid: 0000-0001-5199-3143 - first_name: Oded full_name: Maler, Oded last_name: Maler citation: ama: 'Bakhirkin A, Ferrere T, Maler O. Efficient parametric identification for STL. In: Proceedings of the 21st International Conference on Hybrid Systems. ACM; 2018:177-186. doi:10.1145/3178126.3178132' apa: 'Bakhirkin, A., Ferrere, T., & Maler, O. (2018). Efficient parametric identification for STL. In Proceedings of the 21st International Conference on Hybrid Systems (pp. 177–186). Porto, Portugal: ACM. https://doi.org/10.1145/3178126.3178132' chicago: Bakhirkin, Alexey, Thomas Ferrere, and Oded Maler. “Efficient Parametric Identification for STL.” In Proceedings of the 21st International Conference on Hybrid Systems, 177–86. ACM, 2018. https://doi.org/10.1145/3178126.3178132. ieee: A. Bakhirkin, T. Ferrere, and O. Maler, “Efficient parametric identification for STL,” in Proceedings of the 21st International Conference on Hybrid Systems, Porto, Portugal, 2018, pp. 177–186. ista: 'Bakhirkin A, Ferrere T, Maler O. 2018. Efficient parametric identification for STL. Proceedings of the 21st International Conference on Hybrid Systems. HSCC: Hybrid Systems: Computation and Control, HSCC Proceedings, , 177–186.' mla: Bakhirkin, Alexey, et al. “Efficient Parametric Identification for STL.” Proceedings of the 21st International Conference on Hybrid Systems, ACM, 2018, pp. 177–86, doi:10.1145/3178126.3178132. short: A. Bakhirkin, T. Ferrere, O. Maler, in:, Proceedings of the 21st International Conference on Hybrid Systems, ACM, 2018, pp. 177–186. conference: end_date: 2018-04-13 location: Porto, Portugal name: 'HSCC: Hybrid Systems: Computation and Control' start_date: 2018-04-11 date_created: 2018-12-11T11:45:04Z date_published: 2018-04-11T00:00:00Z date_updated: 2023-09-11T13:30:51Z day: '11' ddc: - '000' department: - _id: ToHe doi: 10.1145/3178126.3178132 external_id: isi: - '000474781600020' file: - access_level: open_access checksum: 81eabc96430e84336ea88310ac0a1ad0 content_type: application/pdf creator: dernst date_created: 2020-05-14T12:18:29Z date_updated: 2020-07-14T12:45:17Z file_id: '7833' file_name: 2018_HSCC_Bakhirkin.pdf file_size: 5900421 relation: main_file file_date_updated: 2020-07-14T12:45:17Z has_accepted_license: '1' isi: 1 language: - iso: eng month: '04' oa: 1 oa_version: Submitted Version page: 177 - 186 project: - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering publication: Proceedings of the 21st International Conference on Hybrid Systems publication_identifier: isbn: - '978-1-4503-5642-8 ' publication_status: published publisher: ACM publist_id: '7739' quality_controlled: '1' scopus_import: '1' status: public title: Efficient parametric identification for STL type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2018' ...