[{"oa":1,"title":"Scalable enumeration of trap spaces in boolean networks via answer set programming","publication_identifier":{"issn":["2159-5399"],"eissn":["2374-3468"],"isbn":["1577358872"]},"type":"conference","doi":"10.1609/aaai.v38i9.28943","main_file_link":[{"open_access":"1","url":"https://amu.hal.science/hal-04523118/"}],"publication":"Proceedings of the 38th AAAI Conference on Artificial Intelligence","author":[{"first_name":"Giang","last_name":"Trinh","full_name":"Trinh, Giang"},{"last_name":"Benhamou","full_name":"Benhamou, Belaid","first_name":"Belaid"},{"first_name":"Samuel","orcid":"0000-0003-1993-0331","last_name":"Pastva","id":"07c5ea74-f61c-11ec-a664-aa7c5d957b2b","full_name":"Pastva, Samuel"},{"last_name":"Soliman","full_name":"Soliman, Sylvain","first_name":"Sylvain"}],"scopus_import":"1","project":[{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","grant_number":"101034413"}],"quality_controlled":"1","article_processing_charge":"No","date_created":"2024-04-14T22:01:02Z","supplementarymaterial":"yes","month":"03","page":"10714-10722","publication_status":"published","volume":38,"language":[{"iso":"eng"}],"department":[{"_id":"ToHe"}],"date_published":"2024-03-25T00:00:00Z","ddc":["000"],"fulldoi":"https://doi.org/10.1609/aaai.v38i9.28943","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"text":"Boolean Networks (BNs) are widely used as a modeling formalism in several domains, notably systems biology and computer science. A fundamental problem in BN analysis is the enumeration of trap spaces, which are hypercubes in the state space that cannot be escaped once entered. Several methods have been proposed for enumerating trap spaces, however they often suffer from scalability and efficiency issues, particularly for large and complex models. To our knowledge, the most efficient and recent methods for the trap space enumeration all rely on Answer Set Programming (ASP), which has been widely applied to the analysis of BNs. Motivated by these considerations, our work proposes a new method for enumerating trap spaces in BNs using ASP. We evaluate the method on a mix of 250+ real-world and 400+ randomly generated BNs, showing that it enables analysis of models beyond the capabilities of existing tools (namely pyboolnet, mpbn, trappist, and trapmvn).","lang":"eng"}],"ec_funded":1,"date_updated":"2026-10-21T12:04:20Z","issue":"9","intvolume":"        38","das_tickbox":"0","day":"25","publisher":"Association for the Advancement of Artificial Intelligence","citation":{"chicago":"Trinh, Giang, Belaid Benhamou, Samuel Pastva, and Sylvain Soliman. “Scalable Enumeration of Trap Spaces in Boolean Networks via Answer Set Programming.” In <i>Proceedings of the 38th AAAI Conference on Artificial Intelligence</i>, 38:10714–22. Association for the Advancement of Artificial Intelligence, 2024. <a href=\"https://doi.org/10.1609/aaai.v38i9.28943\">https://doi.org/10.1609/aaai.v38i9.28943</a>.","mla":"Trinh, Giang, et al. “Scalable Enumeration of Trap Spaces in Boolean Networks via Answer Set Programming.” <i>Proceedings of the 38th AAAI Conference on Artificial Intelligence</i>, vol. 38, no. 9, Association for the Advancement of Artificial Intelligence, 2024, pp. 10714–22, doi:<a href=\"https://doi.org/10.1609/aaai.v38i9.28943\">10.1609/aaai.v38i9.28943</a>.","short":"G. Trinh, B. Benhamou, S. Pastva, S. Soliman, in:, Proceedings of the 38th AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence, 2024, pp. 10714–10722.","ama":"Trinh G, Benhamou B, Pastva S, Soliman S. Scalable enumeration of trap spaces in boolean networks via answer set programming. In: <i>Proceedings of the 38th AAAI Conference on Artificial Intelligence</i>. Vol 38. Association for the Advancement of Artificial Intelligence; 2024:10714-10722. doi:<a href=\"https://doi.org/10.1609/aaai.v38i9.28943\">10.1609/aaai.v38i9.28943</a>","ista":"Trinh G, Benhamou B, Pastva S, Soliman S. 2024. Scalable enumeration of trap spaces in boolean networks via answer set programming. Proceedings of the 38th AAAI Conference on Artificial Intelligence. vol. 38, 10714–10722.","ieee":"G. Trinh, B. Benhamou, S. Pastva, and S. Soliman, “Scalable enumeration of trap spaces in boolean networks via answer set programming,” in <i>Proceedings of the 38th AAAI Conference on Artificial Intelligence</i>, 2024, vol. 38, no. 9, pp. 10714–10722.","apa":"Trinh, G., Benhamou, B., Pastva, S., &#38; Soliman, S. (2024). Scalable enumeration of trap spaces in boolean networks via answer set programming. In <i>Proceedings of the 38th AAAI Conference on Artificial Intelligence</i> (Vol. 38, pp. 10714–10722). Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v38i9.28943\">https://doi.org/10.1609/aaai.v38i9.28943</a>"},"acknowledgement":"This work was supported by Institut Carnot STAR, Marseille, France and by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 101034413.","year":"2024","_id":"15321","status":"public","researchdata_availability":"yes (supplementary data)","oa_version":"Published Version"},{"date_published":"2024-10-12T00:00:00Z","has_accepted_license":"1","OA_type":"hybrid","ddc":["000"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.1007/978-3-031-74234-7_18","OA_place":"publisher","date_updated":"2026-10-21T13:14:54Z","alternative_title":["LNCS"],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"abstract":[{"text":"In distributed systems with processes that do not share a global clock, partial synchrony is achieved by clock synchronization that guarantees bounded clock skew among all applications. Existing solutions for distributed runtime verification under partial synchrony against temporal logic specifications are exact but suffer from significant computational overhead. In this paper, we propose an approximate distributed monitoring algorithm for Signal Temporal Logic (STL) that mitigates this issue by abstracting away potential interleaving behaviors. This conservative abstraction enables a significant speedup of the distributed monitors, albeit with a tradeoff in accuracy. We address this tradeoff with a methodology that combines our approximate monitor with its exact counterpart, resulting in enhanced efficiency without sacrificing precision. We evaluate our approach with multiple experiments, showcasing its efficacy in both real-world applications and synthetic examples.","lang":"eng"}],"file_date_updated":"2024-11-11T09:42:28Z","external_id":{"isi":["001420093700018"],"arxiv":["2408.05033"]},"intvolume":"     15191","file":[{"date_updated":"2024-11-11T09:42:28Z","content_type":"application/pdf","creator":"dernst","access_level":"open_access","checksum":"7b8ca21b8c19ab796fa445b0e54003ca","relation":"main_file","file_name":"2024_LNCS_Bonakdarpour.pdf","date_created":"2024-11-11T09:42:28Z","file_size":1897101,"success":1,"file_id":"18539"}],"_id":"18521","researchdata_availability":"no","status":"public","oa_version":"Published Version","isi":1,"arxiv":1,"day":"12","das_tickbox":"0","publisher":"Springer Nature","acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093. This work is sponsored in part by the United States NSF CCF-2118356 award. This research was partially funded by A-IQ Ready (Chips JU, grant agreement No. 101096658).","year":"2024","citation":{"ama":"Bonakdarpour B, Momtaz A, Nickovic D, Sarac NE. Approximate distributed monitoring under partial synchrony: Balancing speed &#38; accuracy. In: <i>24th International Conference on Runtime Verification</i>. Vol 15191. Springer Nature; 2024:282-301. doi:<a href=\"https://doi.org/10.1007/978-3-031-74234-7_18\">10.1007/978-3-031-74234-7_18</a>","ista":"Bonakdarpour B, Momtaz A, Nickovic D, Sarac NE. 2024. Approximate distributed monitoring under partial synchrony: Balancing speed &#38; accuracy. 24th International Conference on Runtime Verification. RV: Conference on Runtime Verification, LNCS, vol. 15191, 282–301.","ieee":"B. Bonakdarpour, A. Momtaz, D. Nickovic, and N. E. Sarac, “Approximate distributed monitoring under partial synchrony: Balancing speed &#38; accuracy,” in <i>24th International Conference on Runtime Verification</i>, Istanbul, Turkey, 2024, vol. 15191, pp. 282–301.","apa":"Bonakdarpour, B., Momtaz, A., Nickovic, D., &#38; Sarac, N. E. (2024). Approximate distributed monitoring under partial synchrony: Balancing speed &#38; accuracy. In <i>24th International Conference on Runtime Verification</i> (Vol. 15191, pp. 282–301). Istanbul, Turkey: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-74234-7_18\">https://doi.org/10.1007/978-3-031-74234-7_18</a>","chicago":"Bonakdarpour, Borzoo, Anik Momtaz, Dejan Nickovic, and Naci E Sarac. “Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed &#38; Accuracy.” In <i>24th International Conference on Runtime Verification</i>, 15191:282–301. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-74234-7_18\">https://doi.org/10.1007/978-3-031-74234-7_18</a>.","mla":"Bonakdarpour, Borzoo, et al. “Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed &#38; Accuracy.” <i>24th International Conference on Runtime Verification</i>, vol. 15191, Springer Nature, 2024, pp. 282–301, doi:<a href=\"https://doi.org/10.1007/978-3-031-74234-7_18\">10.1007/978-3-031-74234-7_18</a>.","short":"B. Bonakdarpour, A. Momtaz, D. Nickovic, N.E. Sarac, in:, 24th International Conference on Runtime Verification, Springer Nature, 2024, pp. 282–301."},"title":"Approximate distributed monitoring under partial synchrony: Balancing speed & accuracy","oa":1,"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783031742330"]},"type":"conference","doi":"10.1007/978-3-031-74234-7_18","conference":{"end_date":"2024-10-17","name":"RV: Conference on Runtime Verification","location":"Istanbul, Turkey","start_date":"2024-10-15"},"corr_author":"1","scopus_import":"1","publication":"24th International Conference on Runtime Verification","author":[{"full_name":"Bonakdarpour, Borzoo","last_name":"Bonakdarpour","first_name":"Borzoo"},{"first_name":"Anik","last_name":"Momtaz","full_name":"Momtaz, Anik"},{"first_name":"Dejan","last_name":"Nickovic","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","full_name":"Nickovic, Dejan"},{"full_name":"Sarac, Naci E","last_name":"Sarac","id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425","first_name":"Naci E"}],"article_processing_charge":"Yes (in subscription journal)","APC_amount":"2748 EUR","supplementarymaterial":"no","date_created":"2024-11-10T23:01:58Z","project":[{"call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093"}],"quality_controlled":"1","page":"282-301","publication_status":"published","department":[{"_id":"ToHe"},{"_id":"GradSch"}],"volume":15191,"language":[{"iso":"eng"}],"month":"10"},{"OA_place":"publisher","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.CONCUR.2024.29","has_accepted_license":"1","date_published":"2024-09-01T00:00:00Z","OA_type":"gold","ddc":["000"],"ec_funded":1,"file_date_updated":"2024-09-17T07:48:56Z","abstract":[{"lang":"eng","text":"We study the following refinement relation between nondeterministic state-transition models: model ℬ strategically dominates model 𝒜 iff every deterministic refinement of 𝒜 is language contained in some deterministic refinement of ℬ. While language containment is trace inclusion, and the (fair) simulation preorder coincides with tree inclusion, strategic dominance falls strictly between the two and can be characterized as \"strategy inclusion\" between 𝒜 and ℬ: every strategy that resolves the nondeterminism of 𝒜 is dominated by a strategy that resolves the nondeterminism of ℬ. Strategic dominance can be checked in 2-ExpTime by a decidable first-order Presburger logic with quantification over words and strategies, called resolver logic. We give several other applications of resolver logic, including checking the co-safety, co-liveness, and history-determinism of boolean and quantitative automata, and checking the inclusion between hyperproperties that are specified by nondeterministic boolean and quantitative automata."}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2026-10-21T13:15:11Z","alternative_title":["LIPIcs"],"intvolume":"       311","file":[{"checksum":"555bd343e1fb38adeab8fc465ff4fad8","access_level":"open_access","relation":"main_file","creator":"dernst","content_type":"application/pdf","date_updated":"2024-09-17T07:48:56Z","success":1,"file_id":"18081","file_size":964124,"date_created":"2024-09-17T07:48:56Z","file_name":"2024_LIPICS_Henzinger.pdf"}],"external_id":{"isi":["001556847400029"],"arxiv":["2407.10473"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093. N. Mazzocchi was affiliated with ISTA when this work was submitted for publication.","year":"2024","citation":{"chicago":"Henzinger, Thomas A, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Strategic Dominance: A New Preorder for Nondeterministic Processes.” In <i>35th International Conference on Concurrency Theory</i>, Vol. 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.29\">https://doi.org/10.4230/LIPIcs.CONCUR.2024.29</a>.","short":"T.A. Henzinger, N.A. Mazzocchi, N.E. Sarac, in:, 35th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Henzinger, Thomas A., et al. “Strategic Dominance: A New Preorder for Nondeterministic Processes.” <i>35th International Conference on Concurrency Theory</i>, vol. 311, 29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.29\">10.4230/LIPIcs.CONCUR.2024.29</a>.","ama":"Henzinger TA, Mazzocchi NA, Sarac NE. Strategic dominance: A new preorder for nondeterministic processes. In: <i>35th International Conference on Concurrency Theory</i>. Vol 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.29\">10.4230/LIPIcs.CONCUR.2024.29</a>","ista":"Henzinger TA, Mazzocchi NA, Sarac NE. 2024. Strategic dominance: A new preorder for nondeterministic processes. 35th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 311, 29.","apa":"Henzinger, T. A., Mazzocchi, N. A., &#38; Sarac, N. E. (2024). Strategic dominance: A new preorder for nondeterministic processes. In <i>35th International Conference on Concurrency Theory</i> (Vol. 311). Calgary, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.29\">https://doi.org/10.4230/LIPIcs.CONCUR.2024.29</a>","ieee":"T. A. Henzinger, N. A. Mazzocchi, and N. E. Sarac, “Strategic dominance: A new preorder for nondeterministic processes,” in <i>35th International Conference on Concurrency Theory</i>, Calgary, Canada, 2024, vol. 311."},"isi":1,"arxiv":1,"day":"01","das_tickbox":"0","oa_version":"Published Version","researchdata_availability":"no","_id":"18068","status":"public","article_number":"29","type":"conference","doi":"10.4230/LIPIcs.CONCUR.2024.29","oa":1,"title":"Strategic dominance: A new preorder for nondeterministic processes","publication_identifier":{"isbn":["9783959773393"],"issn":["1868-8969"]},"author":[{"first_name":"Thomas A","orcid":"0000-0002-2985-7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"},{"first_name":"Nicolas Adrien","full_name":"Mazzocchi, Nicolas Adrien","id":"b26baa86-3308-11ec-87b0-8990f34baa85","last_name":"Mazzocchi"},{"first_name":"Naci E","last_name":"Sarac","id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425","full_name":"Sarac, Naci E"}],"publication":"35th International Conference on Concurrency Theory","scopus_import":"1","conference":{"start_date":"2024-09-09","name":"CONCUR: Conference on Concurrency Theory","end_date":"2024-09-13","location":"Calgary, Canada"},"corr_author":"1","quality_controlled":"1","project":[{"call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093"}],"article_processing_charge":"Yes","date_created":"2024-09-15T22:01:40Z","supplementarymaterial":"no","month":"09","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"ToHe"},{"_id":"GradSch"}],"volume":311},{"publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"ToHe"}],"volume":313,"month":"09","article_processing_charge":"No","supplementarymaterial":"no","date_created":"2024-10-06T22:01:12Z","quality_controlled":"1","conference":{"location":"Vienna, Austria","name":"ECOOP: European Conference on Object-Oriented Programming","end_date":"2024-09-20","start_date":"2024-09-16"},"scopus_import":"1","publication":"38th European Conference on Object-Oriented Programming","author":[{"first_name":"Petr","full_name":"Maj, Petr","last_name":"Maj"},{"full_name":"Muroya Lei, Stefanie","last_name":"Muroya Lei","id":"a376de31-8972-11ed-ae7b-d0251c13c8ff","first_name":"Stefanie"},{"full_name":"Siek, Konrad","last_name":"Siek","first_name":"Konrad"},{"first_name":"Luca","full_name":"Di Grazia, Luca","last_name":"Di Grazia"},{"first_name":"Jan","last_name":"Vitek","full_name":"Vitek, Jan"}],"title":"The fault in our stars: Designing reproducible large-scale code analysis experiments","oa":1,"publication_identifier":{"isbn":["9783959773416"],"issn":["1868-8969"]},"type":"conference","doi":"10.4230/LIPIcs.ECOOP.2024.27","article_number":"27","_id":"18175","status":"public","researchdata_availability":"no","oa_version":"Published Version","isi":1,"das_tickbox":"0","day":"01","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","acknowledgement":"This work was supported by the Czech Ministry of Education, Youth and Sports under\r\nprogram ERC-CZ, grant agreement LL2325, BigCode (reg. no. CZ.02.1.01/0.0/0.0/15_003/0000421). NSF grants CCF-1910850, CNS-1925644, and CCF-2139612, as well as the GACR EXPRO grant 23-07580X. We would like to thank Digital Ocean for their involuntary contribution of computational resources during the early data gathering phase of our research. We acknoweldge the reviewers of ICSE’22, and thank the reviewers of ECOOP’23 for their encouragments and for sticking around until 2024.","year":"2024","citation":{"ama":"Maj P, Muroya Lei S, Siek K, Di Grazia L, Vitek J. The fault in our stars: Designing reproducible large-scale code analysis experiments. In: <i>38th European Conference on Object-Oriented Programming</i>. Vol 313. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ECOOP.2024.27\">10.4230/LIPIcs.ECOOP.2024.27</a>","ista":"Maj P, Muroya Lei S, Siek K, Di Grazia L, Vitek J. 2024. The fault in our stars: Designing reproducible large-scale code analysis experiments. 38th European Conference on Object-Oriented Programming. ECOOP: European Conference on Object-Oriented Programming, LIPIcs, vol. 313, 27.","ieee":"P. Maj, S. Muroya Lei, K. Siek, L. Di Grazia, and J. Vitek, “The fault in our stars: Designing reproducible large-scale code analysis experiments,” in <i>38th European Conference on Object-Oriented Programming</i>, Vienna, Austria, 2024, vol. 313.","apa":"Maj, P., Muroya Lei, S., Siek, K., Di Grazia, L., &#38; Vitek, J. (2024). The fault in our stars: Designing reproducible large-scale code analysis experiments. In <i>38th European Conference on Object-Oriented Programming</i> (Vol. 313). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ECOOP.2024.27\">https://doi.org/10.4230/LIPIcs.ECOOP.2024.27</a>","chicago":"Maj, Petr, Stefanie Muroya Lei, Konrad Siek, Luca Di Grazia, and Jan Vitek. “The Fault in Our Stars: Designing Reproducible Large-Scale Code Analysis Experiments.” In <i>38th European Conference on Object-Oriented Programming</i>, Vol. 313. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ECOOP.2024.27\">https://doi.org/10.4230/LIPIcs.ECOOP.2024.27</a>.","short":"P. Maj, S. Muroya Lei, K. Siek, L. Di Grazia, J. Vitek, in:, 38th European Conference on Object-Oriented Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Maj, Petr, et al. “The Fault in Our Stars: Designing Reproducible Large-Scale Code Analysis Experiments.” <i>38th European Conference on Object-Oriented Programming</i>, vol. 313, 27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ECOOP.2024.27\">10.4230/LIPIcs.ECOOP.2024.27</a>."},"external_id":{"isi":["001533999700027"]},"intvolume":"       313","file":[{"relation":"main_file","access_level":"open_access","checksum":"2e75d305a8c817d76a0c7f136ce34f86","date_updated":"2024-10-07T11:10:55Z","content_type":"application/pdf","creator":"dernst","file_id":"18184","success":1,"file_name":"2024_LIPICs_Maj.pdf","date_created":"2024-10-07T11:10:55Z","file_size":1764222}],"alternative_title":["LIPIcs"],"date_updated":"2026-10-21T13:11:58Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","file_date_updated":"2024-10-07T11:10:55Z","abstract":[{"lang":"eng","text":"Large-scale software repositories are a source of insights for software engineering. They offer an unmatched window into the software development process at scale. Their sheer number and size holds the promise of broadly applicable results. At the same time, that very size presents practical challenges for scaling tools and algorithms to millions of projects. A reasonable approach is to limit studies to representative samples of the population of interest. Broadly applicable conclusions can then be obtained by generalizing to the entire population. The contribution of this paper is a standardized experimental design methodology for choosing the inputs of studies working with large-scale repositories. We advocate for a methodology that clearly lays out what the population of interest is, how to sample it, and that fosters reproducibility. Along the way, we discourage researchers from using extrinsic attributes of projects such as stars, that measure some unclear notion of popularity."}],"date_published":"2024-09-01T00:00:00Z","has_accepted_license":"1","ddc":["000"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.ECOOP.2024.27"},{"OA_place":"publisher","DOAJ_listed":"1","fulldoi":"https://doi.org/10.46298/lmcs-20(4:1)2024","article_type":"original","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["000"],"has_accepted_license":"1","OA_type":"gold","date_published":"2024-10-02T00:00:00Z","file_date_updated":"2024-11-11T08:32:02Z","ec_funded":1,"abstract":[{"lang":"eng","text":"We explore the notion of history-determinism in the context of timed automata (TA) over infinite timed words. History-deterministic (HD) automata are those in which nondeterminism can be resolved on the fly, based on the run constructed thus far. History-determinism is a robust property that admits different game-based characterisations, and HD specifications allow for game-based verification without an expensive determinization step. We show that the class of timed ω\r\n-languages recognized by HD timed automata strictly extends that of deterministic ones, and is strictly included in those recognised by fully non-deterministic TA. For non-deterministic timed automata it is known that universality is already undecidable for safety/reachability TA. For history-deterministic TA with arbitrary parity acceptance, we show that timed universality, inclusion, and synthesis all remain decidable and are EXPTIME-complete. For the subclass of TA with safety or reachability acceptance, one can decide (in EXPTIME) whether such an automaton is history-deterministic. If so, it can effectively determinized without introducing new automaton states."}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2026-10-21T13:12:37Z","file":[{"success":1,"file_id":"18532","date_created":"2024-11-11T08:32:02Z","file_size":563394,"file_name":"2024_LMCS_Bose.pdf","access_level":"open_access","checksum":"26826786a960039b9501cfc5cb4f3fe6","relation":"main_file","creator":"dernst","date_updated":"2024-11-11T08:32:02Z","content_type":"application/pdf"}],"intvolume":"        20","external_id":{"isi":["001332466900002"],"arxiv":["2304.03183"]},"issue":"4","acknowledgement":"This work has in parts been presented at the 33rd International Conference on Concurrency Theory (CONCUR’22) [HLT22] and at the 16th International Workshop on Reachability Problems (RP’22) [BHL+22]. This work was supported by the EU (ERC-2020-AdG 101020093); the EPSRC (EP/V025848/1, EP/X042596/1, EP/X017796/1 and EP/X03688X/1); and the ANR (QUASY 23-CE48-0008-01).","year":"2024","citation":{"mla":"Bose, Sougata, et al. “History-Deterministic Timed Automata.” <i>Logical Methods in Computer Science</i>, vol. 20, no. 4, EPI Sciences, 2024, pp. 1–28, doi:<a href=\"https://doi.org/10.46298/lmcs-20(4:1)2024\">10.46298/lmcs-20(4:1)2024</a>.","short":"S. Bose, T.A. Henzinger, K. Lehtinen, S. Schewe, P. Totzke, Logical Methods in Computer Science 20 (2024) 1–28.","chicago":"Bose, Sougata, Thomas A Henzinger, Karoliina Lehtinen, Sven Schewe, and Patrick Totzke. “History-Deterministic Timed Automata.” <i>Logical Methods in Computer Science</i>. EPI Sciences, 2024. <a href=\"https://doi.org/10.46298/lmcs-20(4:1)2024\">https://doi.org/10.46298/lmcs-20(4:1)2024</a>.","ieee":"S. Bose, T. A. Henzinger, K. Lehtinen, S. Schewe, and P. Totzke, “History-deterministic timed automata,” <i>Logical Methods in Computer Science</i>, vol. 20, no. 4. EPI Sciences, pp. 1–28, 2024.","apa":"Bose, S., Henzinger, T. A., Lehtinen, K., Schewe, S., &#38; Totzke, P. (2024). History-deterministic timed automata. <i>Logical Methods in Computer Science</i>. EPI Sciences. <a href=\"https://doi.org/10.46298/lmcs-20(4:1)2024\">https://doi.org/10.46298/lmcs-20(4:1)2024</a>","ama":"Bose S, Henzinger TA, Lehtinen K, Schewe S, Totzke P. History-deterministic timed automata. <i>Logical Methods in Computer Science</i>. 2024;20(4):1-28. doi:<a href=\"https://doi.org/10.46298/lmcs-20(4:1)2024\">10.46298/lmcs-20(4:1)2024</a>","ista":"Bose S, Henzinger TA, Lehtinen K, Schewe S, Totzke P. 2024. History-deterministic timed automata. Logical Methods in Computer Science. 20(4), 1–28."},"publisher":"EPI Sciences","das_tickbox":"0","arxiv":1,"day":"02","isi":1,"oa_version":"Published Version","_id":"18530","researchdata_availability":"no","status":"public","doi":"10.46298/lmcs-20(4:1)2024","type":"journal_article","publication_identifier":{"eissn":["1860-5974"]},"title":"History-deterministic timed automata","oa":1,"author":[{"full_name":"Bose, Sougata","last_name":"Bose","first_name":"Sougata"},{"last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","first_name":"Thomas A"},{"full_name":"Lehtinen, Karoliina","last_name":"Lehtinen","first_name":"Karoliina"},{"first_name":"Sven","full_name":"Schewe, Sven","last_name":"Schewe"},{"first_name":"Patrick","full_name":"Totzke, Patrick","last_name":"Totzke"}],"publication":"Logical Methods in Computer Science","scopus_import":"1","corr_author":"1","related_material":{"record":[{"status":"public","id":"12508","relation":"earlier_version"}]},"quality_controlled":"1","project":[{"call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093"}],"date_created":"2024-11-10T23:02:01Z","supplementarymaterial":"no","article_processing_charge":"No","month":"10","language":[{"iso":"eng"}],"department":[{"_id":"ToHe"}],"volume":20,"publication_status":"published","page":"1-28"},{"page":"160-167","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"ToHe"}],"month":"01","article_processing_charge":"No","supplementarymaterial":"no","date_created":"2025-01-29T11:55:50Z","project":[{"call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093"}],"quality_controlled":"1","conference":{"location":"Alexandria, VA, United States","name":"SOSA: Symposium on Simplicity in Algorithms","end_date":"2024-01-10","start_date":"2024-01-08"},"scopus_import":"1","publication":"2024 Symposium on Simplicity in Algorithms","author":[{"last_name":"Casares","full_name":"Casares, Antonio","first_name":"Antonio"},{"first_name":"Marcin","full_name":"Pilipczuk, Marcin","last_name":"Pilipczuk"},{"first_name":"Michał","full_name":"Pilipczuk, Michał","last_name":"Pilipczuk"},{"first_name":"Uéverton S.","full_name":"Souza, Uéverton S.","last_name":"Souza"},{"first_name":"K. S.","full_name":"Thejaswini, K. S.","id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","last_name":"Thejaswini"}],"title":"Simple and tight complexity lower bounds for solving Rabin games","oa":1,"publication_identifier":{"isbn":["9781611977936"]},"type":"conference","doi":"10.1137/1.9781611977936.16","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2310.20433"}],"_id":"18955","researchdata_availability":"no","status":"public","oa_version":"Preprint","das_tickbox":"0","arxiv":1,"day":"01","publisher":"Society for Industrial and Applied Mathematics","acknowledgement":"This work is a part of projects CUTACOMBS (Ma. Pilipczuk), BOBR (Mi. Pilipczuk), and VAMOS (K. S. Thejaswini) that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, grant agreements No 714704, 948057, and 101020093, respectively. Ma. Pilipczuk is also partially supported by Polish National Science Centre SONATA BIS-12 grant number 2022/46/E/ST6/00143.","citation":{"apa":"Casares, A., Pilipczuk, M., Pilipczuk, M., Souza, U. S., &#38; Thejaswini, K. S. (2024). Simple and tight complexity lower bounds for solving Rabin games. In <i>2024 Symposium on Simplicity in Algorithms</i> (pp. 160–167). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977936.16\">https://doi.org/10.1137/1.9781611977936.16</a>","ieee":"A. Casares, M. Pilipczuk, M. Pilipczuk, U. S. Souza, and K. S. Thejaswini, “Simple and tight complexity lower bounds for solving Rabin games,” in <i>2024 Symposium on Simplicity in Algorithms</i>, Alexandria, VA, United States, 2024, pp. 160–167.","ama":"Casares A, Pilipczuk M, Pilipczuk M, Souza US, Thejaswini KS. Simple and tight complexity lower bounds for solving Rabin games. In: <i>2024 Symposium on Simplicity in Algorithms</i>. Society for Industrial and Applied Mathematics; 2024:160-167. doi:<a href=\"https://doi.org/10.1137/1.9781611977936.16\">10.1137/1.9781611977936.16</a>","ista":"Casares A, Pilipczuk M, Pilipczuk M, Souza US, Thejaswini KS. 2024. Simple and tight complexity lower bounds for solving Rabin games. 2024 Symposium on Simplicity in Algorithms. SOSA: Symposium on Simplicity in Algorithms, 160–167.","mla":"Casares, Antonio, et al. “Simple and Tight Complexity Lower Bounds for Solving Rabin Games.” <i>2024 Symposium on Simplicity in Algorithms</i>, Society for Industrial and Applied Mathematics, 2024, pp. 160–67, doi:<a href=\"https://doi.org/10.1137/1.9781611977936.16\">10.1137/1.9781611977936.16</a>.","short":"A. Casares, M. Pilipczuk, M. Pilipczuk, U.S. Souza, K.S. Thejaswini, in:, 2024 Symposium on Simplicity in Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 160–167.","chicago":"Casares, Antonio, Marcin Pilipczuk, Michał Pilipczuk, Uéverton S. Souza, and K. S. Thejaswini. “Simple and Tight Complexity Lower Bounds for Solving Rabin Games.” In <i>2024 Symposium on Simplicity in Algorithms</i>, 160–67. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977936.16\">https://doi.org/10.1137/1.9781611977936.16</a>."},"year":"2024","external_id":{"arxiv":["2310.20433"]},"date_updated":"2026-10-21T13:13:33Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"abstract":[{"lang":"eng","text":"We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time 2o(k log k) · nO(1), where k is the number of pairs of vertex subsets involved in the winning condition and n is the vertex count of the game graph. While this result follows from the lower bounds provided by Calude et al [SIAM J. Comp. 2022], our reduction is considerably simpler and arguably provides more insight into the complexity of the problem. In fact, the analogous lower bounds discussed by Calude et al, for solving Muller games and multidimensional parity games, follow as simple corollaries of our approach. Our reduction also highlights the usefulness of a certain pivot problem — Permutation SAT — which may be of independent interest."}],"OA_type":"green","date_published":"2024-01-01T00:00:00Z","fulldoi":"https://doi.org/10.1137/1.9781611977936.16","OA_place":"repository"},{"quality_controlled":"1","project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020","grant_number":"101020093"},{"_id":"34a1b658-11ca-11ed-8bc3-c75229f0241e","name":"Interface Theory for Security and Privacy","grant_number":"F8502"}],"article_processing_charge":"No","date_created":"2024-12-01T23:01:52Z","supplementarymaterial":"no","month":"11","publication_status":"published","department":[{"_id":"ToHe"}],"language":[{"iso":"eng"}],"volume":15234,"page":"151-171","type":"conference","doi":"10.1007/978-3-031-76554-4_9","title":"Monitoring extended hypernode logic","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031765537"],"eissn":["1611-3349"]},"author":[{"full_name":"Chalupa, Marek","id":"87e34708-d6c6-11ec-9f5b-9391e7be2463","last_name":"Chalupa","first_name":"Marek"},{"orcid":"0000-0002-2985-7724","first_name":"Thomas A","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger"},{"id":"f347ec37-6676-11ee-b395-a888cb7b4fb4","last_name":"Oliveira da Costa","full_name":"Oliveira da Costa, Ana","orcid":"0000-0002-8741-5799","first_name":"Ana"}],"publication":"Integrated Formal Methods","scopus_import":"1","corr_author":"1","intvolume":"     15234","external_id":{"isi":["001416640500009"]},"publisher":"Springer Nature","year":"2024","citation":{"mla":"Chalupa, Marek, et al. “Monitoring Extended Hypernode Logic.” <i>Integrated Formal Methods</i>, vol. 15234, Springer Nature, 2024, pp. 151–71, doi:<a href=\"https://doi.org/10.1007/978-3-031-76554-4_9\">10.1007/978-3-031-76554-4_9</a>.","short":"M. Chalupa, T.A. Henzinger, A. Oliveira da Costa, in:, Integrated Formal Methods, Springer Nature, 2024, pp. 151–171.","chicago":"Chalupa, Marek, Thomas A Henzinger, and Ana Oliveira da Costa. “Monitoring Extended Hypernode Logic.” In <i>Integrated Formal Methods</i>, 15234:151–71. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-76554-4_9\">https://doi.org/10.1007/978-3-031-76554-4_9</a>.","ieee":"M. Chalupa, T. A. Henzinger, and A. Oliveira da Costa, “Monitoring extended hypernode logic,” in <i>Integrated Formal Methods</i>, 2024, vol. 15234, pp. 151–171.","apa":"Chalupa, M., Henzinger, T. A., &#38; Oliveira da Costa, A. (2024). Monitoring extended hypernode logic. In <i>Integrated Formal Methods</i> (Vol. 15234, pp. 151–171). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-76554-4_9\">https://doi.org/10.1007/978-3-031-76554-4_9</a>","ista":"Chalupa M, Henzinger TA, Oliveira da Costa A. 2024. Monitoring extended hypernode logic. Integrated Formal Methods. , LNCS, vol. 15234, 151–171.","ama":"Chalupa M, Henzinger TA, Oliveira da Costa A. Monitoring extended hypernode logic. In: <i>Integrated Formal Methods</i>. Vol 15234. Springer Nature; 2024:151-171. doi:<a href=\"https://doi.org/10.1007/978-3-031-76554-4_9\">10.1007/978-3-031-76554-4_9</a>"},"acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093, and by the Austrian Science Fund (FWF) SFB project SpyCoDe F8502.","isi":1,"das_tickbox":"0","day":"13","oa_version":"None","researchdata_availability":"no","_id":"18599","status":"public","fulldoi":"https://doi.org/10.1007/978-3-031-76554-4_9","date_published":"2024-11-13T00:00:00Z","OA_type":"closed access","abstract":[{"text":"Hypernode logic can reason about the prefix relation on stutter-reduced finite traces through the stutter-reduced prefix predicate. We increase the expressiveness of hypernode logic in two ways. First, we split the stutter-reduced prefix predicate into an explicit stutter-reduction operator and the classical prefix predicate on words. This change gives hypernode logic the ability to combine synchronous and asynchronous reasoning by explicitly stating which parts of traces can stutter. Second, we allow the use of regular expressions in formulas to reason about the structure of traces. This change enables hypernode logic to describe a mixture of trace properties and hyperproperties.\r\n\r\nWe show how to translate extended hypernode logic formulas into multi-track automata, which are automata that read multiple input words. Then we describe a fully online monitoring algorithm for monitoring k-safety hyperproperties specified in the logic. We have implemented the monitoring algorithm, and evaluated it on monitoring synchronous and asynchronous versions of observational determinism, and on checking the privacy preservation by compiler optimizations.","lang":"eng"}],"ec_funded":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","alternative_title":["LNCS"],"date_updated":"2026-10-21T13:13:13Z"},{"page":"19-26","volume":14971,"department":[{"_id":"ToHe"}],"language":[{"iso":"eng"}],"publication_status":"published","month":"09","date_created":"2024-10-06T22:01:12Z","supplementarymaterial":"no","article_processing_charge":"No","project":[{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413"}],"quality_controlled":"1","scopus_import":"1","publication":"Computational Methods in Systems Biology","author":[{"last_name":"Beneš","full_name":"Beneš, Nikola","first_name":"Nikola"},{"first_name":"Luboš","full_name":"Brim, Luboš","last_name":"Brim"},{"first_name":"Ondřej","last_name":"Huvar","full_name":"Huvar, Ondřej"},{"full_name":"Pastva, Samuel","last_name":"Pastva","id":"07c5ea74-f61c-11ec-a664-aa7c5d957b2b","first_name":"Samuel","orcid":"0000-0003-1993-0331"},{"full_name":"Šafránek, David","last_name":"Šafránek","first_name":"David"}],"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783031716706"]},"title":"BNClassifier: Classifying boolean models by dynamic properties","doi":"10.1007/978-3-031-71671-3_2","type":"conference","_id":"18177","researchdata_availability":"no","status":"public","oa_version":"None","day":"19","das_tickbox":"0","isi":1,"year":"2024","citation":{"ama":"Beneš N, Brim L, Huvar O, Pastva S, Šafránek D. BNClassifier: Classifying boolean models by dynamic properties. In: <i>Computational Methods in Systems Biology</i>. Vol 14971. Springer Nature; 2024:19-26. doi:<a href=\"https://doi.org/10.1007/978-3-031-71671-3_2\">10.1007/978-3-031-71671-3_2</a>","ista":"Beneš N, Brim L, Huvar O, Pastva S, Šafránek D. 2024. BNClassifier: Classifying boolean models by dynamic properties. Computational Methods in Systems Biology. , LNBI, vol. 14971, 19–26.","ieee":"N. Beneš, L. Brim, O. Huvar, S. Pastva, and D. Šafránek, “BNClassifier: Classifying boolean models by dynamic properties,” in <i>Computational Methods in Systems Biology</i>, 2024, vol. 14971, pp. 19–26.","apa":"Beneš, N., Brim, L., Huvar, O., Pastva, S., &#38; Šafránek, D. (2024). BNClassifier: Classifying boolean models by dynamic properties. In <i>Computational Methods in Systems Biology</i> (Vol. 14971, pp. 19–26). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-71671-3_2\">https://doi.org/10.1007/978-3-031-71671-3_2</a>","chicago":"Beneš, Nikola, Luboš Brim, Ondřej Huvar, Samuel Pastva, and David Šafránek. “BNClassifier: Classifying Boolean Models by Dynamic Properties.” In <i>Computational Methods in Systems Biology</i>, 14971:19–26. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-71671-3_2\">https://doi.org/10.1007/978-3-031-71671-3_2</a>.","mla":"Beneš, Nikola, et al. “BNClassifier: Classifying Boolean Models by Dynamic Properties.” <i>Computational Methods in Systems Biology</i>, vol. 14971, Springer Nature, 2024, pp. 19–26, doi:<a href=\"https://doi.org/10.1007/978-3-031-71671-3_2\">10.1007/978-3-031-71671-3_2</a>.","short":"N. Beneš, L. Brim, O. Huvar, S. Pastva, D. Šafránek, in:, Computational Methods in Systems Biology, Springer Nature, 2024, pp. 19–26."},"acknowledgement":"The work has been supported by the Czech Science Foundation grant No. GA22-10845S. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Grant Agreement No. 101034413.","publisher":"Springer Nature","external_id":{"isi":["001333144400002"]},"intvolume":"     14971","alternative_title":["LNBI"],"date_updated":"2026-10-21T13:12:17Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"abstract":[{"text":"Partially Specified Boolean Networks (PSBNs) represent a family of Boolean models resulting from possible interpretations of unknown update logics. Hybrid extension of CTL (HCTL) has the power to express complex dynamical phenomena, such as oscillations or stability. We present BNClassifier to classify Boolean Networks corresponding to a given PSBN according to criteria specified in HCTL. The implementation of the tool is fully symbolic (based on BDDs). The results are visualised using the machine-learning-based technology of decision trees.","lang":"eng"}],"date_published":"2024-09-19T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-031-71671-3_2"},{"date_published":"2024-10-23T00:00:00Z","OA_type":"closed access","fulldoi":"https://doi.org/10.1007/978-3-031-73751-0_12","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"lang":"eng","text":"I give a personal account about the wave of new research activities that rose in the 1990s on the specification, verification, and control of real-time systems."}],"alternative_title":["LNCS"],"date_updated":"2026-10-21T13:12:56Z","intvolume":"     15230","day":"23","das_tickbox":"0","year":"2024","citation":{"ama":"Henzinger TA. Reminiscences of a Real-Time Researcher. In: Graf S, Pettersson P, Steffen B, eds. <i>Real Time and Such</i>. Vol 15230. LNCS. Cham: Springer Nature; 2024:154-164. doi:<a href=\"https://doi.org/10.1007/978-3-031-73751-0_12\">10.1007/978-3-031-73751-0_12</a>","ista":"Henzinger TA. 2024.Reminiscences of a Real-Time Researcher. In: Real Time and Such. LNCS, vol. 15230, 154–164.","apa":"Henzinger, T. A. (2024). Reminiscences of a Real-Time Researcher. In S. Graf, P. Pettersson, &#38; B. Steffen (Eds.), <i>Real Time and Such</i> (Vol. 15230, pp. 154–164). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-73751-0_12\">https://doi.org/10.1007/978-3-031-73751-0_12</a>","ieee":"T. A. Henzinger, “Reminiscences of a Real-Time Researcher,” in <i>Real Time and Such</i>, vol. 15230, S. Graf, P. Pettersson, and B. Steffen, Eds. Cham: Springer Nature, 2024, pp. 154–164.","chicago":"Henzinger, Thomas A. “Reminiscences of a Real-Time Researcher.” In <i>Real Time and Such</i>, edited by Susanne Graf, Paul Pettersson, and Bernhard Steffen, 15230:154–64. LNCS. Cham: Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-73751-0_12\">https://doi.org/10.1007/978-3-031-73751-0_12</a>.","short":"T.A. Henzinger, in:, S. Graf, P. Pettersson, B. Steffen (Eds.), Real Time and Such, Springer Nature, Cham, 2024, pp. 154–164.","mla":"Henzinger, Thomas A. “Reminiscences of a Real-Time Researcher.” <i>Real Time and Such</i>, edited by Susanne Graf et al., vol. 15230, Springer Nature, 2024, pp. 154–64, doi:<a href=\"https://doi.org/10.1007/978-3-031-73751-0_12\">10.1007/978-3-031-73751-0_12</a>."},"acknowledgement":"I thank all my collaborators over the years. None of the mentioned contributions would have been possible without them. I also apologize for all omissions. The selection of contributions in this essay reflects primarily my personal involvement rather than any measure of importance.","publisher":"Springer Nature","_id":"18563","researchdata_availability":"no","status":"public","editor":[{"first_name":"Susanne","full_name":"Graf, Susanne","last_name":"Graf"},{"full_name":"Pettersson, Paul","last_name":"Pettersson","first_name":"Paul"},{"full_name":"Steffen, Bernhard","last_name":"Steffen","first_name":"Bernhard"}],"oa_version":"None","publication_identifier":{"issn":["0302-9743"],"eisbn":["9783031737510"],"eissn":["1611-3349"],"isbn":["9783031737503"]},"title":"Reminiscences of a Real-Time Researcher","doi":"10.1007/978-3-031-73751-0_12","type":"book_chapter","publication":"Real Time and Such","author":[{"orcid":"0000-0002-2985-7724","first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"corr_author":"1","scopus_import":"1","place":"Cham","quality_controlled":"1","supplementarymaterial":"no","date_created":"2024-11-18T09:10:06Z","article_processing_charge":"No","month":"10","page":"154-164","series_title":"LNCS","language":[{"iso":"eng"}],"department":[{"_id":"ToHe"}],"volume":15230,"publication_status":"published"},{"publication":"41st International Symposium on Theoretical Aspects of Computer Science","author":[{"first_name":"Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","full_name":"Filakovský, Marek"},{"first_name":"Tamio Vesa","full_name":"Nakajima, Tamio Vesa","last_name":"Nakajima"},{"full_name":"Opršal, Jakub","id":"ec596741-c539-11ec-b829-c79322a91242","last_name":"Opršal","orcid":"0000-0003-1245-3456","first_name":"Jakub"},{"full_name":"Tasinato, Gianluca","last_name":"Tasinato","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","first_name":"Gianluca"},{"orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"conference":{"start_date":"2024-03-12","end_date":"2024-03-14","name":"STACS: Symposium on Theoretical Aspects of Computer Science","location":"Clermont-Ferrand, France"},"corr_author":"1","scopus_import":"1","article_number":"34","title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","oa":1,"publication_identifier":{"isbn":["9783959773119"],"eissn":["1868-8969"]},"type":"conference","doi":"10.4230/LIPIcs.STACS.2024.34","month":"03","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"UlWa"}],"volume":289,"project":[{"grant_number":"P31312","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory"},{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"22247"},{"id":"20339","relation":"dissertation_contains","status":"public"}]},"quality_controlled":"1","article_processing_charge":"No","supplementarymaterial":"yes","date_created":"2024-03-24T23:00:59Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","file_date_updated":"2024-03-25T07:44:30Z","ec_funded":1,"abstract":[{"text":"A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the \"linearly ordered chromatic number\" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).","lang":"eng"}],"alternative_title":["LIPIcs"],"date_updated":"2026-10-21T13:23:55Z","has_accepted_license":"1","date_published":"2024-03-01T00:00:00Z","ddc":["510"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.STACS.2024.34","isi":1,"das_tickbox":"0","day":"01","arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","acknowledgement":"Marek Filakovský: This research was supported by Charles University (project PRIMUS/\r\n21/SCI/014), the Austrian Science Fund (FWF project P31312-N35), and MSCAfellow5_MUNI\r\n(CZ.02.01.01/00/22_010/0003229). Tamio-Vesa Nakajima: This research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All data is provided in full in the results section of this paper. Jakub Opršal: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Uli Wagner: This research was supported by the Austrian Science Fund (FWF project P31312-N35).","year":"2024","citation":{"chicago":"Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” In <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>.","short":"M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>.","ista":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 289, 34.","ama":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: <i>41st International Symposium on Theoretical Aspects of Computer Science</i>. Vol 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>","ieee":"M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Clermont-Ferrand, France, 2024, vol. 289.","apa":"Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., &#38; Wagner, U. (2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In <i>41st International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>"},"researchdata_availability":"yes","_id":"15168","status":"public","oa_version":"Published Version","external_id":{"isi":["001300393400034"],"arxiv":["2312.12981"]},"intvolume":"       289","file":[{"access_level":"open_access","checksum":"0524d4189fd1ed08989546511343edf3","relation":"main_file","date_updated":"2024-03-25T07:44:30Z","content_type":"application/pdf","creator":"dernst","success":1,"file_id":"15175","file_name":"2024_LIPICs_Filakovsky.pdf","date_created":"2024-03-25T07:44:30Z","file_size":927290}]},{"dataavailabilitystatement":"Data sharing not applicable to this article as no datasets were generated or analysed during the current study.","file":[{"date_updated":"2024-07-16T10:14:13Z","content_type":"application/pdf","creator":"dernst","access_level":"open_access","checksum":"9418534ac2f3d6f1f091a8b8ccaed01e","relation":"main_file","file_name":"2024_GeometriaeDedicata_Dymond.pdf","file_size":540981,"date_created":"2024-07-16T10:14:13Z","success":1,"file_id":"17257"}],"intvolume":"       218","external_id":{"isi":["001105681500001"],"arxiv":["2102.13046"],"pmid":["38021107"]},"oa_version":"Published Version","researchdata_availability":"not applicable","_id":"9651","status":"public","citation":{"chicago":"Dymond, Michael, and Vojtech Kaluza. “Divergence of Separated Nets with Respect to Displacement Equivalence.” <i>Geometriae Dedicata</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s10711-023-00862-3\">https://doi.org/10.1007/s10711-023-00862-3</a>.","mla":"Dymond, Michael, and Vojtech Kaluza. “Divergence of Separated Nets with Respect to Displacement Equivalence.” <i>Geometriae Dedicata</i>, vol. 218, 15, Springer Nature, 2024, doi:<a href=\"https://doi.org/10.1007/s10711-023-00862-3\">10.1007/s10711-023-00862-3</a>.","short":"M. Dymond, V. Kaluza, Geometriae Dedicata 218 (2024).","ista":"Dymond M, Kaluza V. 2024. Divergence of separated nets with respect to displacement equivalence. Geometriae Dedicata. 218, 15.","ama":"Dymond M, Kaluza V. Divergence of separated nets with respect to displacement equivalence. <i>Geometriae Dedicata</i>. 2024;218. doi:<a href=\"https://doi.org/10.1007/s10711-023-00862-3\">10.1007/s10711-023-00862-3</a>","apa":"Dymond, M., &#38; Kaluza, V. (2024). Divergence of separated nets with respect to displacement equivalence. <i>Geometriae Dedicata</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10711-023-00862-3\">https://doi.org/10.1007/s10711-023-00862-3</a>","ieee":"M. Dymond and V. Kaluza, “Divergence of separated nets with respect to displacement equivalence,” <i>Geometriae Dedicata</i>, vol. 218. Springer Nature, 2024."},"year":"2024","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). This work was started while both authors were employed at the University of Innsbruck and enjoyed the full support of Austrian Science Fund (FWF): P 30902-N35. It was continued when the first named author was employed at University of Leipzig and the second named author was employed at Institute of Science and Technology of Austria, where he was supported by an IST Fellowship.","publisher":"Springer Nature","day":"01","arxiv":1,"das_tickbox":"1","isi":1,"article_type":"original","fulldoi":"https://doi.org/10.1007/s10711-023-00862-3","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["510"],"OA_type":"hybrid","date_published":"2024-02-01T00:00:00Z","has_accepted_license":"1","OA_place":"publisher","date_updated":"2026-10-21T13:22:57Z","abstract":[{"lang":"eng","text":"We introduce a hierachy of equivalence relations on the set of separated nets of a given Euclidean space, indexed by concave increasing functions ϕ:(0,∞)→(0,∞). Two separated nets are called ϕ-displacement equivalent if, roughly speaking, there is a bijection between them which, for large radii R, displaces points of norm at most R by something of order at most ϕ(R). We show that the spectrum of ϕ-displacement equivalence spans from the established notion of bounded displacement equivalence, which corresponds to bounded ϕ, to the indiscrete equivalence relation, coresponding to ϕ(R)∈Ω(R), in which all separated nets are equivalent. In between the two ends of this spectrum, the notions of ϕ-displacement equivalence are shown to be pairwise distinct with respect to the asymptotic classes of ϕ(R) for R→∞. We further undertake a comparison of our notion of ϕ-displacement equivalence with previously studied relations on separated nets. Particular attention is given to the interaction of the notions of ϕ-displacement equivalence with that of bilipschitz equivalence."}],"file_date_updated":"2024-07-16T10:14:13Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","supplementarymaterial":"no","date_created":"2021-07-14T07:01:27Z","article_processing_charge":"Yes (via OA deal)","quality_controlled":"1","language":[{"iso":"eng"}],"volume":218,"department":[{"_id":"UlWa"}],"publication_status":"published","month":"02","doi":"10.1007/s10711-023-00862-3","type":"journal_article","publication_identifier":{"issn":["0046-5755"],"eissn":["1572-9168"]},"pmid":1,"oa":1,"title":"Divergence of separated nets with respect to displacement equivalence","article_number":"15","scopus_import":"1","corr_author":"1","author":[{"full_name":"Dymond, Michael","last_name":"Dymond","first_name":"Michael"},{"id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","last_name":"Kaluza","full_name":"Kaluza, Vojtech","orcid":"0000-0002-2512-8698","first_name":"Vojtech"}],"publication":"Geometriae Dedicata"},{"file_date_updated":"2024-07-16T10:35:10Z","abstract":[{"lang":"eng","text":"The classical Steinitz theorem states that if the origin belongs to the interior of the convex hull of a set 𝑆⊂ℝ𝑑, then there are at most 2𝑑 points of 𝑆 whose convex hull contains the origin in the interior. Bárány, Katchalski,and Pach proved the following quantitative version of Steinitz’s theorem. Let 𝑄 be a convex polytope in ℝ𝑑 containing the standard Euclidean unit ball 𝐁𝑑. Then there exist at most 2𝑑 vertices of 𝑄 whose convex hull 𝑄′ satisfies 𝑟𝐁𝑑⊂𝑄′ with 𝑟⩾𝑑−2𝑑. They conjectured that 𝑟⩾𝑐𝑑−1∕2 holds with a universal constant 𝑐>0. We prove 𝑟⩾15𝑑2, the first polynomial lower bound on 𝑟. Furthermore, we show that 𝑟 is not greater than 2/√𝑑."}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2026-10-21T13:23:20Z","article_type":"original","fulldoi":"https://doi.org/10.1112/blms.12965","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["510"],"has_accepted_license":"1","date_published":"2024-02-01T00:00:00Z","year":"2024","citation":{"ama":"Ivanov G, Naszódi M. Quantitative Steinitz theorem: A polynomial bound. <i>Bulletin of the London Mathematical Society</i>. 2024;56(2):796-802. doi:<a href=\"https://doi.org/10.1112/blms.12965\">10.1112/blms.12965</a>","ista":"Ivanov G, Naszódi M. 2024. Quantitative Steinitz theorem: A polynomial bound. Bulletin of the London Mathematical Society. 56(2), 796–802.","apa":"Ivanov, G., &#38; Naszódi, M. (2024). Quantitative Steinitz theorem: A polynomial bound. <i>Bulletin of the London Mathematical Society</i>. London Mathematical Society. <a href=\"https://doi.org/10.1112/blms.12965\">https://doi.org/10.1112/blms.12965</a>","ieee":"G. Ivanov and M. Naszódi, “Quantitative Steinitz theorem: A polynomial bound,” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 2. London Mathematical Society, pp. 796–802, 2024.","chicago":"Ivanov, Grigory, and Márton Naszódi. “Quantitative Steinitz Theorem: A Polynomial Bound.” <i>Bulletin of the London Mathematical Society</i>. London Mathematical Society, 2024. <a href=\"https://doi.org/10.1112/blms.12965\">https://doi.org/10.1112/blms.12965</a>.","short":"G. Ivanov, M. Naszódi, Bulletin of the London Mathematical Society 56 (2024) 796–802.","mla":"Ivanov, Grigory, and Márton Naszódi. “Quantitative Steinitz Theorem: A Polynomial Bound.” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 2, London Mathematical Society, 2024, pp. 796–802, doi:<a href=\"https://doi.org/10.1112/blms.12965\">10.1112/blms.12965</a>."},"acknowledgement":"M.N. was supported by the János Bolyai Scholarship of the Hungarian Academy of Sciences aswell as the National Research, Development and Innovation Fund (NRDI) grants K119670 andK131529, and the ÚNKP-22-5 New National Excellence Program of the Ministry for Innovationand Technology from the source of the NRDI as well as the ELTE TKP 2021-NKTA-62 fundingscheme","publisher":"London Mathematical Society","das_tickbox":"0","day":"01","arxiv":1,"isi":1,"oa_version":"Published Version","status":"public","_id":"14660","researchdata_availability":"no","file":[{"date_created":"2024-07-16T10:35:10Z","file_size":111756,"file_name":"2024_BulletinLondonMathSoc_Ivanov.pdf","file_id":"17259","success":1,"creator":"dernst","date_updated":"2024-07-16T10:35:10Z","content_type":"application/pdf","relation":"main_file","checksum":"30ea0694757bc668cf7cd15ae357b35e","access_level":"open_access"}],"intvolume":"        56","external_id":{"arxiv":["2212.04308"],"isi":["001113277100001"]},"issue":"2","author":[{"last_name":"Ivanov","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory","first_name":"Grigory","orcid":"0000-0002-5021-3982"},{"full_name":"Naszódi, Márton","last_name":"Naszódi","first_name":"Márton"}],"publication":"Bulletin of the London Mathematical Society","scopus_import":"1","corr_author":"1","doi":"10.1112/blms.12965","type":"journal_article","publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"title":"Quantitative Steinitz theorem: A polynomial bound","oa":1,"month":"02","volume":56,"language":[{"iso":"eng"}],"department":[{"_id":"UlWa"}],"publication_status":"published","page":"796-802","quality_controlled":"1","supplementarymaterial":"no","date_created":"2023-12-10T23:00:58Z","article_processing_charge":"Yes (via OA deal)"},{"status":"public","_id":"18617","researchdata_availability":"not applicable","oa_version":"Published Version","isi":1,"das_tickbox":"1","arxiv":1,"day":"01","publisher":"Elsevier","citation":{"mla":"Beďatš, Daniel. “Separation of Variables for Scalar-Valued Polynomials in the Non-Stable Range.” <i>Journal of Algebra</i>, vol. 651, Elsevier, 2024, pp. 281–304, doi:<a href=\"https://doi.org/10.1016/j.jalgebra.2024.04.013\">10.1016/j.jalgebra.2024.04.013</a>.","short":"D. Beďatš, Journal of Algebra 651 (2024) 281–304.","chicago":"Beďatš, Daniel. “Separation of Variables for Scalar-Valued Polynomials in the Non-Stable Range.” <i>Journal of Algebra</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.jalgebra.2024.04.013\">https://doi.org/10.1016/j.jalgebra.2024.04.013</a>.","ieee":"D. Beďatš, “Separation of variables for scalar-valued polynomials in the non-stable range,” <i>Journal of Algebra</i>, vol. 651. Elsevier, pp. 281–304, 2024.","apa":"Beďatš, D. (2024). Separation of variables for scalar-valued polynomials in the non-stable range. <i>Journal of Algebra</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jalgebra.2024.04.013\">https://doi.org/10.1016/j.jalgebra.2024.04.013</a>","ista":"Beďatš D. 2024. Separation of variables for scalar-valued polynomials in the non-stable range. Journal of Algebra. 651, 281–304.","ama":"Beďatš D. Separation of variables for scalar-valued polynomials in the non-stable range. <i>Journal of Algebra</i>. 2024;651:281-304. doi:<a href=\"https://doi.org/10.1016/j.jalgebra.2024.04.013\">10.1016/j.jalgebra.2024.04.013</a>"},"acknowledgement":"The author is sincerely grateful for guidance, advice and valuable feedback from Roman Lávička.","year":"2024","dataavailabilitystatement":"No data was used for the research described in the article.\r\n","external_id":{"isi":["001232775600001"],"arxiv":["2309.11154"]},"intvolume":"       651","file":[{"creator":"dernst","content_type":"application/pdf","date_updated":"2024-12-09T13:56:26Z","relation":"main_file","checksum":"7b01c89128ba16d5334dfab389a03878","access_level":"open_access","file_size":486969,"date_created":"2024-12-09T13:56:26Z","file_name":"2024_JourAlgebra_Bedats.pdf","file_id":"18638","success":1}],"date_updated":"2026-10-21T13:24:58Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","file_date_updated":"2024-12-09T13:56:26Z","abstract":[{"lang":"eng","text":"Any complex-valued polynomial on (Rn)k decomposes into an algebraic combination of O(n)-invariant polynomials and harmonic polynomials. This decomposition, separation of variables, is granted to be unique if n≥2k−1. We prove that the condition n≥2k−1 is not only sufficient, but also necessary for uniqueness of the separation. Moreover, we describe the structure of non-uniqueness of the separation in the boundary cases when n=2k−2 and n=2k−3.\r\nFormally, we study the kernel of a multiplication map ϕ carrying out separation of variables. We devise a general algorithmic procedure for describing Ker ϕ in the restricted non-stable range k≤n<2k−1. In the full non-stable range n<2k−1, we give formulas for highest weights of generators of the kernel as well as formulas for its Hilbert series. Using the developed methods, we obtain a list of highest weight vectors generating Ker ϕ."}],"OA_type":"hybrid","date_published":"2024-08-01T00:00:00Z","has_accepted_license":"1","ddc":["510"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.1016/j.jalgebra.2024.04.013","article_type":"original","OA_place":"publisher","page":"281-304","publication_status":"published","volume":651,"department":[{"_id":"UlWa"}],"language":[{"iso":"eng"}],"month":"08","article_processing_charge":"Yes (via OA deal)","date_created":"2024-12-04T07:58:45Z","supplementarymaterial":"no","quality_controlled":"1","corr_author":"1","scopus_import":"1","publication":"Journal of Algebra","author":[{"orcid":"0009-0004-1828-0044","first_name":"Daniel","id":"78ea3cc9-31e7-11ee-aa02-a6169bbfe1f1","last_name":"Beďatš","full_name":"Beďatš, Daniel"}],"title":"Separation of variables for scalar-valued polynomials in the non-stable range","oa":1,"publication_identifier":{"issn":["0021-8693"]},"type":"journal_article","doi":"10.1016/j.jalgebra.2024.04.013"},{"date_created":"2023-08-06T22:01:12Z","supplementarymaterial":"no","article_processing_charge":"No","related_material":{"record":[{"relation":"earlier_version","id":"6647","status":"public"}]},"quality_controlled":"1","project":[{"grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF"}],"volume":72,"language":[{"iso":"eng"}],"department":[{"_id":"UlWa"}],"publication_status":"published","page":"831-848","month":"09","doi":"10.1007/s00454-023-00532-x","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1812.04911"}],"type":"journal_article","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"oa":1,"title":"The crossing Tverberg theorem","scopus_import":"1","author":[{"orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"full_name":"Gärtner, Bernd","last_name":"Gärtner","first_name":"Bernd"},{"last_name":"Kupavskii","full_name":"Kupavskii, Andrey","first_name":"Andrey"},{"full_name":"Valtr, Pavel","last_name":"Valtr","first_name":"Pavel"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"publication":"Discrete and Computational Geometry","intvolume":"        72","external_id":{"isi":["001038546500001"],"arxiv":["1812.04911"]},"oa_version":"Preprint","_id":"13974","status":"public","researchdata_availability":"no","acknowledgement":"Part of the research leading to this paper was done during the 16th Gremo Workshop on Open Problems (GWOP), Waltensburg, Switzerland, June 12–16, 2018. We thank Patrick Schnider for suggesting the problem, and Stefan Felsner, Malte Milatz, and Emo Welzl for fruitful discussions during the workshop. We also thank Stefan Felsner and Manfred Scheucher for finding, communicating the example from Sect. 3.3, and the kind permission to include their visualization of the point set. We thank Dömötör Pálvölgyi, the SoCG reviewers, and DCG reviewers for various helpful comments.\r\nR. Fulek gratefully acknowledges support from Austrian Science Fund (FWF), Project  M2281-N35. A. Kupavskii was supported by the Advanced Postdoc.Mobility Grant no. P300P2_177839 of the Swiss National Science Foundation. Research by P. Valtr was supported by the Grant no. 18-19158 S of the Czech Science Foundation (GAČR).","year":"2024","citation":{"short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational Geometry 72 (2024) 831–848.","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” <i>Discrete and Computational Geometry</i>, vol. 72, Springer Nature, 2024, pp. 831–48, doi:<a href=\"https://doi.org/10.1007/s00454-023-00532-x\">10.1007/s00454-023-00532-x</a>.","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s00454-023-00532-x\">https://doi.org/10.1007/s00454-023-00532-x</a>.","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” <i>Discrete and Computational Geometry</i>, vol. 72. Springer Nature, pp. 831–848, 2024.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., &#38; Wagner, U. (2024). The crossing Tverberg theorem. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-023-00532-x\">https://doi.org/10.1007/s00454-023-00532-x</a>","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. <i>Discrete and Computational Geometry</i>. 2024;72:831-848. doi:<a href=\"https://doi.org/10.1007/s00454-023-00532-x\">10.1007/s00454-023-00532-x</a>","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2024. The crossing Tverberg theorem. Discrete and Computational Geometry. 72, 831–848."},"publisher":"Springer Nature","day":"01","das_tickbox":"0","arxiv":1,"isi":1,"fulldoi":"https://doi.org/10.1007/s00454-023-00532-x","article_type":"original","OA_type":"green","date_published":"2024-09-01T00:00:00Z","OA_place":"repository","date_updated":"2026-10-21T13:25:18Z","abstract":[{"lang":"eng","text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common point. In this paper, we prove a trengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result generalizes to a result about simplices in Rd, d≥2."}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"date_published":"2024-03-14T00:00:00Z","fulldoi":"https://doi.org/10.1063/5.0195908","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"lang":"eng","text":"In this paper we build a constructive algorithm that returns a rectifiable curve that connects two points in a weakly convex set in a Hilbert space. We have proven that this algorithm converges and obtained an estimate on the curve’s length and compare the length of the curve obtained to known results."}],"date_updated":"2026-10-21T13:24:14Z","issue":"1","intvolume":"      3030","day":"14","publisher":"AIP Publishing","year":"2024","citation":{"ieee":"M. Lopushanski and G. Ivanov, “A constructive algorithm for building rectifiable curves in weakly convex sets,” in <i>AIP Conference Proceedings</i>, Virtual, 2024, vol. 3030, no. 1.","apa":"Lopushanski, M., &#38; Ivanov, G. (2024). A constructive algorithm for building rectifiable curves in weakly convex sets. In <i>AIP Conference Proceedings</i> (Vol. 3030). Virtual: AIP Publishing. <a href=\"https://doi.org/10.1063/5.0195908\">https://doi.org/10.1063/5.0195908</a>","ista":"Lopushanski M, Ivanov G. 2024. A constructive algorithm for building rectifiable curves in weakly convex sets. AIP Conference Proceedings. ICCMSE: International Conference of Computational Methods in Sciences and Engiineering vol. 3030, 080002.","ama":"Lopushanski M, Ivanov G. A constructive algorithm for building rectifiable curves in weakly convex sets. In: <i>AIP Conference Proceedings</i>. Vol 3030. AIP Publishing; 2024. doi:<a href=\"https://doi.org/10.1063/5.0195908\">10.1063/5.0195908</a>","short":"M. Lopushanski, G. Ivanov, in:, AIP Conference Proceedings, AIP Publishing, 2024.","mla":"Lopushanski, Mariana, and Grigory Ivanov. “A Constructive Algorithm for Building Rectifiable Curves in Weakly Convex Sets.” <i>AIP Conference Proceedings</i>, vol. 3030, no. 1, 080002, AIP Publishing, 2024, doi:<a href=\"https://doi.org/10.1063/5.0195908\">10.1063/5.0195908</a>.","chicago":"Lopushanski, Mariana, and Grigory Ivanov. “A Constructive Algorithm for Building Rectifiable Curves in Weakly Convex Sets.” In <i>AIP Conference Proceedings</i>, Vol. 3030. AIP Publishing, 2024. <a href=\"https://doi.org/10.1063/5.0195908\">https://doi.org/10.1063/5.0195908</a>."},"researchdata_availability":"unclear","_id":"15296","status":"public","oa_version":"None","article_number":"080002","title":"A constructive algorithm for building rectifiable curves in weakly convex sets","publication_identifier":{"eissn":["1551-7616"],"issn":["0094-243X"]},"type":"conference","doi":"10.1063/5.0195908","publication":"AIP Conference Proceedings","author":[{"last_name":"Lopushanski","full_name":"Lopushanski, Mariana","first_name":"Mariana"},{"orcid":"0000-0002-5021-3982","first_name":"Grigory","full_name":"Ivanov, Grigory","last_name":"Ivanov","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E"}],"conference":{"location":"Virtual","name":"ICCMSE: International Conference of Computational Methods in Sciences and Engiineering","end_date":"2022-10-29","start_date":"2022-10-26"},"scopus_import":"1","quality_controlled":"1","article_processing_charge":"No","date_created":"2024-04-07T22:00:55Z","supplementarymaterial":"unclear","month":"03","publication_status":"published","department":[{"_id":"UlWa"}],"language":[{"iso":"eng"}],"volume":3030},{"arxiv":1,"das_tickbox":"0","day":"06","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2024","acknowledgement":"Aronov, Boris: Work has been supported by NSF grants CCF 15-40656 and CCF 20-08551, and by grant 2014/170 from the US-Israel Binational Science Foundation. Part of this research was conducted while BA was visiting ISTA in the summers of 2022 and 2023. The visit of BA to ISTA in the summer of 2022 was supported by an ISTA Visiting Professorship.\r\nBasit, Abdul: Work has been supported by Australian Research Council grant DP220102212.\r\nRamesh, Indu: Work supported by a Tandon School of Engineering Fellowship and by NSF Grant CCF-20-08551.\r\nBA and AB would like to thank William Steiger for insightful initial discussions of the problems addressed in this work.","citation":{"apa":"Aronov, B., Basit, A., Ramesh, I., Tasinato, G., &#38; Wagner, U. (2024). Eight-partitioning points in 3D, and efficiently too. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293, p. 8:1-8:15). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">https://doi.org/10.4230/LIPIcs.SoCG.2024.8</a>","ieee":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, and U. Wagner, “Eight-partitioning points in 3D, and efficiently too,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293, p. 8:1-8:15.","ama":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. Eight-partitioning points in 3D, and efficiently too. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:8:1-8:15. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">10.4230/LIPIcs.SoCG.2024.8</a>","ista":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. 2024. Eight-partitioning points in 3D, and efficiently too. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry vol. 293, 8:1-8:15.","mla":"Aronov, Boris, et al. “Eight-Partitioning Points in 3D, and Efficiently Too.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 8:1-8:15, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">10.4230/LIPIcs.SoCG.2024.8</a>.","short":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, U. Wagner, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 8:1-8:15.","chicago":"Aronov, Boris, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner. “Eight-Partitioning Points in 3D, and Efficiently Too.” In <i>40th International Symposium on Computational Geometry</i>, 293:8:1-8:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">https://doi.org/10.4230/LIPIcs.SoCG.2024.8</a>."},"researchdata_availability":"no","_id":"18917","status":"public","oa_version":"Published Version","external_id":{"arxiv":["2403.02627"]},"intvolume":"       293","file":[{"file_size":880725,"date_created":"2025-01-27T14:17:37Z","file_name":"2024_LIPICs_Aronov.pdf","file_id":"18918","success":1,"creator":"dernst","date_updated":"2025-01-27T14:17:37Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"443aa29ea5d948e917cfccd681dcf176"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"text":"An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument.\r\nWe prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction.\r\nMoreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}).","lang":"eng"}],"file_date_updated":"2025-01-27T14:17:37Z","date_updated":"2026-10-21T13:38:17Z","OA_place":"publisher","OA_type":"gold","has_accepted_license":"1","date_published":"2024-06-06T00:00:00Z","ddc":["510"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2024.8","month":"06","page":"8:1-8:15","publication_status":"published","volume":293,"language":[{"iso":"eng"}],"department":[{"_id":"UlWa"},{"_id":"GradSch"}],"quality_controlled":"1","related_material":{"record":[{"id":"19860","relation":"later_version","status":"public"}]},"article_processing_charge":"Yes","supplementarymaterial":"no","date_created":"2025-01-27T14:19:17Z","publication":"40th International Symposium on Computational Geometry","author":[{"last_name":"Aronov","full_name":"Aronov, Boris","first_name":"Boris"},{"first_name":"Abdul","last_name":"Basit","full_name":"Basit, Abdul"},{"first_name":"Indu","full_name":"Ramesh, Indu","last_name":"Ramesh"},{"full_name":"Tasinato, Gianluca","last_name":"Tasinato","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","first_name":"Gianluca"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"conference":{"start_date":"2024-06-11","name":"SoCG: Symposium on Computational Geometry","end_date":"2024-06-14","location":"Athens, Greece"},"corr_author":"1","scopus_import":"1","title":"Eight-partitioning points in 3D, and efficiently too","oa":1,"publication_identifier":{"isbn":["9783959773164"]},"type":"conference","doi":"10.4230/LIPIcs.SoCG.2024.8"},{"corr_author":"1","scopus_import":"1","publication":"Geometric and Functional Analysis","author":[{"last_name":"Kaloshin","id":"FE553552-CDE8-11E9-B324-C0EBE5697425","full_name":"Kaloshin, Vadim","first_name":"Vadim","orcid":"0000-0002-6051-2628"},{"id":"52DF3E68-AEFA-11EA-95A4-124A3DDC885E","last_name":"Koudjinan","full_name":"Koudjinan, Edmond","orcid":"0000-0003-2640-4049","first_name":"Edmond"},{"last_name":"Zhang","full_name":"Zhang, Ke","first_name":"Ke"}],"publication_identifier":{"issn":["1016-443X"],"eissn":["1420-8970"]},"oa":1,"title":"Birkhoff conjecture for nearly centrally symmetric domains","doi":"10.1007/s00039-024-00695-6","type":"journal_article","page":"1973-2007","volume":34,"language":[{"iso":"eng"}],"department":[{"_id":"VaKa"}],"publication_status":"published","month":"12","date_created":"2024-10-27T23:01:45Z","supplementarymaterial":"no","article_processing_charge":"Yes (via OA deal)","project":[{"grant_number":"885707","name":"Spectral rigidity and integrability for billiards and geodesic flows","_id":"9B8B92DE-BA93-11EA-9121-9846C619BF3A","call_identifier":"H2020"}],"quality_controlled":"1","date_updated":"2026-10-21T13:44:48Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"file_date_updated":"2025-01-13T09:14:24Z","abstract":[{"text":"In this paper we prove a perturbative version of a remarkable Bialy–Mironov (Ann. Math. 196(1):389–413, 2022) result. They prove non perturbative Birkhoff conjecture for centrally-symmetric convex domains, namely, a centrally-symmetric convex domain with integrable billiard is ellipse. We combine techniques from Bialy–Mironov (Ann. Math. 196(1):389–413, 2022) with a local result by Kaloshin–Sorrentino (Ann. Math. 188(1):315–380, 2018) and show that a domain close enough to a centrally symmetric one with integrable billiard is ellipse. To combine these results we derive a slight extension of Bialy–Mironov (Ann. Math. 196(1):389–413, 2022) by proving that a notion of rational integrability is equivalent to the C0-integrability condition used in their paper.","lang":"eng"}],"ddc":["510"],"has_accepted_license":"1","date_published":"2024-12-01T00:00:00Z","OA_type":"hybrid","article_type":"original","fulldoi":"https://doi.org/10.1007/s00039-024-00695-6","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"OA_place":"publisher","_id":"18483","status":"public","researchdata_availability":"no","oa_version":"Published Version","das_tickbox":"0","day":"01","arxiv":1,"isi":1,"citation":{"ieee":"V. Kaloshin, E. Koudjinan, and K. Zhang, “Birkhoff conjecture for nearly centrally symmetric domains,” <i>Geometric and Functional Analysis</i>, vol. 34. Springer Nature, pp. 1973–2007, 2024.","apa":"Kaloshin, V., Koudjinan, E., &#38; Zhang, K. (2024). Birkhoff conjecture for nearly centrally symmetric domains. <i>Geometric and Functional Analysis</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00039-024-00695-6\">https://doi.org/10.1007/s00039-024-00695-6</a>","ista":"Kaloshin V, Koudjinan E, Zhang K. 2024. Birkhoff conjecture for nearly centrally symmetric domains. Geometric and Functional Analysis. 34, 1973–2007.","ama":"Kaloshin V, Koudjinan E, Zhang K. Birkhoff conjecture for nearly centrally symmetric domains. <i>Geometric and Functional Analysis</i>. 2024;34:1973-2007. doi:<a href=\"https://doi.org/10.1007/s00039-024-00695-6\">10.1007/s00039-024-00695-6</a>","short":"V. Kaloshin, E. Koudjinan, K. Zhang, Geometric and Functional Analysis 34 (2024) 1973–2007.","mla":"Kaloshin, Vadim, et al. “Birkhoff Conjecture for Nearly Centrally Symmetric Domains.” <i>Geometric and Functional Analysis</i>, vol. 34, Springer Nature, 2024, pp. 1973–2007, doi:<a href=\"https://doi.org/10.1007/s00039-024-00695-6\">10.1007/s00039-024-00695-6</a>.","chicago":"Kaloshin, Vadim, Edmond Koudjinan, and Ke Zhang. “Birkhoff Conjecture for Nearly Centrally Symmetric Domains.” <i>Geometric and Functional Analysis</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s00039-024-00695-6\">https://doi.org/10.1007/s00039-024-00695-6</a>."},"year":"2024","acknowledgement":"We are grateful to the anonymous referee for their careful reading and valuable remarks and comments which helped to improve significantly the paper. Open access funding provided by Institute of Science and Technology (IST Austria). V.K. and C.E.K. gratefully acknowledge support from the European Research Council (ERC) through the Advanced Grant “SPERIG” (#885 707).","publisher":"Springer Nature","external_id":{"arxiv":["2306.12301"],"isi":["001329804200001"]},"file":[{"date_updated":"2025-01-13T09:14:24Z","content_type":"application/pdf","creator":"dernst","relation":"main_file","access_level":"open_access","checksum":"e7fcd9f78beb40408c7d858ac0625e27","file_name":"2024_GeometricFunctionalAnalysis_Kaloshin.pdf","date_created":"2025-01-13T09:14:24Z","file_size":2260980,"file_id":"18833","success":1}],"intvolume":"        34"},{"publication_status":"published","volume":457,"department":[{"_id":"VaKa"}],"language":[{"iso":"eng"}],"month":"11","article_processing_charge":"Yes (via OA deal)","supplementarymaterial":"no","date_created":"2024-09-15T22:01:39Z","quality_controlled":"1","project":[{"grant_number":"885707","call_identifier":"H2020","_id":"9B8B92DE-BA93-11EA-9121-9846C619BF3A","name":"Spectral rigidity and integrability for billiards and geodesic flows"}],"scopus_import":"1","corr_author":"1","author":[{"last_name":"Hou","full_name":"Hou, Xuanji","first_name":"Xuanji"},{"full_name":"Pan, Yi","id":"1e21c7f7-9070-11eb-847d-8b04c7169523","last_name":"Pan","first_name":"Yi"},{"full_name":"Zhou, Qi","last_name":"Zhou","first_name":"Qi"}],"publication":"Advances in Mathematics","type":"journal_article","doi":"10.1016/j.aim.2024.109943","oa":1,"title":"Dynamical classification of analytic one-frequency quasi-periodic SO(3,R)-cocycles","publication_identifier":{"issn":["0001-8708"],"eissn":["1090-2082"]},"article_number":"109943","oa_version":"Published Version","status":"public","_id":"18065","researchdata_availability":"no","publisher":"Elsevier","acknowledgement":"X. Hou is partially supported by National Natural Science Foundation of China (Grant \r\n12071083) and Funds for Distinguished Youths of Hubei Province of China (\r\n2019CFA680). Y. Pan is supported by ERC Advanced Grant (#885707). Q. Zhou is partially supported by National Key R&D Program of China (2020YFA0713300), NSFC grant (\r\n12071232) and Nankai Zhide Foundation.","year":"2024","citation":{"ama":"Hou X, Pan Y, Zhou Q. Dynamical classification of analytic one-frequency quasi-periodic SO(3,R)-cocycles. <i>Advances in Mathematics</i>. 2024;457. doi:<a href=\"https://doi.org/10.1016/j.aim.2024.109943\">10.1016/j.aim.2024.109943</a>","ista":"Hou X, Pan Y, Zhou Q. 2024. Dynamical classification of analytic one-frequency quasi-periodic SO(3,R)-cocycles. Advances in Mathematics. 457, 109943.","ieee":"X. Hou, Y. Pan, and Q. Zhou, “Dynamical classification of analytic one-frequency quasi-periodic SO(3,R)-cocycles,” <i>Advances in Mathematics</i>, vol. 457. Elsevier, 2024.","apa":"Hou, X., Pan, Y., &#38; Zhou, Q. (2024). Dynamical classification of analytic one-frequency quasi-periodic SO(3,R)-cocycles. <i>Advances in Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.aim.2024.109943\">https://doi.org/10.1016/j.aim.2024.109943</a>","chicago":"Hou, Xuanji, Yi Pan, and Qi Zhou. “Dynamical Classification of Analytic One-Frequency Quasi-Periodic SO(3,R)-Cocycles.” <i>Advances in Mathematics</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.aim.2024.109943\">https://doi.org/10.1016/j.aim.2024.109943</a>.","mla":"Hou, Xuanji, et al. “Dynamical Classification of Analytic One-Frequency Quasi-Periodic SO(3,R)-Cocycles.” <i>Advances in Mathematics</i>, vol. 457, 109943, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.aim.2024.109943\">10.1016/j.aim.2024.109943</a>.","short":"X. Hou, Y. Pan, Q. Zhou, Advances in Mathematics 457 (2024)."},"isi":1,"arxiv":1,"das_tickbox":"0","day":"01","intvolume":"       457","file":[{"success":1,"file_id":"18826","file_name":"2024_AdvancesMath_Hou.pdf","file_size":713659,"date_created":"2025-01-13T08:29:27Z","access_level":"open_access","checksum":"1c80b844a91d93cf4799f4a65873b18d","relation":"main_file","date_updated":"2025-01-13T08:29:27Z","content_type":"application/pdf","creator":"dernst"}],"external_id":{"arxiv":["2311.17537"],"isi":["001315306500001"]},"date_updated":"2026-10-21T13:44:19Z","abstract":[{"lang":"eng","text":"We establish a close connection between acceleration and dynamical degree for one-frequency quasi-periodic compact cocycles, by showing that two vectors derived separately from each coincide. Based on this, we provide a dynamical classification of one-frequency quasi-periodic  SO(3, R)-cocycles."}],"file_date_updated":"2025-01-13T08:29:27Z","ec_funded":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_type":"original","fulldoi":"https://doi.org/10.1016/j.aim.2024.109943","has_accepted_license":"1","OA_type":"hybrid","date_published":"2024-11-01T00:00:00Z","ddc":["510"],"OA_place":"publisher"},{"publisher":"Brown University","acknowledgement":"This work was initiated at the 16th European Research Week on Geometric Graphs in Strobl in 2019. A.W. has been supported by the Austrian Science Fund (FWF): W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035] and by the NWO Gravitation project NETWORKS under grant no. 024.002.003. Part of the work was done while A.W. was emplyed at Graz University of Technology. Preliminary versions of this work have been presented at the 38th European Workshop on Computational Geometry (EuroCG\r\n2022) in Perugia [10] and at the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023) in Isola delle Femmine [11].","year":"2024","citation":{"chicago":"De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová, Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve Arrangements.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2024. <a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">https://doi.org/10.7155/jgaa.v28i2.2988</a>.","mla":"De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.” <i>Journal of Graph Algorithms and Applications</i>, vol. 28, no. 2, Brown University, 2024, pp. 47–82, doi:<a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">10.7155/jgaa.v28i2.2988</a>.","short":"P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M. Löffler, G. Rote, Journal of Graph Algorithms and Applications 28 (2024) 47–82.","ista":"De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler M, Rote G. 2024. Removing popular faces in curve arrangements. Journal of Graph Algorithms and Applications. 28(2), 47–82.","ama":"De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve arrangements. <i>Journal of Graph Algorithms and Applications</i>. 2024;28(2):47-82. doi:<a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">10.7155/jgaa.v28i2.2988</a>","ieee":"P. De Nooijer <i>et al.</i>, “Removing popular faces in curve arrangements,” <i>Journal of Graph Algorithms and Applications</i>, vol. 28, no. 2. Brown University, pp. 47–82, 2024.","apa":"De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T., Löffler, M., &#38; Rote, G. (2024). Removing popular faces in curve arrangements. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">https://doi.org/10.7155/jgaa.v28i2.2988</a>"},"day":"03","arxiv":1,"das_tickbox":"0","oa_version":"Published Version","status":"public","_id":"18604","researchdata_availability":"no","intvolume":"        28","file":[{"date_created":"2024-12-03T09:45:00Z","file_size":1582493,"file_name":"2024_JourGraphAlgorithms_deNooijer.pdf","success":1,"file_id":"18609","creator":"dernst","date_updated":"2024-12-03T09:45:00Z","content_type":"application/pdf","checksum":"be611da6f9d790dc980d6fb7283fe889","access_level":"open_access","relation":"main_file"}],"issue":"2","external_id":{"arxiv":["2202.12175"]},"abstract":[{"lang":"eng","text":"A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a randomized FPT-time algorithm where the parameter is the number of popular faces."}],"file_date_updated":"2024-12-03T09:45:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2026-10-21T13:41:35Z","DOAJ_listed":"1","OA_place":"publisher","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_type":"original","fulldoi":"https://doi.org/10.7155/jgaa.v28i2.2988","OA_type":"gold","date_published":"2024-11-03T00:00:00Z","has_accepted_license":"1","ddc":["510"],"month":"11","publication_status":"published","language":[{"iso":"eng"}],"volume":28,"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"page":"47-82","quality_controlled":"1","article_processing_charge":"No","date_created":"2024-12-01T23:01:54Z","supplementarymaterial":"no","author":[{"last_name":"De Nooijer","full_name":"De Nooijer, Phoebe","first_name":"Phoebe"},{"first_name":"Soeren","last_name":"Terziadis","full_name":"Terziadis, Soeren"},{"last_name":"Weinberger","full_name":"Weinberger, Alexandra","first_name":"Alexandra"},{"full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová","orcid":"0000-0002-6660-1322","first_name":"Zuzana"},{"first_name":"Tamara","last_name":"Mchedlidze","full_name":"Mchedlidze, Tamara"},{"full_name":"Löffler, Maarten","last_name":"Löffler","first_name":"Maarten"},{"first_name":"Günter","last_name":"Rote","full_name":"Rote, Günter"}],"publication":"Journal of Graph Algorithms and Applications","scopus_import":"1","corr_author":"1","type":"journal_article","doi":"10.7155/jgaa.v28i2.2988","title":"Removing popular faces in curve arrangements","oa":1,"publication_identifier":{"issn":["1526-1719"]}},{"fulldoi":"https://doi.org/10.1007/978-3-031-49275-4_2","date_published":"2024-01-06T00:00:00Z","alternative_title":["LNCS"],"date_updated":"2026-10-21T13:41:13Z","abstract":[{"text":"A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces.","lang":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","intvolume":"     14466","external_id":{"isi":["001207942000002"],"arxiv":["2202.12175"]},"oa_version":"Preprint","status":"public","_id":"14888","researchdata_availability":"no","publisher":"Springer Nature","acknowledgement":"This work was initiated at the 16th European Research Week on Geometric Graphs in Strobl in 2019. A.W. is supported by the Austrian Science Fund (FWF): W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035]. A preliminary version of this work has been presented at the 38th European Workshop on Computational Geometry (EuroCG 2022) in Perugia [9]. A full version of this paper, which includes appendices but is otherwise identical, is available as a technical report [10].","year":"2024","citation":{"mla":"De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.” <i>31st International Symposium on Graph Drawing and Network Visualization</i>, vol. 14466, Springer Nature, 2024, pp. 18–33, doi:<a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">10.1007/978-3-031-49275-4_2</a>.","short":"P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M. Löffler, G. Rote, in:, 31st International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 18–33.","chicago":"De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová, Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve Arrangements.” In <i>31st International Symposium on Graph Drawing and Network Visualization</i>, 14466:18–33. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">https://doi.org/10.1007/978-3-031-49275-4_2</a>.","apa":"De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T., Löffler, M., &#38; Rote, G. (2024). Removing popular faces in curve arrangements. In <i>31st International Symposium on Graph Drawing and Network Visualization</i> (Vol. 14466, pp. 18–33). Isola delle Femmine, Palermo, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">https://doi.org/10.1007/978-3-031-49275-4_2</a>","ieee":"P. De Nooijer <i>et al.</i>, “Removing popular faces in curve arrangements,” in <i>31st International Symposium on Graph Drawing and Network Visualization</i>, Isola delle Femmine, Palermo, Italy, 2024, vol. 14466, pp. 18–33.","ama":"De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve arrangements. In: <i>31st International Symposium on Graph Drawing and Network Visualization</i>. Vol 14466. Springer Nature; 2024:18-33. doi:<a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">10.1007/978-3-031-49275-4_2</a>","ista":"De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler M, Rote G. 2024. Removing popular faces in curve arrangements. 31st International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 14466, 18–33."},"isi":1,"das_tickbox":"0","arxiv":1,"day":"06","type":"conference","doi":"10.1007/978-3-031-49275-4_2","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2202.12175"}],"title":"Removing popular faces in curve arrangements","oa":1,"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783031492747"]},"scopus_import":"1","conference":{"name":"GD: Graph Drawing and Network Visualization","end_date":"2023-09-22","location":"Isola delle Femmine, Palermo, Italy","start_date":"2023-09-20"},"author":[{"first_name":"Phoebe","full_name":"De Nooijer, Phoebe","last_name":"De Nooijer"},{"first_name":"Soeren","full_name":"Terziadis, Soeren","last_name":"Terziadis"},{"full_name":"Weinberger, Alexandra","last_name":"Weinberger","first_name":"Alexandra"},{"full_name":"Masárová, Zuzana","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","first_name":"Zuzana"},{"first_name":"Tamara","full_name":"Mchedlidze, Tamara","last_name":"Mchedlidze"},{"first_name":"Maarten","full_name":"Löffler, Maarten","last_name":"Löffler"},{"last_name":"Rote","full_name":"Rote, Günter","first_name":"Günter"}],"publication":"31st International Symposium on Graph Drawing and Network Visualization","article_processing_charge":"No","supplementarymaterial":"no","date_created":"2024-01-28T23:01:43Z","quality_controlled":"1","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"volume":14466,"page":"18-33","month":"01"}]