[{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"corr_author":"1","article_processing_charge":"Yes","related_material":{"record":[{"relation":"later_version","status":"public","id":"17330"}]},"acknowledgement":"Nicolas Resch: Research supported in part by ERC H2020 grant No.74079 (ALGSTRONGCRYPTO). Chen Yuan: Research supported in part by the National Key Research and Development Projects under Grant 2022YFA1004900 and Grant 2021YFE0109900, the National Natural Science Foundation of China under Grant 12101403 and Grant 12031011.\r\nAcknowledgements YZ is grateful to Shashank Vatedka, Diyuan Wu and Fengxing Zhu for inspiring discussions.","oa":1,"doi":"10.4230/LIPIcs.ICALP.2023.99","month":"07","department":[{"_id":"MaMo"}],"volume":261,"author":[{"first_name":"Nicolas","full_name":"Resch, Nicolas","last_name":"Resch"},{"last_name":"Yuan","full_name":"Yuan, Chen","first_name":"Chen"},{"orcid":"0000-0002-6465-6258","first_name":"Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan","last_name":"Zhang"}],"arxiv":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772785"]},"oa_version":"Published Version","alternative_title":["LIPIcs"],"title":"Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery","date_created":"2023-08-20T22:01:13Z","publication_status":"published","conference":{"location":"Paderborn, Germany","end_date":"2023-07-14","start_date":"2023-07-10","name":"ICALP: Automata, Languages and Programming"},"file":[{"file_size":1141497,"date_created":"2023-08-21T07:23:18Z","content_type":"application/pdf","success":1,"access_level":"open_access","creator":"dernst","relation":"main_file","date_updated":"2023-08-21T07:23:18Z","file_id":"14091","file_name":"2023_LIPIcsICALP_Resch.pdf","checksum":"a449143fec3fbebb092cb8ef3b53c226"}],"status":"public","scopus_import":"1","file_date_updated":"2023-08-21T07:23:18Z","date_updated":"2025-09-08T08:31:53Z","publication":"50th International Colloquium on Automata, Languages, and Programming","year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"intvolume":"       261","article_number":"99","date_published":"2023-07-01T00:00:00Z","type":"conference","quality_controlled":"1","_id":"14083","language":[{"iso":"eng"}],"abstract":[{"text":"In this work we consider the list-decodability and list-recoverability of arbitrary q-ary codes, for all integer values of q ≥ 2. A code is called (p,L)_q-list-decodable if every radius pn Hamming ball contains less than L codewords; (p,𝓁,L)_q-list-recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length 𝓁 and again stipulate that there be less than L codewords.\r\nOur main contribution is to precisely calculate the maximum value of p for which there exist infinite families of positive rate (p,𝓁,L)_q-list-recoverable codes, the quantity we call the zero-rate threshold. Denoting this value by p_*, we in fact show that codes correcting a p_*+ε fraction of errors must have size O_ε(1), i.e., independent of n. Such a result is typically referred to as a \"Plotkin bound.\" To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a p_*-ε fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery.\r\nTechnically, proving the Plotkin bound boils down to demonstrating the Schur convexity of a certain function defined on the q-simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for q-ary list-decoding; however, we point out that this earlier proof is flawed.","lang":"eng"}],"external_id":{"arxiv":["2210.07754"]},"has_accepted_license":"1","citation":{"apa":"Resch, N., Yuan, C., &#38; Zhang, Y. (2023). Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.99\">https://doi.org/10.4230/LIPIcs.ICALP.2023.99</a>","mla":"Resch, Nicolas, et al. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.99\">10.4230/LIPIcs.ICALP.2023.99</a>.","short":"N. Resch, C. Yuan, Y. Zhang, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"N. Resch, C. Yuan, and Y. Zhang, “Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.","chicago":"Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.99\">https://doi.org/10.4230/LIPIcs.ICALP.2023.99</a>.","ama":"Resch N, Yuan C, Zhang Y. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.99\">10.4230/LIPIcs.ICALP.2023.99</a>","ista":"Resch N, Yuan C, Zhang Y. 2023. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 99."},"day":"01"},{"file":[{"access_level":"open_access","content_type":"application/pdf","success":1,"date_created":"2023-08-21T06:45:16Z","file_size":917791,"checksum":"6dee0684245bb1c524b9c955db1e933d","file_name":"2023_LIPIcsICALP_Harris.pdf","date_updated":"2023-08-21T06:45:16Z","file_id":"14088","creator":"dernst","relation":"main_file"}],"publication_status":"published","conference":{"start_date":"2023-07-10","name":"ICALP: Automata, Languages and Programming","location":"Paderborn, Germany","end_date":"2023-07-14"},"date_created":"2023-08-20T22:01:14Z","alternative_title":["LIPIcs"],"title":"Parameter estimation for Gibbs distributions","oa_version":"Published Version","arxiv":1,"publication_identifier":{"isbn":["9783959772785"],"issn":["1868-8969"]},"author":[{"last_name":"Harris","full_name":"Harris, David G.","first_name":"David G."},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"volume":261,"month":"07","department":[{"_id":"VlKo"}],"acknowledgement":"We thank Heng Guo for helpful explanations of algorithms for sampling connected subgraphs and matchings, Maksym Serbyn for bringing to our attention the Wang-Landau algorithm and its use in physics.","oa":1,"doi":"10.4230/LIPIcs.ICALP.2023.72","related_material":{"record":[{"id":"18855","status":"public","relation":"later_version"}]},"corr_author":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_processing_charge":"Yes","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","has_accepted_license":"1","citation":{"ama":"Harris DG, Kolmogorov V. Parameter estimation for Gibbs distributions. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.72\">10.4230/LIPIcs.ICALP.2023.72</a>","ista":"Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 72.","chicago":"Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.72\">https://doi.org/10.4230/LIPIcs.ICALP.2023.72</a>.","mla":"Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.72\">10.4230/LIPIcs.ICALP.2023.72</a>.","short":"D.G. Harris, V. Kolmogorov, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"D. G. Harris and V. Kolmogorov, “Parameter estimation for Gibbs distributions,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.","apa":"Harris, D. G., &#38; Kolmogorov, V. (2023). Parameter estimation for Gibbs distributions. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.72\">https://doi.org/10.4230/LIPIcs.ICALP.2023.72</a>"},"day":"01","language":[{"iso":"eng"}],"_id":"14084","abstract":[{"text":"A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We will consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n].\r\nThe partition function is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log Z(β_max))/Z(β_min)\r\nWe develop a number of algorithms to estimate the counts c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²) samples for integer-valued distributions (ignoring some second-order terms and parameters), We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph.","lang":"eng"}],"external_id":{"arxiv":["2007.10824"]},"type":"conference","quality_controlled":"1","date_published":"2023-07-01T00:00:00Z","article_number":"72","intvolume":"       261","year":"2023","ddc":["000","510"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"50th International Colloquium on Automata, Languages, and Programming","date_updated":"2025-07-10T11:50:45Z","file_date_updated":"2023-08-21T06:45:16Z","scopus_import":"1","status":"public"},{"ec_funded":1,"scopus_import":"1","status":"public","date_updated":"2025-06-04T07:19:37Z","publication":"50th International Colloquium on Automata, Languages, and Programming","file_date_updated":"2023-08-21T06:59:05Z","date_published":"2023-07-01T00:00:00Z","intvolume":"       261","article_number":"69","year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"has_accepted_license":"1","citation":{"chicago":"Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">https://doi.org/10.4230/LIPIcs.ICALP.2023.69</a>.","ama":"Goranci G, Henzinger M. Efficient data structures for incremental exact and approximate maximum flow. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">10.4230/LIPIcs.ICALP.2023.69</a>","ista":"Goranci G, Henzinger M. 2023. Efficient data structures for incremental exact and approximate maximum flow. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 69.","apa":"Goranci, G., &#38; Henzinger, M. (2023). Efficient data structures for incremental exact and approximate maximum flow. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">https://doi.org/10.4230/LIPIcs.ICALP.2023.69</a>","mla":"Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">10.4230/LIPIcs.ICALP.2023.69</a>.","short":"G. Goranci, M. Henzinger, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"G. Goranci and M. Henzinger, “Efficient data structures for incremental exact and approximate maximum flow,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261."},"day":"01","_id":"14085","abstract":[{"text":"We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m1/2+o(1)ϵ−1/2 amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee.","lang":"eng"}],"language":[{"iso":"eng"}],"external_id":{"arxiv":["2211.09606"]},"type":"conference","quality_controlled":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"corr_author":"1","article_processing_charge":"Yes","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":261,"author":[{"last_name":"Goranci","full_name":"Goranci, Gramoz","first_name":"Gramoz"},{"last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"}],"project":[{"call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"department":[{"_id":"MoHe"}],"month":"07","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.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the\r\nAustrian Science Fund (FWF) project “Static and Dynamic Hierarchical Graph Decompositions”,\r\nI 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nThis work was done in part while Gramoz Goranci was at Institute for Theoretical Studies, ETH Zurich, Switzerland. There, he was supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation. We also thank Richard Peng, Thatchaphol Saranurak, Sebastian Forster and Sushant Sachdeva for helpful discussions, and the anonymous reviewers for their insightful comments.","doi":"10.4230/LIPIcs.ICALP.2023.69","oa":1,"title":"Efficient data structures for incremental exact and approximate maximum flow","alternative_title":["LIPIcs"],"date_created":"2023-08-20T22:01:14Z","oa_version":"Published Version","arxiv":1,"publication_identifier":{"isbn":["9783959772785"],"issn":["1868-8969"]},"file":[{"access_level":"open_access","success":1,"content_type":"application/pdf","file_size":875910,"date_created":"2023-08-21T06:59:05Z","checksum":"074177e815a1656de5d4071c7a3dffa6","file_name":"2023_LIPIcsICALP_Goranci.pdf","file_id":"14089","creator":"dernst","date_updated":"2023-08-21T06:59:05Z","relation":"main_file"}],"conference":{"start_date":"2023-07-10","name":"ICALP: Automata, Languages and Programming","location":"Paderborn, Germany","end_date":"2023-07-14"},"publication_status":"published"},{"status":"public","ec_funded":1,"scopus_import":"1","file_date_updated":"2023-08-21T07:04:36Z","publication":"50th International Colloquium on Automata, Languages, and Programming","date_updated":"2025-07-10T11:50:45Z","article_number":"74","intvolume":"       261","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2023","date_published":"2023-07-01T00:00:00Z","external_id":{"arxiv":["2305.00122"]},"language":[{"iso":"eng"}],"_id":"14086","abstract":[{"lang":"eng","text":"The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been investigated extensively due to its algorithmic properties and expressive power. Though tight approximation algorithms for general matroid constraints exist in theory, the running times of such algorithms typically scale quadratically, and are not practical for truly large scale settings. Recent progress has focused on fast algorithms for important classes of matroids given in explicit form. Currently, nearly-linear time algorithms only exist for graphic and partition matroids [Alina Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone submodular maximization constrained by graphic, transversal matroids, or laminar matroids in time near-linear in the size of their representation. Our algorithms achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the running time of our algorithm cannot be improved within the fast continuous greedy framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák, 2014].\r\nTo achieve near-linear running time, we make use of dynamic data structures that maintain bases with approximate maximum cardinality and weight under certain element updates. These data structures need to support a weight decrease operation and a novel Freeze operation that allows the algorithm to freeze elements (i.e. force to be contained) in its basis regardless of future data structure operations. For the laminar matroid, we present a new dynamic data structure using the top tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et al., 2005] that maintains the maximum weight basis under insertions and deletions of elements in O(log n) time. This data structure needs to support certain subtree query and path update operations that are performed every insertion and deletion that are non-trivial to handle in conjunction. For the transversal matroid the Freeze operation corresponds to requiring the data structure to keep a certain set S of vertices matched, a property that we call S-stability. While there is a large body of work on dynamic matching algorithms, none are S-stable and maintain an approximate maximum weight matching under vertex updates. We give the first such algorithm for bipartite graphs with total running time linear (up to log factors) in the number of edges."}],"quality_controlled":"1","type":"conference","citation":{"mla":"Henzinger, Monika, et al. “Faster Submodular Maximization for Several Classes of Matroids.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">10.4230/LIPIcs.ICALP.2023.74</a>.","ieee":"M. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization for several classes of matroids,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.","short":"M. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","apa":"Henzinger, M., Liu, P., Vondrák, J., &#38; Zheng, D. W. (2023). Faster submodular maximization for several classes of matroids. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">https://doi.org/10.4230/LIPIcs.ICALP.2023.74</a>","ama":"Henzinger M, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for several classes of matroids. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">10.4230/LIPIcs.ICALP.2023.74</a>","ista":"Henzinger M, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization for several classes of matroids. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 74.","chicago":"Henzinger, Monika, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular Maximization for Several Classes of Matroids.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">https://doi.org/10.4230/LIPIcs.ICALP.2023.74</a>."},"day":"01","has_accepted_license":"1","article_processing_charge":"Yes","corr_author":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.ICALP.2023.74","oa":1,"acknowledgement":" Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project “Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. Jan Vondrák: Supported by NSF Award 2127781.","volume":261,"author":[{"last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Paul","full_name":"Liu, Paul","last_name":"Liu"},{"first_name":"Jan","full_name":"Vondrák, Jan","last_name":"Vondrák"},{"first_name":"Da Wei","full_name":"Zheng, Da Wei","last_name":"Zheng"}],"month":"07","department":[{"_id":"MoHe"}],"project":[{"name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"publication_identifier":{"isbn":["9783959772785"],"issn":["1868-8969"]},"arxiv":1,"title":"Faster submodular maximization for several classes of matroids","date_created":"2023-08-20T22:01:14Z","alternative_title":["LIPIcs"],"oa_version":"Published Version","conference":{"name":"ICALP: Automata, Languages and Programming","start_date":"2023-07-10","end_date":"2023-07-14","location":"Paderborn, Germany"},"publication_status":"published","file":[{"relation":"main_file","creator":"dernst","date_updated":"2023-08-21T07:04:36Z","file_id":"14090","checksum":"a5eef225014e003efbfbe4830fdd23cb","file_name":"2023_LIPIcsICALP_HenzingerM.pdf","content_type":"application/pdf","success":1,"date_created":"2023-08-21T07:04:36Z","file_size":930943,"access_level":"open_access"}]},{"alternative_title":["LIPIcs"],"title":"Regular methods for operator precedence languages","date_created":"2023-07-24T15:11:41Z","oa_version":"Published Version","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959772785"]},"arxiv":1,"file":[{"content_type":"application/pdf","success":1,"file_size":859379,"date_created":"2023-07-24T15:11:05Z","access_level":"open_access","date_updated":"2023-07-24T15:11:05Z","creator":"esarac","file_id":"13293","relation":"main_file","checksum":"5d4c8932ef3450615a53b9bb15d92eb2","file_name":"icalp23.pdf"}],"publication_status":"published","conference":{"name":"ICALP: Automata, Languages and Programming","start_date":"2023-07-10","end_date":"2023-07-14","location":"Paderborn, Germany"},"corr_author":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_processing_charge":"Yes","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":261,"author":[{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724","last_name":"Henzinger","full_name":"Henzinger, Thomas A"},{"first_name":"Pavol","last_name":"Kebis","full_name":"Kebis, Pavol"},{"first_name":"Nicolas Adrien","id":"b26baa86-3308-11ec-87b0-8990f34baa85","last_name":"Mazzocchi","full_name":"Mazzocchi, Nicolas Adrien"},{"id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425","first_name":"Naci E","last_name":"Sarac","full_name":"Sarac, Naci E"}],"project":[{"name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020"}],"department":[{"_id":"GradSch"},{"_id":"ToHe"}],"month":"07","acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093.\r\nWe thank Pierre Ganty for early discussions and the anonymous reviewers for their helpful comments.\r\n","oa":1,"doi":"10.4230/LIPIcs.ICALP.2023.129","date_published":"2023-07-05T00:00:00Z","intvolume":"       261","year":"2023","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","citation":{"apa":"Henzinger, T. A., Kebis, P., Mazzocchi, N. A., &#38; Sarac, N. E. (2023). Regular methods for operator precedence languages. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261, p. 129:1--129:20). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">https://doi.org/10.4230/LIPIcs.ICALP.2023.129</a>","mla":"Henzinger, Thomas A., et al. “Regular Methods for Operator Precedence Languages.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, p. 129:1--129:20, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">10.4230/LIPIcs.ICALP.2023.129</a>.","ieee":"T. A. Henzinger, P. Kebis, N. A. Mazzocchi, and N. E. Sarac, “Regular methods for operator precedence languages,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261, p. 129:1--129:20.","short":"T.A. Henzinger, P. Kebis, N.A. Mazzocchi, N.E. Sarac, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, p. 129:1--129:20.","chicago":"Henzinger, Thomas A, Pavol Kebis, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Regular Methods for Operator Precedence Languages.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, 261:129:1--129:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">https://doi.org/10.4230/LIPIcs.ICALP.2023.129</a>.","ama":"Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. Regular methods for operator precedence languages. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023:129:1--129:20. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">10.4230/LIPIcs.ICALP.2023.129</a>","ista":"Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. 2023. Regular methods for operator precedence languages. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 129:1--129:20."},"day":"05","_id":"13292","abstract":[{"lang":"eng","text":"The operator precedence languages (OPLs) represent the largest known subclass of the context-free languages which enjoys all desirable closure and decidability properties. This includes the decidability of language inclusion, which is the ultimate verification problem. Operator precedence grammars, automata, and logics have been investigated and used, for example, to verify programs with arithmetic expressions and exceptions (both of which are deterministic pushdown but lie outside the scope of the visibly pushdown languages). In this paper, we complete the picture and give, for the first time, an algebraic characterization of the class of OPLs in the form of a syntactic congruence that has finitely many equivalence classes exactly for the operator precedence languages. This is a generalization of the celebrated Myhill-Nerode theorem for the regular languages to OPLs. As one of the consequences, we show that universality and language inclusion for nondeterministic operator precedence automata can be solved by an antichain algorithm. Antichain algorithms avoid determinization and complementation through an explicit subset construction, by leveraging a quasi-order on words, which allows the pruning of the search space for counterexample words without sacrificing completeness. Antichain algorithms can be implemented symbolically, and these implementations are today the best-performing algorithms in practice for the inclusion of finite automata. We give a generic construction of the quasi-order needed for antichain algorithms from a finite syntactic congruence. This yields the first antichain algorithm for OPLs, an algorithm that solves the ExpTime-hard language inclusion problem for OPLs in exponential time."}],"language":[{"iso":"eng"}],"external_id":{"arxiv":["2305.03447"]},"type":"conference","quality_controlled":"1","ec_funded":1,"scopus_import":"1","status":"public","page":"129:1--129:20","date_updated":"2025-07-10T11:50:41Z","publication":"50th International Colloquium on Automata, Languages, and Programming","file_date_updated":"2023-07-24T15:11:05Z"}]