[{"doi":"10.1016/j.tcs.2023.114353","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"url":"https://doi.org/10.1016/j.tcs.2023.114353","open_access":"1"}],"quality_controlled":"1","project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"}],"month":"01","publication_identifier":{"issn":["0304-3975"]},"author":[{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","first_name":"Jakub","last_name":"Svoboda","full_name":"Svoboda, Jakub"},{"last_name":"Yeo","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X"}],"date_updated":"2024-01-17T09:23:03Z","date_created":"2024-01-16T13:40:41Z","volume":989,"acknowledgement":"We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021-2024.","year":"2024","publication_status":"epub_ahead","publisher":"Elsevier","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"ec_funded":1,"article_number":"114353","date_published":"2024-01-11T00:00:00Z","publication":"Theoretical Computer Science","citation":{"ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” Theoretical Computer Science, vol. 989. Elsevier, 2024.","apa":"Schmid, S., Svoboda, J., & Yeo, M. X. (2024). Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.114353","ista":"Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. 989, 114353.","ama":"Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. 2024;989. doi:10.1016/j.tcs.2023.114353","chicago":"Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” Theoretical Computer Science. Elsevier, 2024. https://doi.org/10.1016/j.tcs.2023.114353.","short":"S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024).","mla":"Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” Theoretical Computer Science, vol. 989, 114353, Elsevier, 2024, doi:10.1016/j.tcs.2023.114353."},"article_type":"original","day":"11","article_processing_charge":"Yes (via OA deal)","keyword":["General Computer Science","Theoretical Computer Science"],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"14820","status":"public","title":"Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation","intvolume":" 989","abstract":[{"lang":"eng","text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity on \r\n increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+E) . (1+3) for some arbitrary E>0."}],"type":"journal_article"},{"file":[{"content_type":"application/pdf","file_size":602333,"creator":"dernst","file_name":"2023_TheoreticalCompScience_Alistarh.pdf","access_level":"open_access","date_updated":"2023-02-20T07:30:20Z","date_created":"2023-02-20T07:30:20Z","checksum":"b27c5290f2f1500c403494364ee39c9f","success":1,"relation":"main_file","file_id":"12570"}],"oa_version":"Published Version","ddc":["000"],"title":"Wait-free approximate agreement on graphs","status":"public","intvolume":" 948","_id":"12566","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","abstract":[{"text":"Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of approximate agreement on arbitrary undirected connected graphs. Each process is given a node of the graph as input and, if non-faulty, must output a node such that\r\n– all the outputs are within distance 1 of one another, and\r\n– each output value lies on a shortest path between two input values.\r\nFrom prior work, it is known that there is no wait-free algorithm among processes for this problem on any cycle of length , by reduction from 2-set agreement (Castañeda et al., 2018).\r\n\r\nIn this work, we investigate the solvability of this task on general graphs. We give a new, direct proof of the impossibility of approximate agreement on cycles of length , via a generalisation of Sperner's Lemma to convex polygons. We also extend the reduction from 2-set agreement to a larger class of graphs, showing that approximate agreement on these graphs is unsolvable. On the positive side, we present a wait-free algorithm for a different class of graphs, which properly contains the class of chordal graphs.","lang":"eng"}],"issue":"2","type":"journal_article","date_published":"2023-02-28T00:00:00Z","article_type":"original","publication":"Theoretical Computer Science","citation":{"ista":"Alistarh D-A, Ellen F, Rybicki J. 2023. Wait-free approximate agreement on graphs. Theoretical Computer Science. 948(2), 113733.","apa":"Alistarh, D.-A., Ellen, F., & Rybicki, J. (2023). Wait-free approximate agreement on graphs. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.113733","ieee":"D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement on graphs,” Theoretical Computer Science, vol. 948, no. 2. Elsevier, 2023.","ama":"Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs. Theoretical Computer Science. 2023;948(2). doi:10.1016/j.tcs.2023.113733","chicago":"Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate Agreement on Graphs.” Theoretical Computer Science. Elsevier, 2023. https://doi.org/10.1016/j.tcs.2023.113733.","mla":"Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” Theoretical Computer Science, vol. 948, no. 2, 113733, Elsevier, 2023, doi:10.1016/j.tcs.2023.113733.","short":"D.-A. Alistarh, F. Ellen, J. Rybicki, Theoretical Computer Science 948 (2023)."},"day":"28","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","scopus_import":"1","date_created":"2023-02-19T23:00:55Z","date_updated":"2023-08-01T13:17:20Z","volume":948,"author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Faith","last_name":"Ellen","full_name":"Ellen, Faith"},{"full_name":"Rybicki, Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646","first_name":"Joel","last_name":"Rybicki"}],"publication_status":"published","publisher":"Elsevier","department":[{"_id":"DaAl"}],"acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 805223 ScaleML) and under the Marie Skłodowska-Curie grant agreement No. 840605 and from the Natural Sciences and Engineering Research Council of Canada grant RGPIN-2020-04178. Part of this work was done while Faith Ellen was visiting IST Austria.","year":"2023","license":"https://creativecommons.org/licenses/by/4.0/","file_date_updated":"2023-02-20T07:30:20Z","ec_funded":1,"article_number":"113733","language":[{"iso":"eng"}],"doi":"10.1016/j.tcs.2023.113733","isi":1,"quality_controlled":"1","project":[{"call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"},{"grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Coordination in constrained and natural distributed systems"}],"external_id":{"isi":["000934262700001"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"month":"02","publication_identifier":{"issn":["0304-3975"]}},{"article_processing_charge":"No","day":"25","scopus_import":"1","date_published":"2023-10-25T00:00:00Z","citation":{"short":"I. Castellano, A. Giordano Bruno, N. Zava, Theoretical Computer Science 977 (2023).","mla":"Castellano, Ilaria, et al. “Weakly Weighted Generalised Quasi-Metric Spaces and Semilattices.” Theoretical Computer Science, vol. 977, 114129, Elsevier, 2023, doi:10.1016/j.tcs.2023.114129.","chicago":"Castellano, Ilaria, Anna Giordano Bruno, and Nicolò Zava. “Weakly Weighted Generalised Quasi-Metric Spaces and Semilattices.” Theoretical Computer Science. Elsevier, 2023. https://doi.org/10.1016/j.tcs.2023.114129.","ama":"Castellano I, Giordano Bruno A, Zava N. Weakly weighted generalised quasi-metric spaces and semilattices. Theoretical Computer Science. 2023;977. doi:10.1016/j.tcs.2023.114129","ieee":"I. Castellano, A. Giordano Bruno, and N. Zava, “Weakly weighted generalised quasi-metric spaces and semilattices,” Theoretical Computer Science, vol. 977. Elsevier, 2023.","apa":"Castellano, I., Giordano Bruno, A., & Zava, N. (2023). Weakly weighted generalised quasi-metric spaces and semilattices. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.114129","ista":"Castellano I, Giordano Bruno A, Zava N. 2023. Weakly weighted generalised quasi-metric spaces and semilattices. Theoretical Computer Science. 977, 114129."},"publication":"Theoretical Computer Science","article_type":"original","abstract":[{"lang":"eng","text":"Motivated by recent applications to entropy theory in dynamical systems, we generalise notions introduced by Matthews and define weakly weighted and componentwise weakly weighted (generalised) quasi-metrics. We then systematise and extend to full generality the correspondences between these objects and other structures arising in theoretical computer science and dynamics. In particular, we study the correspondences with weak partial metrics and, if the underlying space is a semilattice, with invariant (generalised) quasi-metrics satisfying the descending path condition, and with strictly monotone semi(-co-)valuations.\r\nWe conclude discussing, for endomorphisms of generalised quasi-metric semilattices, a generalisation of both the known intrinsic semilattice entropy and the semigroup entropy."}],"type":"journal_article","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"14362","intvolume":" 977","status":"public","title":"Weakly weighted generalised quasi-metric spaces and semilattices","publication_identifier":{"issn":["0304-3975"]},"month":"10","doi":"10.1016/j.tcs.2023.114129","language":[{"iso":"eng"}],"oa":1,"external_id":{"isi":["001076934000001"],"arxiv":["2212.08424"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2212.08424 "}],"quality_controlled":"1","isi":1,"article_number":"114129","author":[{"first_name":"Ilaria","last_name":"Castellano","full_name":"Castellano, Ilaria"},{"full_name":"Giordano Bruno, Anna","last_name":"Giordano Bruno","first_name":"Anna"},{"full_name":"Zava, Nicolò","id":"c8b3499c-7a77-11eb-b046-aa368cbbf2ad","orcid":"0000-0001-8686-1888","first_name":"Nicolò","last_name":"Zava"}],"volume":977,"date_created":"2023-09-24T22:01:11Z","date_updated":"2024-01-30T13:22:04Z","year":"2023","department":[{"_id":"HeEd"}],"publisher":"Elsevier","publication_status":"published"},{"scopus_import":"1","day":"04","has_accepted_license":"1","article_processing_charge":"No","article_type":"original","page":"1-16","publication":"Theoretical Computer Science","citation":{"short":"T. Petrov, C. Igler, A. Sezgin, T.A. Henzinger, C.C. Guet, Theoretical Computer Science 893 (2021) 1–16.","mla":"Petrov, Tatjana, et al. “Long Lived Transients in Gene Regulation.” Theoretical Computer Science, vol. 893, Elsevier, 2021, pp. 1–16, doi:10.1016/j.tcs.2021.05.023.","chicago":"Petrov, Tatjana, Claudia Igler, Ali Sezgin, Thomas A Henzinger, and Calin C Guet. “Long Lived Transients in Gene Regulation.” Theoretical Computer Science. Elsevier, 2021. https://doi.org/10.1016/j.tcs.2021.05.023.","ama":"Petrov T, Igler C, Sezgin A, Henzinger TA, Guet CC. Long lived transients in gene regulation. Theoretical Computer Science. 2021;893:1-16. doi:10.1016/j.tcs.2021.05.023","ieee":"T. Petrov, C. Igler, A. Sezgin, T. A. Henzinger, and C. C. Guet, “Long lived transients in gene regulation,” Theoretical Computer Science, vol. 893. Elsevier, pp. 1–16, 2021.","apa":"Petrov, T., Igler, C., Sezgin, A., Henzinger, T. A., & Guet, C. C. (2021). Long lived transients in gene regulation. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2021.05.023","ista":"Petrov T, Igler C, Sezgin A, Henzinger TA, Guet CC. 2021. Long lived transients in gene regulation. Theoretical Computer Science. 893, 1–16."},"date_published":"2021-06-04T00:00:00Z","type":"journal_article","abstract":[{"text":"Gene expression is regulated by the set of transcription factors (TFs) that bind to the promoter. The ensuing regulating function is often represented as a combinational logic circuit, where output (gene expression) is determined by current input values (promoter bound TFs) only. However, the simultaneous arrival of TFs is a strong assumption, since transcription and translation of genes introduce intrinsic time delays and there is no global synchronisation among the arrival times of different molecular species at their targets. We present an experimentally implementable genetic circuit with two inputs and one output, which in the presence of small delays in input arrival, exhibits qualitatively distinct population-level phenotypes, over timescales that are longer than typical cell doubling times. From a dynamical systems point of view, these phenotypes represent long-lived transients: although they converge to the same value eventually, they do so after a very long time span. The key feature of this toy model genetic circuit is that, despite having only two inputs and one output, it is regulated by twenty-three distinct DNA-TF configurations, two of which are more stable than others (DNA looped states), one promoting and another blocking the expression of the output gene. Small delays in input arrival time result in a majority of cells in the population quickly reaching the stable state associated with the first input, while exiting of this stable state occurs at a slow timescale. In order to mechanistically model the behaviour of this genetic circuit, we used a rule-based modelling language, and implemented a grid-search to find parameter combinations giving rise to long-lived transients. Our analysis shows that in the absence of feedback, there exist path-dependent gene regulatory mechanisms based on the long timescale of transients. The behaviour of this toy model circuit suggests that gene regulatory networks can exploit event timing to create phenotypes, and it opens the possibility that they could use event timing to memorise events, without regulatory feedback. The model reveals the importance of (i) mechanistically modelling the transitions between the different DNA-TF states, and (ii) employing transient analysis thereof.","lang":"eng"}],"title":"Long lived transients in gene regulation","status":"public","ddc":["004"],"intvolume":" 893","_id":"9647","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","file":[{"file_name":"2021_TheoreticalComputerScience_Petrov.pdf","access_level":"open_access","creator":"dernst","file_size":2566504,"content_type":"application/pdf","file_id":"11364","relation":"main_file","date_created":"2022-05-12T12:13:27Z","date_updated":"2022-05-12T12:13:27Z","success":1,"checksum":"d3aef34cfb13e53bba4cf44d01680793"}],"oa_version":"Published Version","month":"06","publication_identifier":{"issn":["0304-3975"]},"isi":1,"quality_controlled":"1","project":[{"call_identifier":"FWF","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png"},"oa":1,"external_id":{"isi":["000710180500002"]},"language":[{"iso":"eng"}],"doi":"10.1016/j.tcs.2021.05.023","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","file_date_updated":"2022-05-12T12:13:27Z","publication_status":"published","department":[{"_id":"ToHe"},{"_id":"CaGu"}],"publisher":"Elsevier","year":"2021","acknowledgement":"Tatjana Petrov’s research was supported in part by SNSF Advanced Postdoctoral Mobility Fellowship grant number P300P2 161067, the Ministry of Science, Research and the Arts of the state of Baden-Wurttemberg, and the DFG Centre of Excellence 2117 ‘Centre for the Advanced Study of Collective Behaviour’ (ID: 422037984). Claudia Igler is the recipient of a DOC Fellowship of the Austrian Academy of Sciences. Thomas A. Henzinger’s research was supported in part by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award).","date_created":"2021-07-11T22:01:18Z","date_updated":"2023-08-10T14:11:19Z","volume":893,"author":[{"full_name":"Petrov, Tatjana","last_name":"Petrov","first_name":"Tatjana"},{"full_name":"Igler, Claudia","last_name":"Igler","first_name":"Claudia","id":"46613666-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Sezgin, Ali","id":"4C7638DA-F248-11E8-B48F-1D18A9856A87","last_name":"Sezgin","first_name":"Ali"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0001-6220-2052","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","last_name":"Guet","first_name":"Calin C","full_name":"Guet, Calin C"}]},{"abstract":[{"lang":"eng","text":"The Nearest neighbour search (NNS) is a fundamental problem in many application domains dealing with multidimensional data. In a concurrent setting, where dynamic modifications are allowed, a linearizable implementation of the NNS is highly desirable.This paper introduces the LockFree-kD-tree (LFkD-tree ): a lock-free concurrent kD-tree, which implements an abstract data type (ADT) that provides the operations Add, Remove, Contains, and NNS. Our implementation is linearizable. The operations in the LFkD-tree use single-word read and compare-and-swap (Image 1 ) atomic primitives, which are readily supported on available multi-core processors. We experimentally evaluate the LFkD-tree using several benchmarks comprising real-world and synthetic datasets. The experiments show that the presented design is scalable and achieves significant speed-up compared to the implementations of an existing sequential kD-tree and a recently proposed multidimensional indexing structure, PH-tree."}],"type":"journal_article","oa_version":"Submitted Version","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"9827","intvolume":" 886","status":"public","title":"Concurrent linearizable nearest neighbour search in LockFree-kD-tree","article_processing_charge":"No","day":"13","scopus_import":"1","keyword":["Concurrent data structure","kD-tree","Nearest neighbor search","Similarity search","Lock-free","Linearizability"],"date_published":"2021-09-13T00:00:00Z","citation":{"ista":"Chatterjee B, Walulya I, Tsigas P. 2021. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science. 886, 27–48.","apa":"Chatterjee, B., Walulya, I., & Tsigas, P. (2021). Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2021.06.041","ieee":"B. Chatterjee, I. Walulya, and P. Tsigas, “Concurrent linearizable nearest neighbour search in LockFree-kD-tree,” Theoretical Computer Science, vol. 886. Elsevier, pp. 27–48, 2021.","ama":"Chatterjee B, Walulya I, Tsigas P. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science. 2021;886:27-48. doi:10.1016/j.tcs.2021.06.041","chicago":"Chatterjee, Bapi, Ivan Walulya, and Philippas Tsigas. “Concurrent Linearizable Nearest Neighbour Search in LockFree-KD-Tree.” Theoretical Computer Science. Elsevier, 2021. https://doi.org/10.1016/j.tcs.2021.06.041.","mla":"Chatterjee, Bapi, et al. “Concurrent Linearizable Nearest Neighbour Search in LockFree-KD-Tree.” Theoretical Computer Science, vol. 886, Elsevier, 2021, pp. 27–48, doi:10.1016/j.tcs.2021.06.041.","short":"B. Chatterjee, I. Walulya, P. Tsigas, Theoretical Computer Science 886 (2021) 27–48."},"publication":"Theoretical Computer Science","page":"27-48","article_type":"original","author":[{"full_name":"Chatterjee, Bapi","orcid":"0000-0002-2742-4028","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Bapi"},{"full_name":"Walulya, Ivan","last_name":"Walulya","first_name":"Ivan"},{"full_name":"Tsigas, Philippas","last_name":"Tsigas","first_name":"Philippas"}],"volume":886,"date_created":"2021-08-08T22:01:31Z","date_updated":"2023-08-10T14:27:43Z","year":"2021","department":[{"_id":"DaAl"}],"publisher":"Elsevier","publication_status":"published","publication_identifier":{"issn":["0304-3975"]},"month":"09","doi":"10.1016/j.tcs.2021.06.041","language":[{"iso":"eng"}],"external_id":{"isi":["000694718900004"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://publications.lib.chalmers.se/records/fulltext/232185/232185.pdf"}],"quality_controlled":"1","isi":1},{"quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1902.02304","open_access":"1"}],"oa":1,"external_id":{"arxiv":["1902.02304"]},"language":[{"iso":"eng"}],"doi":"10.1016/j.tcs.2019.01.043","month":"08","publication_identifier":{"issn":["0304-3975"]},"publication_status":"published","publisher":"Elsevier","year":"2019","date_updated":"2022-09-09T11:29:04Z","date_created":"2022-08-17T09:02:15Z","volume":779,"author":[{"full_name":"Bhattacharya, Sayan","first_name":"Sayan","last_name":"Bhattacharya"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H"},{"full_name":"Neumann, Stefan","last_name":"Neumann","first_name":"Stefan"}],"extern":"1","article_type":"original","page":"72-87","publication":"Theoretical Computer Science","citation":{"apa":"Bhattacharya, S., Henzinger, M. H., & Neumann, S. (2019). New amortized cell-probe lower bounds for dynamic problems. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2019.01.043","ieee":"S. Bhattacharya, M. H. Henzinger, and S. Neumann, “New amortized cell-probe lower bounds for dynamic problems,” Theoretical Computer Science, vol. 779. Elsevier, pp. 72–87, 2019.","ista":"Bhattacharya S, Henzinger MH, Neumann S. 2019. New amortized cell-probe lower bounds for dynamic problems. Theoretical Computer Science. 779, 72–87.","ama":"Bhattacharya S, Henzinger MH, Neumann S. New amortized cell-probe lower bounds for dynamic problems. Theoretical Computer Science. 2019;779:72-87. doi:10.1016/j.tcs.2019.01.043","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Stefan Neumann. “New Amortized Cell-Probe Lower Bounds for Dynamic Problems.” Theoretical Computer Science. Elsevier, 2019. https://doi.org/10.1016/j.tcs.2019.01.043.","short":"S. Bhattacharya, M.H. Henzinger, S. Neumann, Theoretical Computer Science 779 (2019) 72–87.","mla":"Bhattacharya, Sayan, et al. “New Amortized Cell-Probe Lower Bounds for Dynamic Problems.” Theoretical Computer Science, vol. 779, Elsevier, 2019, pp. 72–87, doi:10.1016/j.tcs.2019.01.043."},"date_published":"2019-08-02T00:00:00Z","scopus_import":"1","day":"02","article_processing_charge":"No","title":"New amortized cell-probe lower bounds for dynamic problems","status":"public","intvolume":" 779","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11898","oa_version":"Preprint","type":"journal_article","abstract":[{"text":"We build upon the recent papers by Weinstein and Yu (FOCS'16), Larsen (FOCS'12), and Clifford et al. (FOCS'15) to present a general framework that gives amortized lower bounds on the update and query times of dynamic data structures. Using our framework, we present two concrete results.\r\n(1) For the dynamic polynomial evaluation problem, where the polynomial is defined over a finite field of size n1+Ω(1) and has degree n, any dynamic data structure must either have an amortized update time of Ω((lgn/lglgn)2) or an amortized query time of Ω((lgn/lglgn)2).\r\n(2) For the dynamic online matrix vector multiplication problem, where we get an n×n matrix whose entires are drawn from a finite field of size nΘ(1), any dynamic data structure must either have an amortized update time of Ω((lgn/lglgn)2) or an amortized query time of Ω(n⋅(lgn/lglgn)2).\r\nFor these two problems, the previous works by Larsen (FOCS'12) and Clifford et al. (FOCS'15) gave the same lower bounds, but only for worst case update and query times. Our bounds match the highest unconditional lower bounds known till date for any dynamic problem in the cell-probe model.","lang":"eng"}]},{"extern":"1","year":"2015","publication_status":"published","publisher":"Elsevier","author":[{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Loitzenbauer, Veronika","last_name":"Loitzenbauer","first_name":"Veronika"}],"date_updated":"2023-02-17T14:50:04Z","date_created":"2022-08-17T09:06:53Z","volume":573,"month":"03","publication_identifier":{"issn":["0304-3975"]},"main_file_link":[{"url":"https://doi.org/10.1016/j.tcs.2015.01.033","open_access":"1"}],"oa":1,"quality_controlled":"1","doi":"10.1016/j.tcs.2015.01.033","language":[{"iso":"eng"}],"type":"journal_article","abstract":[{"text":"We consider auctions of indivisible items to unit-demand bidders with budgets. This setting was suggested as an expressive model for single sponsored search auctions. Prior work presented mechanisms that compute bidder-optimal outcomes and are truthful for a restricted set of inputs, i.e., inputs in so-called general position. This condition is easily violated. We provide the first mechanism that is truthful in expectation for all inputs and achieves for each bidder no worse utility than the bidder-optimal outcome. Additionally we give a complete characterization for which inputs mechanisms that compute bidder-optimal outcomes are truthful.","lang":"eng"}],"_id":"11901","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Truthful unit-demand auctions with budgets revisited","intvolume":" 573","oa_version":"None","scopus_import":"1","day":"30","article_processing_charge":"No","publication":"Theoretical Computer Science","citation":{"chicago":"Henzinger, Monika H, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” Theoretical Computer Science. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.01.033.","short":"M.H. Henzinger, V. Loitzenbauer, Theoretical Computer Science 573 (2015) 1–15.","mla":"Henzinger, Monika H., and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” Theoretical Computer Science, vol. 573, Elsevier, 2015, pp. 1–15, doi:10.1016/j.tcs.2015.01.033.","ieee":"M. H. Henzinger and V. Loitzenbauer, “Truthful unit-demand auctions with budgets revisited,” Theoretical Computer Science, vol. 573. Elsevier, pp. 1–15, 2015.","apa":"Henzinger, M. H., & Loitzenbauer, V. (2015). Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2015.01.033","ista":"Henzinger MH, Loitzenbauer V. 2015. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 573, 1–15.","ama":"Henzinger MH, Loitzenbauer V. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 2015;573:1-15. doi:10.1016/j.tcs.2015.01.033"},"article_type":"original","page":"1-15","date_published":"2015-03-30T00:00:00Z"},{"publication_status":"published","status":"public","title":"From prima quadraginta octant to lattice sphere through primitive integer operations","intvolume":" 624","publisher":"Elsevier","_id":"5804","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2015","date_created":"2019-01-08T20:44:06Z","date_updated":"2021-01-12T08:03:36Z","volume":624,"oa_version":"None","author":[{"orcid":"0000-0002-5372-7890","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","last_name":"Biswas","first_name":"Ranita","full_name":"Biswas, Ranita"},{"full_name":"Bhowmick, Partha","last_name":"Bhowmick","first_name":"Partha"}],"type":"journal_article","extern":"1","abstract":[{"text":"We present here the first integer-based algorithm for constructing a well-defined lattice sphere specified by integer radius and integer center. The algorithm evolves from a unique correspondence between the lattice points comprising the sphere and the distribution of sum of three square numbers in integer intervals. We characterize these intervals to derive a useful set of recurrences, which, in turn, aids in efficient computation. Each point of the lattice sphere is determined by resorting to only a few primitive operations in the integer domain. The symmetry of its quadraginta octants provides an added advantage by confining the computation to its prima quadraginta octant. Detailed theoretical analysis and experimental results have been furnished to demonstrate its simplicity and elegance.","lang":"eng"}],"issue":"4","quality_controlled":"1","page":"56-72","publication":"Theoretical Computer Science","citation":{"short":"R. Biswas, P. Bhowmick, Theoretical Computer Science 624 (2015) 56–72.","mla":"Biswas, Ranita, and Partha Bhowmick. “From Prima Quadraginta Octant to Lattice Sphere through Primitive Integer Operations.” Theoretical Computer Science, vol. 624, no. 4, Elsevier, 2015, pp. 56–72, doi:10.1016/j.tcs.2015.11.018.","chicago":"Biswas, Ranita, and Partha Bhowmick. “From Prima Quadraginta Octant to Lattice Sphere through Primitive Integer Operations.” Theoretical Computer Science. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.11.018.","ama":"Biswas R, Bhowmick P. From prima quadraginta octant to lattice sphere through primitive integer operations. Theoretical Computer Science. 2015;624(4):56-72. doi:10.1016/j.tcs.2015.11.018","ieee":"R. Biswas and P. Bhowmick, “From prima quadraginta octant to lattice sphere through primitive integer operations,” Theoretical Computer Science, vol. 624, no. 4. Elsevier, pp. 56–72, 2015.","apa":"Biswas, R., & Bhowmick, P. (2015). From prima quadraginta octant to lattice sphere through primitive integer operations. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2015.11.018","ista":"Biswas R, Bhowmick P. 2015. From prima quadraginta octant to lattice sphere through primitive integer operations. Theoretical Computer Science. 624(4), 56–72."},"language":[{"iso":"eng"}],"doi":"10.1016/j.tcs.2015.11.018","date_published":"2015-04-18T00:00:00Z","day":"18","month":"04","publication_identifier":{"issn":["0304-3975"]}},{"status":"public","title":"On different topological classes of spherical geodesic paths and circles inZ3","publication_status":"published","intvolume":" 605","publisher":"Elsevier","_id":"5807","year":"2015","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2019-01-08T20:44:52Z","date_updated":"2021-01-12T08:03:37Z","oa_version":"None","volume":605,"author":[{"first_name":"Ranita","last_name":"Biswas","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5372-7890","full_name":"Biswas, Ranita"},{"last_name":"Bhowmick","first_name":"Partha","full_name":"Bhowmick, Partha"}],"type":"journal_article","extern":"1","issue":"11","quality_controlled":"1","page":"146-163","publication":"Theoretical Computer Science","citation":{"ieee":"R. Biswas and P. Bhowmick, “On different topological classes of spherical geodesic paths and circles inZ3,” Theoretical Computer Science, vol. 605, no. 11. Elsevier, pp. 146–163, 2015.","apa":"Biswas, R., & Bhowmick, P. (2015). On different topological classes of spherical geodesic paths and circles inZ3. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2015.09.003","ista":"Biswas R, Bhowmick P. 2015. On different topological classes of spherical geodesic paths and circles inZ3. Theoretical Computer Science. 605(11), 146–163.","ama":"Biswas R, Bhowmick P. On different topological classes of spherical geodesic paths and circles inZ3. Theoretical Computer Science. 2015;605(11):146-163. doi:10.1016/j.tcs.2015.09.003","chicago":"Biswas, Ranita, and Partha Bhowmick. “On Different Topological Classes of Spherical Geodesic Paths and Circles InZ3.” Theoretical Computer Science. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.09.003.","short":"R. Biswas, P. Bhowmick, Theoretical Computer Science 605 (2015) 146–163.","mla":"Biswas, Ranita, and Partha Bhowmick. “On Different Topological Classes of Spherical Geodesic Paths and Circles InZ3.” Theoretical Computer Science, vol. 605, no. 11, Elsevier, 2015, pp. 146–63, doi:10.1016/j.tcs.2015.09.003."},"language":[{"iso":"eng"}],"date_published":"2015-11-09T00:00:00Z","doi":"10.1016/j.tcs.2015.09.003","month":"11","day":"09","publication_identifier":{"issn":["0304-3975"]}},{"extern":"1","volume":478,"date_created":"2022-08-17T11:11:04Z","date_updated":"2023-02-21T16:28:41Z","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"11799"}]},"author":[{"first_name":"Paul","last_name":"Dütting","full_name":"Dütting, Paul"},{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"first_name":"Ingmar","last_name":"Weber","full_name":"Weber, Ingmar"}],"publisher":"Elsevier","publication_status":"published","year":"2013","publication_identifier":{"issn":["0304-3975"]},"month":"03","language":[{"iso":"eng"}],"doi":"10.1016/j.tcs.2013.01.030","quality_controlled":"1","issue":"3","abstract":[{"lang":"eng","text":"We study the problem of matching bidders to items where each bidder i has general, strictly monotonic utility functions ui,j(pj) expressing his utility of being matched to item j at price pj. For this setting we prove that a bidder optimal outcome always exists, even when the utility functions are non-linear and non-continuous. We give sufficient conditions under\r\nwhich every mechanism that finds a bidder optimal outcome is incentive compatible. We also give a mechanism that finds a bidder optimal outcome if the conditions for incentive compatibility are satisfied. The running time of this mechanism is exponential in the number of items, but polynomial in the number of bidders."}],"type":"journal_article","oa_version":"None","intvolume":" 478","status":"public","title":"Bidder optimal assignments for general utilities","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11902","article_processing_charge":"No","day":"25","scopus_import":"1","date_published":"2013-03-25T00:00:00Z","page":"22-32","article_type":"original","citation":{"short":"P. Dütting, M.H. Henzinger, I. Weber, Theoretical Computer Science 478 (2013) 22–32.","mla":"Dütting, Paul, et al. “Bidder Optimal Assignments for General Utilities.” Theoretical Computer Science, vol. 478, no. 3, Elsevier, 2013, pp. 22–32, doi:10.1016/j.tcs.2013.01.030.","chicago":"Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Bidder Optimal Assignments for General Utilities.” Theoretical Computer Science. Elsevier, 2013. https://doi.org/10.1016/j.tcs.2013.01.030.","ama":"Dütting P, Henzinger MH, Weber I. Bidder optimal assignments for general utilities. Theoretical Computer Science. 2013;478(3):22-32. doi:10.1016/j.tcs.2013.01.030","ieee":"P. Dütting, M. H. Henzinger, and I. Weber, “Bidder optimal assignments for general utilities,” Theoretical Computer Science, vol. 478, no. 3. Elsevier, pp. 22–32, 2013.","apa":"Dütting, P., Henzinger, M. H., & Weber, I. (2013). Bidder optimal assignments for general utilities. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2013.01.030","ista":"Dütting P, Henzinger MH, Weber I. 2013. Bidder optimal assignments for general utilities. Theoretical Computer Science. 478(3), 22–32."},"publication":"Theoretical Computer Science"},{"citation":{"chicago":"Raskin, Jean, Pierre Schobbens, and Thomas A Henzinger. “Axioms for Real-Time Logics.” Theoretical Computer Science. Elsevier, 2002. https://doi.org/10.1016/S0304-3975(00)00308-X.","short":"J. Raskin, P. Schobbens, T.A. Henzinger, Theoretical Computer Science 274 (2002) 151–182.","mla":"Raskin, Jean, et al. “Axioms for Real-Time Logics.” Theoretical Computer Science, vol. 274, no. 1–2, Elsevier, 2002, pp. 151–82, doi:10.1016/S0304-3975(00)00308-X.","apa":"Raskin, J., Schobbens, P., & Henzinger, T. A. (2002). Axioms for real-time logics. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/S0304-3975(00)00308-X","ieee":"J. Raskin, P. Schobbens, and T. A. Henzinger, “Axioms for real-time logics,” Theoretical Computer Science, vol. 274, no. 1–2. Elsevier, pp. 151–182, 2002.","ista":"Raskin J, Schobbens P, Henzinger TA. 2002. Axioms for real-time logics. Theoretical Computer Science. 274(1–2), 151–182.","ama":"Raskin J, Schobbens P, Henzinger TA. Axioms for real-time logics. Theoretical Computer Science. 2002;274(1-2):151-182. doi:10.1016/S0304-3975(00)00308-X"},"publication":"Theoretical Computer Science","page":"151 - 182","article_type":"original","date_published":"2002-03-01T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"01","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4407","intvolume":" 274","title":"Axioms for real-time logics","status":"public","oa_version":"None","type":"journal_article","issue":"1-2","abstract":[{"text":"This paper presents a complete axiomatization of two decidable propositional real-time linear temporal logics: Event Clock Logic (EventClockTL) and Metric Interval Temporal Logic with past (MetricIntervalTL). The completeness proof consists of an effective proof building procedure for EventClockTL. From this result we obtain a complete axiomatization of MetricIntervalTL by providing axioms translating MetricIntervalTL formulae into EventClockTL formulae, the two logics being equally expressive. Our proof is structured to yield axiomatizations also for interesting fragments of these logics, such as the linear temporal logic of the real numbers (TLR).","lang":"eng"}],"quality_controlled":"1","doi":"10.1016/S0304-3975(00)00308-X","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0304-3975"]},"month":"03","year":"2002","publisher":"Elsevier","publication_status":"published","author":[{"last_name":"Raskin","first_name":"Jean","full_name":"Raskin, Jean"},{"first_name":"Pierre","last_name":"Schobbens","full_name":"Schobbens, Pierre"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A"}],"volume":274,"date_created":"2018-12-11T12:08:42Z","date_updated":"2023-06-06T09:10:56Z","publist_id":"324","extern":"1"},{"type":"journal_article","issue":"1-2","abstract":[{"lang":"eng","text":"Rectangular hybrid automata model digital control programs of analog plant environments. We study rectangular hybrid automata where the plant state evolves continuously in real-numbered time, and the controller samples the plant state and changes the control state discretely, only at the integer points in time. We prove that rectangular hybrid automata have finite bisimilarity quotients when all control transitions happen at integer times, even if the constraints on the derivatives of the variables vary between control states. This is in contrast with the conventional model where control transitions may happen at any real time, and already the reachability problem is undecidable. Based on the finite bisimilarity quotients, we give an exponential algorithm for the symbolic sampling-controller synthesis of rectangular automata. We show our algorithm to be optimal by proving the problem to be EXPTIME-hard. We also show that rectangular automata form a maximal class of systems for which the sampling-controller synthesis problem can be solved algorithmically."}],"_id":"4442","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 221","title":"Discrete-time control for rectangular hybrid automata","status":"public","oa_version":"None","scopus_import":"1","article_processing_charge":"No","day":"01","citation":{"mla":"Henzinger, Thomas A., and Peter Kopke. “Discrete-Time Control for Rectangular Hybrid Automata.” Theoretical Computer Science, vol. 221, no. 1–2, Elsevier, 1999, pp. 369–92, doi:10.1016/S0304-3975(99)00038-9.","short":"T.A. Henzinger, P. Kopke, Theoretical Computer Science 221 (1999) 369–392.","chicago":"Henzinger, Thomas A, and Peter Kopke. “Discrete-Time Control for Rectangular Hybrid Automata.” Theoretical Computer Science. Elsevier, 1999. https://doi.org/10.1016/S0304-3975(99)00038-9.","ama":"Henzinger TA, Kopke P. Discrete-time control for rectangular hybrid automata. Theoretical Computer Science. 1999;221(1-2):369-392. doi:10.1016/S0304-3975(99)00038-9","ista":"Henzinger TA, Kopke P. 1999. Discrete-time control for rectangular hybrid automata. Theoretical Computer Science. 221(1–2), 369–392.","ieee":"T. A. Henzinger and P. Kopke, “Discrete-time control for rectangular hybrid automata,” Theoretical Computer Science, vol. 221, no. 1–2. Elsevier, pp. 369–392, 1999.","apa":"Henzinger, T. A., & Kopke, P. (1999). Discrete-time control for rectangular hybrid automata. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/S0304-3975(99)00038-9"},"publication":"Theoretical Computer Science","page":"369 - 392","article_type":"original","date_published":"1999-01-01T00:00:00Z","publist_id":"290","extern":"1","year":"1999","publisher":"Elsevier","publication_status":"published","author":[{"orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"full_name":"Kopke, Peter","first_name":"Peter","last_name":"Kopke"}],"volume":221,"date_updated":"2022-09-06T08:03:48Z","date_created":"2018-12-11T12:08:52Z","publication_identifier":{"issn":["0304-3975"]},"month":"01","quality_controlled":"1","doi":"10.1016/S0304-3975(99)00038-9","language":[{"iso":"eng"}]},{"page":"3 - 34","article_type":"original","citation":{"ista":"Alur R, Courcoubetis C, Halbwachs N, Henzinger TA, Ho P, Nicollin X, Olivero A, Sifakis J, Yovine S. 1995. The algorithmic analysis of hybrid systems. Theoretical Computer Science. 138(1), 3–34.","ieee":"R. Alur et al., “The algorithmic analysis of hybrid systems,” Theoretical Computer Science, vol. 138, no. 1. Elsevier, pp. 3–34, 1995.","apa":"Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T. A., Ho, P., Nicollin, X., … Yovine, S. (1995). The algorithmic analysis of hybrid systems. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(94)00202-T","ama":"Alur R, Courcoubetis C, Halbwachs N, et al. The algorithmic analysis of hybrid systems. Theoretical Computer Science. 1995;138(1):3-34. doi:10.1016/0304-3975(94)00202-T","chicago":"Alur, Rajeev, Costas Courcoubetis, Nicolas Halbwachs, Thomas A Henzinger, Pei Ho, Xavier Nicollin, Alfredo Olivero, Joseph Sifakis, and Sergio Yovine. “The Algorithmic Analysis of Hybrid Systems.” Theoretical Computer Science. Elsevier, 1995. https://doi.org/10.1016/0304-3975(94)00202-T.","mla":"Alur, Rajeev, et al. “The Algorithmic Analysis of Hybrid Systems.” Theoretical Computer Science, vol. 138, no. 1, Elsevier, 1995, pp. 3–34, doi:10.1016/0304-3975(94)00202-T.","short":"R. Alur, C. Courcoubetis, N. Halbwachs, T.A. Henzinger, P. Ho, X. Nicollin, A. Olivero, J. Sifakis, S. Yovine, Theoretical Computer Science 138 (1995) 3–34."},"publication":"Theoretical Computer Science","date_published":"1995-02-06T00:00:00Z","article_processing_charge":"No","day":"06","intvolume":" 138","title":"The algorithmic analysis of hybrid systems","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4613","oa_version":"None","type":"journal_article","issue":"1","abstract":[{"lang":"eng","text":"We present a general framework for the formal specification and algorithmic analysis of hybrid systems. A hybrid system consists of a discrete program with an analog environment. We model hybrid systems as finite automata equipped with variables that evolve continuously with time according to dynamical laws. For verification purposes, we restrict ourselves to linear hybrid systems, where all variables follow piecewise-linear trajectories. We provide decidability and undecidability results for classes of linear hybrid systems, and we show that standard program-analysis techniques can be adapted to linear hybrid systems. In particular, we consider symbolic model-checking and minimization procedures that are based on the reachability analysis of an infinite state space. The procedures iteratively compute state sets that are definable as unions of convex polyhedra in multidimensional real space. We also present approximation techniques for dealing with systems for which the iterative procedures do not converge."}],"quality_controlled":"1","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/030439759400202T?via%3Dihub"}],"language":[{"iso":"eng"}],"doi":"10.1016/0304-3975(94)00202-T","publication_identifier":{"issn":["0304-3975"]},"month":"02","publisher":"Elsevier","publication_status":"published","year":"1995","volume":138,"date_created":"2018-12-11T12:09:45Z","date_updated":"2022-06-09T13:40:48Z","author":[{"full_name":"Alur, Rajeev","last_name":"Alur","first_name":"Rajeev"},{"last_name":"Courcoubetis","first_name":"Costas","full_name":"Courcoubetis, Costas"},{"full_name":"Halbwachs, Nicolas","first_name":"Nicolas","last_name":"Halbwachs"},{"full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724"},{"full_name":"Ho, Pei","first_name":"Pei","last_name":"Ho"},{"last_name":"Nicollin","first_name":"Xavier","full_name":"Nicollin, Xavier"},{"first_name":"Alfredo","last_name":"Olivero","full_name":"Olivero, Alfredo"},{"full_name":"Sifakis, Joseph","last_name":"Sifakis","first_name":"Joseph"},{"first_name":"Sergio","last_name":"Yovine","full_name":"Yovine, Sergio"}],"extern":"1","publist_id":"94"},{"publist_id":"2079","extern":"1","author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"full_name":"Pach, János","first_name":"János","last_name":"Pach"},{"full_name":"Pollack, Richard","last_name":"Pollack","first_name":"Richard"},{"first_name":"Raimund","last_name":"Seidel","full_name":"Seidel, Raimund"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"}],"volume":92,"date_created":"2018-12-11T12:06:37Z","date_updated":"2022-03-16T09:04:37Z","year":"1992","acknowledgement":"Work on this paper by the first author has been supported by the National Science Foundation under grant CCR-8714565. Work by the third and sixth authors has been supported by Office of Naval Research Grant NOOOl4-82-K-0381, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the sixth author has also been supported by a research grant from the NCRD- the Israeli National Council for Research and Development. Work by the fourth author has been supported by National Science Foundation Grant DMS-8501947. ","publisher":"Elsevier","publication_status":"published","publication_identifier":{"issn":["0304-3975"]},"month":"01","doi":"10.1016/0304-3975(92)90319-B","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://www.sciencedirect.com/science/article/pii/030439759290319B?via%3Dihub"}],"oa":1,"quality_controlled":"1","issue":"2","abstract":[{"text":"Arrangements of curves in the plane are fundamental to many problems in computational and combinatorial geometry (e.g. motion planning, algebraic cell decomposition, etc.). In this paper we study various topological and combinatorial properties of such arrangements under some mild assumptions on the shape of the curves, and develop basic tools for the construction, manipulation, and analysis of these arrangements. Our main results include a generalization of the zone theorem of Edelsbrunner (1986) and Chazelle (1985) to arrangements of curves (in which we show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves) and an application of that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements.","lang":"eng"}],"type":"journal_article","oa_version":"Published Version","_id":"4047","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 92","status":"public","title":"Arrangements of curves in the plane - topology, combinatorics, and algorithms","article_processing_charge":"No","day":"20","scopus_import":"1","date_published":"1992-01-20T00:00:00Z","citation":{"ama":"Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. Arrangements of curves in the plane - topology, combinatorics, and algorithms. Theoretical Computer Science. 1992;92(2):319-336. doi:10.1016/0304-3975(92)90319-B","ista":"Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. 1992. Arrangements of curves in the plane - topology, combinatorics, and algorithms. Theoretical Computer Science. 92(2), 319–336.","ieee":"H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, “Arrangements of curves in the plane - topology, combinatorics, and algorithms,” Theoretical Computer Science, vol. 92, no. 2. Elsevier, pp. 319–336, 1992.","apa":"Edelsbrunner, H., Guibas, L., Pach, J., Pollack, R., Seidel, R., & Sharir, M. (1992). Arrangements of curves in the plane - topology, combinatorics, and algorithms. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(92)90319-B","mla":"Edelsbrunner, Herbert, et al. “Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms.” Theoretical Computer Science, vol. 92, no. 2, Elsevier, 1992, pp. 319–36, doi:10.1016/0304-3975(92)90319-B.","short":"H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, M. Sharir, Theoretical Computer Science 92 (1992) 319–336.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, János Pach, Richard Pollack, Raimund Seidel, and Micha Sharir. “Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms.” Theoretical Computer Science. Elsevier, 1992. https://doi.org/10.1016/0304-3975(92)90319-B."},"publication":"Theoretical Computer Science","page":"319 - 336","article_type":"original"},{"article_processing_charge":"No","day":"22","scopus_import":"1","date_published":"1991-07-22T00:00:00Z","citation":{"ama":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M. A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoretical Computer Science. 1991;84(1):77-105. doi:10.1016/0304-3975(91)90261-Y","ista":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1991. A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoretical Computer Science. 84(1), 77–105.","ieee":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “A singly exponential stratification scheme for real semi-algebraic varieties and its applications,” Theoretical Computer Science, vol. 84, no. 1. Elsevier, pp. 77–105, 1991.","apa":"Chazelle, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1991). A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(91)90261-Y","mla":"Chazelle, Bernard, et al. “A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications.” Theoretical Computer Science, vol. 84, no. 1, Elsevier, 1991, pp. 77–105, doi:10.1016/0304-3975(91)90261-Y.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Theoretical Computer Science 84 (1991) 77–105.","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. “A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications.” Theoretical Computer Science. Elsevier, 1991. https://doi.org/10.1016/0304-3975(91)90261-Y."},"publication":"Theoretical Computer Science","page":"77 - 105","article_type":"original","issue":"1","abstract":[{"text":"This paper describes an effective procedure for stratifying a real semi-algebraic set into cells of constant description size. The attractive feature of our method is that the number of cells produced is singly exponential in the number of input variables. This compares favorably with the doubly exponential size of Collins' decomposition. Unlike Collins' construction, however, our scheme does not produce a cell complex but only a smooth stratification. Nevertheless, we are able to apply our results in interesting ways to problems of point location and geometric optimization.","lang":"eng"}],"type":"journal_article","oa_version":"Published Version","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4052","intvolume":" 84","status":"public","title":"A singly exponential stratification scheme for real semi-algebraic varieties and its applications","publication_identifier":{"eissn":["1879-2294"],"issn":["0304-3975"]},"month":"07","doi":"10.1016/0304-3975(91)90261-Y","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://www.sciencedirect.com/science/article/pii/030439759190261Y?via%3Dihub"}],"oa":1,"quality_controlled":"1","publist_id":"2073","extern":"1","author":[{"full_name":"Chazelle, Bernard","first_name":"Bernard","last_name":"Chazelle"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"}],"volume":84,"date_created":"2018-12-11T12:06:39Z","date_updated":"2022-03-02T10:23:58Z","acknowledgement":"The authors wish to thank DEC/Systems Research Center and DEC/Paris Research Laboratory, where part of this research was conducted. For individual support, Bernard Chazelle acknowledges the National Science Foundation for supporting this research in part under Grant CCR-8700917. Herbert Edelsbrunner acknowledges the support of the National Science Foundation under Grant CCR-8714565. Micha Sharir acknowledges the Office of Naval Research under Grant N00014-87-K-0129, the National Science Foundation under Grant No. NSF-DCR-83-20085, grants from the Digital Equipment Corporation and the IBM Corporation, and a research grant from the US-Israeli Binational Science Foundation.","year":"1991","publisher":"Elsevier","publication_status":"published"},{"oa_version":"Published Version","status":"public","title":"Testing the necklace condition for shortest tours and optimal factors in the plane","intvolume":" 66","_id":"4084","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","abstract":[{"text":"A tour of a finite set P of points is a necklace-tour if there are disks with the points in P as centers such that two disks intersect if and only if their centers are adjacent in . It has been observed by Sanders that a necklace-tour is an optimal traveling salesman tour.\r\n\r\nIn this paper, we present an algorithm that either reports that no necklace-tour exists or outputs a necklace-tour of a given set of n points in O(n2 log n) time. If a tour is given, then we can test in O(n2) time whether or not this tour is a necklace-tour. Both algorithms can be generalized to ƒ-factors of point sets in the plane. The complexity results rely on a combinatorial analysis of certain intersection graphs of disks defined for finite sets of points in the plane.","lang":"eng"}],"issue":"2","type":"journal_article","date_published":"1989-08-01T00:00:00Z","article_type":"original","page":"157 - 180","publication":"Theoretical Computer Science","citation":{"ama":"Edelsbrunner H, Rote G, Welzl E. Testing the necklace condition for shortest tours and optimal factors in the plane. Theoretical Computer Science. 1989;66(2):157-180. doi:10.1016/0304-3975(89)90133-3","ista":"Edelsbrunner H, Rote G, Welzl E. 1989. Testing the necklace condition for shortest tours and optimal factors in the plane. Theoretical Computer Science. 66(2), 157–180.","apa":"Edelsbrunner, H., Rote, G., & Welzl, E. (1989). Testing the necklace condition for shortest tours and optimal factors in the plane. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(89)90133-3","ieee":"H. Edelsbrunner, G. Rote, and E. Welzl, “Testing the necklace condition for shortest tours and optimal factors in the plane,” Theoretical Computer Science, vol. 66, no. 2. Elsevier, pp. 157–180, 1989.","mla":"Edelsbrunner, Herbert, et al. “Testing the Necklace Condition for Shortest Tours and Optimal Factors in the Plane.” Theoretical Computer Science, vol. 66, no. 2, Elsevier, 1989, pp. 157–80, doi:10.1016/0304-3975(89)90133-3.","short":"H. Edelsbrunner, G. Rote, E. Welzl, Theoretical Computer Science 66 (1989) 157–180.","chicago":"Edelsbrunner, Herbert, Günter Rote, and Emo Welzl. “Testing the Necklace Condition for Shortest Tours and Optimal Factors in the Plane.” Theoretical Computer Science. Elsevier, 1989. https://doi.org/10.1016/0304-3975(89)90133-3."},"day":"01","article_processing_charge":"No","scopus_import":"1","date_updated":"2022-02-11T11:15:43Z","date_created":"2018-12-11T12:06:51Z","volume":66,"author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"last_name":"Rote","first_name":"Günter","full_name":"Rote, Günter"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"publication_status":"published","publisher":"Elsevier","year":"1989","extern":"1","publist_id":"2041","language":[{"iso":"eng"}],"doi":"10.1016/0304-3975(89)90133-3","quality_controlled":"1","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0304397589901333?via%3Dihub","open_access":"1"}],"oa":1,"month":"08","publication_identifier":{"eissn":["1879-2294"],"issn":["0304-3975"]}},{"oa_version":"Published Version","status":"public","title":"Finding Transversals for Sets of Simple Geometric-Figures","intvolume":" 35","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4116","abstract":[{"text":"A straight line that intersects all members of a set S of objects in the real plane is called a transversal of S. Geometric transforms are described that reduce transversal problems for various types of objects to convex hull problems for points. These reductions lead to efficient algorithms for finding transversals which are also described. Applications of the algorithms are found in computer graphics: “Reproduce the line displayed by a collection of pixels”, and in statistics: “Find the line that minimizes the maximum distance from a collection of (weighted) points in the plane”.","lang":"eng"}],"issue":"1","type":"journal_article","date_published":"1985-01-01T00:00:00Z","article_type":"original","page":"55 - 69","publication":"Theoretical Computer Science","citation":{"chicago":"Edelsbrunner, Herbert. “Finding Transversals for Sets of Simple Geometric-Figures.” Theoretical Computer Science. Elsevier, 1985. https://doi.org/10.1016/0304-3975(85)90005-2.","mla":"Edelsbrunner, Herbert. “Finding Transversals for Sets of Simple Geometric-Figures.” Theoretical Computer Science, vol. 35, no. 1, Elsevier, 1985, pp. 55–69, doi:10.1016/0304-3975(85)90005-2.","short":"H. Edelsbrunner, Theoretical Computer Science 35 (1985) 55–69.","ista":"Edelsbrunner H. 1985. Finding Transversals for Sets of Simple Geometric-Figures. Theoretical Computer Science. 35(1), 55–69.","ieee":"H. Edelsbrunner, “Finding Transversals for Sets of Simple Geometric-Figures,” Theoretical Computer Science, vol. 35, no. 1. Elsevier, pp. 55–69, 1985.","apa":"Edelsbrunner, H. (1985). Finding Transversals for Sets of Simple Geometric-Figures. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(85)90005-2","ama":"Edelsbrunner H. Finding Transversals for Sets of Simple Geometric-Figures. Theoretical Computer Science. 1985;35(1):55-69. doi:10.1016/0304-3975(85)90005-2"},"day":"01","article_processing_charge":"No","scopus_import":"1","date_updated":"2022-01-31T11:09:26Z","date_created":"2018-12-11T12:07:02Z","volume":35,"author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"}],"publication_status":"published","publisher":"Elsevier","acknowledgement":"The author gratefully acknowledges the criticism of an anonymous referee who discovered a serious flaw in an earlier version of this paper. ","year":"1985","extern":"1","publist_id":"2008","language":[{"iso":"eng"}],"doi":"10.1016/0304-3975(85)90005-2","quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"https://www.sciencedirect.com/science/article/pii/0304397585900052?via%3Dihub"}],"month":"01","publication_identifier":{"issn":["0304-3975"],"eissn":["0304-3975"]}},{"publication_identifier":{"issn":["0304-3975"]},"month":"01","language":[{"iso":"eng"}],"doi":"10.1016/0304-3975(81)90103-1","quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"https://www.sciencedirect.com/science/article/pii/0304397581901031"}],"extern":"1","publist_id":"1989","volume":16,"date_updated":"2021-12-16T09:03:47Z","date_created":"2018-12-11T12:07:08Z","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Maurer, Hermann","last_name":"Maurer","first_name":"Hermann"}],"publisher":"Elsevier","publication_status":"published","year":"1981","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"1981-01-01T00:00:00Z","page":"329 - 336","article_type":"original","citation":{"short":"H. Edelsbrunner, H. Maurer, Theoretical Computer Science 16 (1981) 329–336.","mla":"Edelsbrunner, Herbert, and Hermann Maurer. “A Space-Optimal Solution of General Region Location.” Theoretical Computer Science, vol. 16, no. 3, Elsevier, 1981, pp. 329–36, doi:10.1016/0304-3975(81)90103-1.","chicago":"Edelsbrunner, Herbert, and Hermann Maurer. “A Space-Optimal Solution of General Region Location.” Theoretical Computer Science. Elsevier, 1981. https://doi.org/10.1016/0304-3975(81)90103-1.","ama":"Edelsbrunner H, Maurer H. A space-optimal solution of general region location. Theoretical Computer Science. 1981;16(3):329-336. doi:10.1016/0304-3975(81)90103-1","apa":"Edelsbrunner, H., & Maurer, H. (1981). A space-optimal solution of general region location. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(81)90103-1","ieee":"H. Edelsbrunner and H. Maurer, “A space-optimal solution of general region location,” Theoretical Computer Science, vol. 16, no. 3. Elsevier, pp. 329–336, 1981.","ista":"Edelsbrunner H, Maurer H. 1981. A space-optimal solution of general region location. Theoretical Computer Science. 16(3), 329–336."},"publication":"Theoretical Computer Science","issue":"3","abstract":[{"lang":"eng","text":"In 1979 Kirpatrick obtained a practically feasible algorithm for planar regionlocation working in linear space and logarithmic time, provided the regions are bounded by straight line segments. No algorithm requiring only linear space and log-polynomial time was known, so far, for general planar regionlocation, i.e. for the case where regions are bounded by curves more complicated than straight line segments. As main result of this paper such an algorithm is presented."}],"type":"journal_article","oa_version":"Published Version","intvolume":" 16","status":"public","title":"A space-optimal solution of general region location","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","_id":"4133"}]