[{"conference":{"start_date":"2023-08-28","name":"MFCS: Symposium on Mathematical Foundations of Computer Science","location":"Bordeaux, France","end_date":"2023-09-01"},"language":[{"iso":"eng"}],"project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"oa_version":"Published Version","article_number":"15","month":"08","has_accepted_license":"1","publication":"48th International Symposium on Mathematical Foundations of Computer Science","file":[{"date_updated":"2023-10-09T09:19:11Z","file_name":"2023_LIPIcsMFCS_Baier.pdf","content_type":"application/pdf","date_created":"2023-10-09T09:19:11Z","checksum":"402281b17ed669bbf149d0fdf68ac201","file_size":826843,"file_id":"14418","creator":"dernst","relation":"main_file","access_level":"open_access","success":1}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publication_identifier":{"isbn":["9783959772921"],"eissn":["1868-8969"]},"oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"conference","date_published":"2023-08-21T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","ec_funded":1,"file_date_updated":"2023-10-09T09:19:11Z","date_created":"2023-10-09T09:21:05Z","article_processing_charge":"Yes","department":[{"_id":"KrCh"}],"publication_status":"published","intvolume":"       272","alternative_title":["LIPIcs"],"title":"Entropic risk for turn-based stochastic games","scopus_import":"1","_id":"14417","author":[{"first_name":"Christel","last_name":"Baier","full_name":"Baier, Christel"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","orcid":"0000-0002-1712-2165","full_name":"Meggendorfer, Tobias","first_name":"Tobias","last_name":"Meggendorfer"},{"last_name":"Piribauer","first_name":"Jakob","full_name":"Piribauer, Jakob"}],"acknowledgement":"This work was partly funded by the ERC CoG 863818 (ForM-SMArt), the DFG Grant\r\n389792660 as part of TRR 248 (Foundations of Perspicuous Software Systems), the Cluster of\r\nExcellence EXC 2050/1 (CeTI, project ID 390696704, as part of Germany’s Excellence Strategy), and the DFG projects BA-1679/11-1 and BA-1679/12-1.","volume":272,"ddc":["000"],"day":"21","doi":"10.4230/LIPIcs.MFCS.2023.15","arxiv":1,"abstract":[{"text":"Entropic risk (ERisk) is an established risk measure in finance, quantifying risk by an exponential re-weighting of rewards. We study ERisk for the first time in the context of turn-based stochastic games with the total reward objective. This gives rise to an objective function that demands the control of systems in a risk-averse manner. We show that the resulting games are determined and, in particular, admit optimal memoryless deterministic strategies. This contrasts risk measures that previously have been considered in the special case of Markov decision processes and that require randomization and/or memory. We provide several results on the decidability and the computational complexity of the threshold problem, i.e. whether the optimal value of ERisk exceeds a given threshold. In the most general case, the problem is decidable subject to Shanuel’s conjecture. If all inputs are rational, the resulting threshold problem can be solved using algebraic numbers, leading to decidability via a polynomial-time reduction to the existential theory of the reals. Further restrictions on the encoding of the input allow the solution of the threshold problem in NP∩coNP. Finally, an approximation algorithm for the optimal value of ERisk is provided.","lang":"eng"}],"citation":{"chicago":"Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob Piribauer. “Entropic Risk for Turn-Based Stochastic Games.” In <i>48th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">https://doi.org/10.4230/LIPIcs.MFCS.2023.15</a>.","ieee":"C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Entropic risk for turn-based stochastic games,” in <i>48th International Symposium on Mathematical Foundations of Computer Science</i>, Bordeaux, France, 2023, vol. 272.","ama":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Entropic risk for turn-based stochastic games. In: <i>48th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">10.4230/LIPIcs.MFCS.2023.15</a>","apa":"Baier, C., Chatterjee, K., Meggendorfer, T., &#38; Piribauer, J. (2023). Entropic risk for turn-based stochastic games. In <i>48th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 272). Bordeaux, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">https://doi.org/10.4230/LIPIcs.MFCS.2023.15</a>","ista":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. 2023. Entropic risk for turn-based stochastic games. 48th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 272, 15.","mla":"Baier, Christel, et al. “Entropic Risk for Turn-Based Stochastic Games.” <i>48th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 272, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">10.4230/LIPIcs.MFCS.2023.15</a>.","short":"C. Baier, K. Chatterjee, T. Meggendorfer, J. Piribauer, in:, 48th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023."},"year":"2023","date_updated":"2025-07-14T09:09:57Z","external_id":{"arxiv":["2307.06611"]}},{"publication":"14th International Conference on Interactive Theorem Proving","has_accepted_license":"1","month":"07","article_number":"15","oa_version":"Published Version","language":[{"iso":"eng"}],"conference":{"start_date":"2023-07-31","name":"ITP: International Conference on Interactive Theorem Proving","end_date":"2023-08-04","location":"Bialystok, Poland"},"date_published":"2023-07-27T00:00:00Z","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959772846"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"link":[{"url":"https://github.com/madvorak/grammars/tree/publish","relation":"software"}]},"status":"public","file":[{"date_created":"2023-08-07T11:55:43Z","file_size":715976,"checksum":"773a0197f05b67feaa6cb1e17ec3642d","date_updated":"2023-08-07T11:55:43Z","file_name":"2023_LIPIcS_Dvorak.pdf","content_type":"application/pdf","relation":"main_file","success":1,"access_level":"open_access","file_id":"13982","creator":"dernst"}],"author":[{"id":"40ED02A8-C8B4-11E9-A9C0-453BE6697425","full_name":"Dvorak, Martin","orcid":"0000-0001-5293-214X","last_name":"Dvorak","first_name":"Martin"},{"full_name":"Blanchette, Jasmin","first_name":"Jasmin","last_name":"Blanchette"}],"_id":"13120","scopus_import":"1","alternative_title":["LIPIcs"],"title":"Closure properties of general grammars - formally verified","intvolume":"       268","publication_status":"published","article_processing_charge":"No","department":[{"_id":"GradSch"},{"_id":"VlKo"}],"date_created":"2023-06-05T07:29:05Z","file_date_updated":"2023-08-07T11:55:43Z","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","external_id":{"arxiv":["2302.06420"]},"date_updated":"2023-09-25T11:04:29Z","citation":{"chicago":"Dvorak, Martin, and Jasmin Blanchette. “Closure Properties of General Grammars - Formally Verified.” In <i>14th International Conference on Interactive Theorem Proving</i>, Vol. 268. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ITP.2023.15\">https://doi.org/10.4230/LIPIcs.ITP.2023.15</a>.","ieee":"M. Dvorak and J. Blanchette, “Closure properties of general grammars - formally verified,” in <i>14th International Conference on Interactive Theorem Proving</i>, Bialystok, Poland, 2023, vol. 268.","apa":"Dvorak, M., &#38; Blanchette, J. (2023). Closure properties of general grammars - formally verified. In <i>14th International Conference on Interactive Theorem Proving</i> (Vol. 268). Bialystok, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITP.2023.15\">https://doi.org/10.4230/LIPIcs.ITP.2023.15</a>","ama":"Dvorak M, Blanchette J. Closure properties of general grammars - formally verified. In: <i>14th International Conference on Interactive Theorem Proving</i>. Vol 268. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITP.2023.15\">10.4230/LIPIcs.ITP.2023.15</a>","ista":"Dvorak M, Blanchette J. 2023. Closure properties of general grammars - formally verified. 14th International Conference on Interactive Theorem Proving. ITP: International Conference on Interactive Theorem Proving, LIPIcs, vol. 268, 15.","mla":"Dvorak, Martin, and Jasmin Blanchette. “Closure Properties of General Grammars - Formally Verified.” <i>14th International Conference on Interactive Theorem Proving</i>, vol. 268, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITP.2023.15\">10.4230/LIPIcs.ITP.2023.15</a>.","short":"M. Dvorak, J. Blanchette, in:, 14th International Conference on Interactive Theorem Proving, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023."},"year":"2023","abstract":[{"text":"We formalized general (i.e., type-0) grammars using the Lean 3 proof assistant. We defined basic notions of rewrite rules and of words derived by a grammar, and used grammars to show closure of the class of type-0 languages under four operations: union, reversal, concatenation, and the Kleene star. The literature mostly focuses on Turing machine arguments, which are possibly more difficult to formalize. For the Kleene star, we could not follow the literature and came up with our own grammar-based construction.","lang":"eng"}],"doi":"10.4230/LIPIcs.ITP.2023.15","arxiv":1,"day":"27","ddc":["000"],"volume":268,"acknowledgement":"Jasmin Blanchette: This research has received funding from the Netherlands Organization\r\nfor Scientific Research (NWO) under the Vidi program (project No. 016.Vidi.189.037, Lean Forward).\r\n__\r\nWe thank Vladimir Kolmogorov for making this collaboration possible. We\r\nthank Václav Končický for discussing ideas about the Kleene star construction. We thank Patrick Johnson, Floris van Doorn, and Damiano Testa for their small yet very valuable contributions to our code. We thank Eric Wieser for simplifying one of our proofs. We thank Mark Summerfield for suggesting textual improvements. We thank the anonymous reviewers for very helpful comments. Finally, we thank the Lean community for helping us with various technical issues and answering many questions. "},{"date_updated":"2023-10-09T07:14:03Z","citation":{"ieee":"U. Boker, T. A. Henzinger, N. A. Mazzocchi, and N. E. Sarac, “Safety and liveness of quantitative automata,” in <i>34th International Conference on Concurrency Theory</i>, Antwerp, Belgium, 2023, vol. 279.","chicago":"Boker, Udi, Thomas A Henzinger, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Safety and Liveness of Quantitative Automata.” In <i>34th International Conference on Concurrency Theory</i>, Vol. 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.17\">https://doi.org/10.4230/LIPIcs.CONCUR.2023.17</a>.","apa":"Boker, U., Henzinger, T. A., Mazzocchi, N. A., &#38; Sarac, N. E. (2023). Safety and liveness of quantitative automata. In <i>34th International Conference on Concurrency Theory</i> (Vol. 279). Antwerp, Belgium: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.17\">https://doi.org/10.4230/LIPIcs.CONCUR.2023.17</a>","ama":"Boker U, Henzinger TA, Mazzocchi NA, Sarac NE. Safety and liveness of quantitative automata. In: <i>34th International Conference on Concurrency Theory</i>. Vol 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.17\">10.4230/LIPIcs.CONCUR.2023.17</a>","ista":"Boker U, Henzinger TA, Mazzocchi NA, Sarac NE. 2023. Safety and liveness of quantitative automata. 34th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 279, 17.","short":"U. Boker, T.A. Henzinger, N.A. Mazzocchi, N.E. Sarac, in:, 34th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","mla":"Boker, Udi, et al. “Safety and Liveness of Quantitative Automata.” <i>34th International Conference on Concurrency Theory</i>, vol. 279, 17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.17\">10.4230/LIPIcs.CONCUR.2023.17</a>."},"year":"2023","external_id":{"arxiv":["2307.06016"]},"doi":"10.4230/LIPIcs.CONCUR.2023.17","arxiv":1,"day":"01","abstract":[{"lang":"eng","text":"The safety-liveness dichotomy is a fundamental concept in formal languages which plays a key role in verification. Recently, this dichotomy has been lifted to quantitative properties, which are arbitrary functions from infinite words to partially-ordered domains. We look into harnessing the dichotomy for the specific classes of quantitative properties expressed by quantitative automata. These automata contain finitely many states and rational-valued transition weights, and their common value functions Inf, Sup, LimInf, LimSup, LimInfAvg, LimSupAvg, and DSum map infinite words into the totallyordered domain of real numbers. In this automata-theoretic setting, we establish a connection between quantitative safety and topological continuity and provide an alternative characterization of quantitative safety and liveness in terms of their boolean counterparts. For all common value functions, we show how the safety closure of a quantitative automaton can be constructed in PTime, and we provide PSpace-complete checks of whether a given quantitative automaton is safe or live, with the exception of LimInfAvg and LimSupAvg automata, for which the safety check is in ExpSpace. Moreover, for deterministic Sup, LimInf, and LimSup automata, we give PTime decompositions into safe and live automata. These decompositions enable the separation of techniques for safety and liveness verification for quantitative specifications."}],"volume":279,"acknowledgement":"We thank Christof Löding for pointing us to some results on PSpace-hardess of universality problems and the anonymous reviewers for their helpful comments. This work was supported in part by the ERC-2020-AdG 101020093 and the Israel Science Foundation grant 2410/22.","ddc":["000"],"_id":"13221","author":[{"id":"31E297B6-F248-11E8-B48F-1D18A9856A87","full_name":"Boker, Udi","first_name":"Udi","last_name":"Boker"},{"orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Nicolas Adrien","last_name":"Mazzocchi","full_name":"Mazzocchi, Nicolas Adrien","id":"b26baa86-3308-11ec-87b0-8990f34baa85"},{"id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425","first_name":"Naci E","last_name":"Sarac","full_name":"Sarac, Naci E"}],"publication_status":"published","date_created":"2023-07-14T10:00:15Z","department":[{"_id":"GradSch"},{"_id":"ToHe"}],"article_processing_charge":"No","title":"Safety and liveness of quantitative automata","alternative_title":["LIPIcs"],"intvolume":"       279","ec_funded":1,"quality_controlled":"1","file_date_updated":"2023-07-14T12:03:48Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2023-09-01T00:00:00Z","type":"conference","publication_identifier":{"isbn":["9783959772990"],"eissn":["1868-8969"]},"oa":1,"file":[{"file_id":"13224","creator":"esarac","access_level":"open_access","relation":"main_file","success":1,"date_updated":"2023-07-14T12:03:48Z","content_type":"application/pdf","file_name":"CONCUR23.pdf","date_created":"2023-07-14T12:03:48Z","file_size":755529,"checksum":"d40e57a04448ea5c77d7e1cfb9590a81"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"34th International Conference on Concurrency Theory","has_accepted_license":"1","oa_version":"Published Version","project":[{"name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093","call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d"}],"month":"09","article_number":"17","language":[{"iso":"eng"}],"conference":{"start_date":"2023-09-18","name":"CONCUR: Conference on Concurrency Theory","location":"Antwerp, Belgium","end_date":"2023-09-23"}},{"conference":{"end_date":"2023-07-14","location":"Paderborn, Germany","name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"2023-07-10"},"language":[{"iso":"eng"}],"month":"07","project":[{"call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093"}],"oa_version":"Published Version","has_accepted_license":"1","publication":"50th International Colloquium on Automata, Languages, and Programming","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_name":"icalp23.pdf","content_type":"application/pdf","date_updated":"2023-07-24T15:11:05Z","file_size":859379,"checksum":"5d4c8932ef3450615a53b9bb15d92eb2","date_created":"2023-07-24T15:11:05Z","creator":"esarac","file_id":"13293","access_level":"open_access","relation":"main_file","success":1}],"oa":1,"publication_identifier":{"isbn":["9783959772785"],"eissn":["1868-8969"]},"type":"conference","date_published":"2023-07-05T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2023-07-24T15:11:05Z","ec_funded":1,"quality_controlled":"1","page":"129:1--129:20","intvolume":"       261","title":"Regular methods for operator precedence languages","alternative_title":["LIPIcs"],"date_created":"2023-07-24T15:11:41Z","article_processing_charge":"Yes","department":[{"_id":"GradSch"},{"_id":"ToHe"}],"publication_status":"published","author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724"},{"full_name":"Kebis, Pavol","last_name":"Kebis","first_name":"Pavol"},{"id":"b26baa86-3308-11ec-87b0-8990f34baa85","first_name":"Nicolas Adrien","last_name":"Mazzocchi","full_name":"Mazzocchi, Nicolas Adrien"},{"id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425","full_name":"Sarac, Naci E","first_name":"Naci E","last_name":"Sarac"}],"_id":"13292","ddc":["000"],"volume":261,"acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093.\r\nWe thank Pierre Ganty for early discussions and the anonymous reviewers for their helpful comments.\r\n","abstract":[{"text":"The operator precedence languages (OPLs) represent the largest known subclass of the context-free languages which enjoys all desirable closure and decidability properties. This includes the decidability of language inclusion, which is the ultimate verification problem. Operator precedence grammars, automata, and logics have been investigated and used, for example, to verify programs with arithmetic expressions and exceptions (both of which are deterministic pushdown but lie outside the scope of the visibly pushdown languages). In this paper, we complete the picture and give, for the first time, an algebraic characterization of the class of OPLs in the form of a syntactic congruence that has finitely many equivalence classes exactly for the operator precedence languages. This is a generalization of the celebrated Myhill-Nerode theorem for the regular languages to OPLs. As one of the consequences, we show that universality and language inclusion for nondeterministic operator precedence automata can be solved by an antichain algorithm. Antichain algorithms avoid determinization and complementation through an explicit subset construction, by leveraging a quasi-order on words, which allows the pruning of the search space for counterexample words without sacrificing completeness. Antichain algorithms can be implemented symbolically, and these implementations are today the best-performing algorithms in practice for the inclusion of finite automata. We give a generic construction of the quasi-order needed for antichain algorithms from a finite syntactic congruence. This yields the first antichain algorithm for OPLs, an algorithm that solves the ExpTime-hard language inclusion problem for OPLs in exponential time.","lang":"eng"}],"day":"05","doi":"10.4230/LIPIcs.ICALP.2023.129","arxiv":1,"external_id":{"arxiv":["2305.03447"]},"year":"2023","citation":{"chicago":"Henzinger, Thomas A, Pavol Kebis, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Regular Methods for Operator Precedence Languages.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, 261:129:1--129:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">https://doi.org/10.4230/LIPIcs.ICALP.2023.129</a>.","ieee":"T. A. Henzinger, P. Kebis, N. A. Mazzocchi, and N. E. Sarac, “Regular methods for operator precedence languages,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261, p. 129:1--129:20.","apa":"Henzinger, T. A., Kebis, P., Mazzocchi, N. A., &#38; Sarac, N. E. (2023). Regular methods for operator precedence languages. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261, p. 129:1--129:20). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">https://doi.org/10.4230/LIPIcs.ICALP.2023.129</a>","ama":"Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. Regular methods for operator precedence languages. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023:129:1--129:20. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">10.4230/LIPIcs.ICALP.2023.129</a>","ista":"Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. 2023. Regular methods for operator precedence languages. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 129:1--129:20.","mla":"Henzinger, Thomas A., et al. “Regular Methods for Operator Precedence Languages.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, p. 129:1--129:20, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">10.4230/LIPIcs.ICALP.2023.129</a>.","short":"T.A. Henzinger, P. Kebis, N.A. Mazzocchi, N.E. Sarac, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, p. 129:1--129:20."},"date_updated":"2023-07-31T08:38:38Z"},{"type":"conference","date_published":"2022-04-29T00:00:00Z","publication_identifier":{"isbn":["9783959772242"],"eissn":["1868-8969"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.SAND.2022.1"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"1st Symposium on Algorithmic Foundations of Dynamic Networks","oa_version":"Published Version","article_number":"1","month":"04","language":[{"iso":"eng"}],"conference":{"location":"Virtual","end_date":"2022-03-30","name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","start_date":"2022-03-28"},"year":"2022","citation":{"apa":"Hanauer, K., Henzinger, M. H., &#38; Schulz, C. (2022). Recent advances in fully dynamic graph algorithms. In <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i> (Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">https://doi.org/10.4230/LIPIcs.SAND.2022.1</a>","ama":"Hanauer K, Henzinger MH, Schulz C. Recent advances in fully dynamic graph algorithms. In: <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>. Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">10.4230/LIPIcs.SAND.2022.1</a>","chicago":"Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Recent Advances in Fully Dynamic Graph Algorithms.” In <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">https://doi.org/10.4230/LIPIcs.SAND.2022.1</a>.","ieee":"K. Hanauer, M. H. Henzinger, and C. Schulz, “Recent advances in fully dynamic graph algorithms,” in <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, Virtual, 2022, vol. 221.","mla":"Hanauer, Kathrin, et al. “Recent Advances in Fully Dynamic Graph Algorithms.” <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 221, 1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">10.4230/LIPIcs.SAND.2022.1</a>.","short":"K. Hanauer, M.H. Henzinger, C. Schulz, in:, 1st Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ista":"Hanauer K, Henzinger MH, Schulz C. 2022. Recent advances in fully dynamic graph algorithms. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 1."},"date_updated":"2023-02-14T08:14:41Z","external_id":{"arxiv":["2102.11169"]},"day":"29","arxiv":1,"doi":"10.4230/LIPIcs.SAND.2022.1","abstract":[{"lang":"eng","text":"In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms."}],"volume":221,"extern":"1","scopus_import":"1","_id":"11808","author":[{"full_name":"Hanauer, Kathrin","last_name":"Hanauer","first_name":"Kathrin"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Schulz","first_name":"Christian","full_name":"Schulz, Christian"}],"article_processing_charge":"No","date_created":"2022-08-11T14:35:52Z","publication_status":"published","intvolume":"       221","alternative_title":["LIPIcs"],"title":"Recent advances in fully dynamic graph algorithms","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"date_updated":"2023-01-27T06:59:29Z","citation":{"mla":"Pacut, Maciej, et al. “Brief Announcement: Temporal Locality in Online Algorithms.” <i>36th International Symposium on Distributed Computing</i>, vol. 246, 52, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2022.52\">10.4230/LIPIcs.DISC.2022.52</a>.","short":"M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, A. Tereshchenko, in:, 36th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ista":"Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. 2022. Brief announcement: Temporal locality in online algorithms. 36th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing vol. 246, 52.","ama":"Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. Brief announcement: Temporal locality in online algorithms. In: <i>36th International Symposium on Distributed Computing</i>. Vol 246. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2022.52\">10.4230/LIPIcs.DISC.2022.52</a>","apa":"Pacut, M., Parham, M., Rybicki, J., Schmid, S., Suomela, J., &#38; Tereshchenko, A. (2022). Brief announcement: Temporal locality in online algorithms. In <i>36th International Symposium on Distributed Computing</i> (Vol. 246). Augusta, GA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2022.52\">https://doi.org/10.4230/LIPIcs.DISC.2022.52</a>","ieee":"M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, and A. Tereshchenko, “Brief announcement: Temporal locality in online algorithms,” in <i>36th International Symposium on Distributed Computing</i>, Augusta, GA, United States, 2022, vol. 246.","chicago":"Pacut, Maciej, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, and Aleksandr Tereshchenko. “Brief Announcement: Temporal Locality in Online Algorithms.” In <i>36th International Symposium on Distributed Computing</i>, Vol. 246. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2022.52\">https://doi.org/10.4230/LIPIcs.DISC.2022.52</a>."},"year":"2022","doi":"10.4230/LIPIcs.DISC.2022.52","day":"17","abstract":[{"lang":"eng","text":"Online algorithms make decisions based on past inputs, with the goal of being competitive against an algorithm that sees also future inputs. In this work, we introduce time-local online algorithms; these are online algorithms in which the output at any given time is a function of only T latest inputs. Our main observation is that time-local online algorithms are closely connected to local distributed graph algorithms: distributed algorithms make decisions based on the local information in the spatial dimension, while time-local online algorithms make decisions based on the local information in the temporal dimension. We formalize this connection, and show how we can directly use the tools developed to study distributed approximability of graph optimization problems to prove upper and lower bounds on the competitive ratio achieved with time-local online algorithms. Moreover, we show how to use computational techniques to synthesize optimal time-local algorithms."}],"volume":246,"acknowledgement":"This research has received funding from the German Research Foundation (DFG), grant\r\n470029389 (FlexNets), 2021-2024, and the Marie Skłodowska-Curie grant agreement No. 840605.","ddc":["000"],"_id":"12182","scopus_import":"1","author":[{"full_name":"Pacut, Maciej","first_name":"Maciej","last_name":"Pacut"},{"full_name":"Parham, Mahmoud","last_name":"Parham","first_name":"Mahmoud"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki","first_name":"Joel","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646"},{"full_name":"Schmid, Stefan","first_name":"Stefan","last_name":"Schmid"},{"full_name":"Suomela, Jukka","first_name":"Jukka","last_name":"Suomela"},{"full_name":"Tereshchenko, Aleksandr","last_name":"Tereshchenko","first_name":"Aleksandr"}],"publication_status":"published","article_processing_charge":"No","date_created":"2023-01-13T11:06:28Z","department":[{"_id":"DaAl"}],"title":"Brief announcement: Temporal locality in online algorithms","intvolume":"       246","quality_controlled":"1","ec_funded":1,"file_date_updated":"2023-01-27T06:58:02Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2022-10-17T00:00:00Z","type":"conference","publication_identifier":{"eisbn":["9783959772556"],"eissn":["1868-8969"]},"oa":1,"file":[{"access_level":"open_access","success":1,"relation":"main_file","file_id":"12409","creator":"dernst","date_created":"2023-01-27T06:58:02Z","file_size":524804,"checksum":"11bbb56f68a00f2cf6bcce6cc7f5c5f9","date_updated":"2023-01-27T06:58:02Z","file_name":"2022_LIPICs_Pacut.pdf","content_type":"application/pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publication":"36th International Symposium on Distributed Computing","has_accepted_license":"1","oa_version":"Published Version","project":[{"grant_number":"840605","name":"Coordination in constrained and natural distributed systems","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"month":"10","article_number":"52","language":[{"iso":"eng"}],"conference":{"end_date":"2022-10-27","location":"Augusta, GA, United States","name":"DISC: Symposium on Distributed Computing","start_date":"2022-10-25"}}]