[{"publication_status":"published","department":[{"_id":"KrCh","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]}],"date_created":"2018-12-11T11:59:46Z","dini_type":"doc-type:conferenceObject","date_updated":"2023-09-27T12:52:38Z","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"first_name":"Alexander","last_name":"Kößler"},{"first_name":"Ulrich","last_name":"Schmid"}],"related_material":{"record":[{"id":"738","relation":"later_version","status":"public"}]},"creator":{"id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","login":"dernst"},"publist_id":"3981","ec_funded":1,"quality_controlled":"1","project":[{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"language":[{}],"conference":{"name":"HSCC: Hybrid Systems - Computation and Control","end_date":"2013-04-11","start_date":"2013-04-08","location":"Philadelphia, PA, United States"},"month":"04","publication_identifier":{"isbn":[]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"2820","oa_version":"None","type":"conference","abstract":[{"lang":"eng"}],"page":"163 - 172","publication":"Proceedings of the 16th International conference on Hybrid systems: Computation and control","citation":{"short":"K. Chatterjee, A. Kößler, U. Schmid, in:, Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, ACM, 2013, pp. 163–172.","mla":"Chatterjee, Krishnendu, et al. “Automated Analysis of Real-Time Scheduling Using Graph Games.” Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, ACM, 2013, pp. 163–72, doi:10.1145/2461328.2461356.","chicago":"Chatterjee, Krishnendu, Alexander Kößler, and Ulrich Schmid. “Automated Analysis of Real-Time Scheduling Using Graph Games.” In Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, 163–72. ACM, 2013. https://doi.org/10.1145/2461328.2461356.","ieee":"K. Chatterjee, A. Kößler, and U. Schmid, “Automated analysis of real-time scheduling using graph games,” in Proceedings of the 16th International conference on Hybrid systems: Computation and control, Philadelphia, PA, United States, 2013, pp. 163–172.","apa":"Chatterjee, K., Kößler, A., & Schmid, U. (2013). Automated analysis of real-time scheduling using graph games. In Proceedings of the 16th International conference on Hybrid systems: Computation and control (pp. 163–172). Philadelphia, PA, United States: ACM. https://doi.org/10.1145/2461328.2461356","ista":"Chatterjee K, Kößler A, Schmid U. 2013. Automated analysis of real-time scheduling using graph games. Proceedings of the 16th International conference on Hybrid systems: Computation and control. HSCC: Hybrid Systems - Computation and Control, 163–172."},"date_published":"2013-04-01T00:00:00Z","scopus_import":1,"dc":{"language":["eng"],"date":["2013"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1145/2461328.2461356","info:eu-repo/semantics/altIdentifier/isbn/978-1-4503-1567-8 ","info:eu-repo/grantAgreement/FWF//S 11407_N23","info:eu-repo/grantAgreement/FWF//S11407","info:eu-repo/grantAgreement/FWF//P 23499-N23","info:eu-repo/grantAgreement/EC/FP7/279307"],"publisher":["ACM"],"title":["Automated analysis of real-time scheduling using graph games"],"rights":["info:eu-repo/semantics/closedAccess"],"source":["Chatterjee K, Kößler A, Schmid U. Automated analysis of real-time scheduling using graph games. In: Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control. ACM; 2013:163-172. doi:10.1145/2461328.2461356"],"creator":["Chatterjee, Krishnendu","Kößler, Alexander","Schmid, Ulrich"],"description":["In this paper, we introduce the powerful framework of graph games for the analysis of real-time scheduling with firm deadlines. We introduce a novel instance of a partial-observation game that is suitable for this purpose, and prove decidability of all the involved decision problems. We derive a graph game that allows the automated computation of the competitive ratio (along with an optimal witness algorithm for the competitive ratio) and establish an NP-completeness proof for the graph game problem. For a given on-line algorithm, we present polynomial time solution for computing (i) the worst-case utility; (ii) the worst-case utility ratio w.r.t. a clairvoyant off-line algorithm; and (iii) the competitive ratio. A major strength of the proposed approach lies in its flexibility w.r.t. incorporating additional constraints on the adversary and/or the algorithm, including limited maximum or average load, finiteness of periods of overload, etc., which are easily added by means of additional instances of standard objective functions for graph games. "],"identifier":["https://research-explorer.ista.ac.at/record/2820"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"]},"day":"01","uri_base":"https://research-explorer.ista.ac.at"}]