{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,26]],"date-time":"2026-01-26T14:00:28Z","timestamp":1769436028009,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T00:00:00Z","timestamp":1659398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,8,2]]},"DOI":"10.1145\/3531130.3532399","type":"proceedings-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T20:23:38Z","timestamp":1659644618000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Computing the Density of the Positivity Set for Linear Recurrence Sequences"],"prefix":"10.1145","author":[{"given":"Edon","family":"Kelmendi","sequence":"first","affiliation":[{"name":"Max Planck Institute for Software Systems, Germany"}]}],"member":"320","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434329"},{"key":"e_1_3_2_1_2_1","volume-title":"Periods and the conjectures of Grothendieck and Kontsevich-Zagier","author":"Ayoub Joseph","year":"2014","unstructured":"Joseph Ayoub . 2014. Periods and the conjectures of Grothendieck and Kontsevich-Zagier . European Mathematical Society . Newsletter91 ( 2014 ), 12\u201318. Joseph Ayoub. 2014. Periods and the conjectures of Grothendieck and Kontsevich-Zagier. European Mathematical Society. Newsletter91 (2014), 12\u201318."},{"key":"#cr-split#-e_1_3_2_1_3_1.1","doi-asserted-by":"crossref","unstructured":"Saugata Basu Richard Pollack and Marie-Francois Roy. 2006. Real Roots. Springer Berlin Heidelberg 351-401. https:\/\/doi.org\/10.1007\/3-540-33099-2_11 10.1007\/3-540-33099-2_11","DOI":"10.1007\/3-540-33099-2_11"},{"key":"#cr-split#-e_1_3_2_1_3_1.2","doi-asserted-by":"crossref","unstructured":"Saugata Basu Richard Pollack and Marie-Francois Roy. 2006. Real Roots. Springer Berlin Heidelberg 351-401. https:\/\/doi.org\/10.1007\/3-540-33099-2_11","DOI":"10.1007\/3-540-33099-2_11"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-006-0015-1"},{"key":"e_1_3_2_1_5_1","volume-title":"Deux propri\u00e9t\u00e9s d\u00e9cidables Des Suites r\u00e9currentes lin\u00e9aires. Bulletin de la Societe mathematique de France 79","author":"Berstel Jean","year":"1976","unstructured":"Jean Berstel and Maurice Mignotte . 1976. Deux propri\u00e9t\u00e9s d\u00e9cidables Des Suites r\u00e9currentes lin\u00e9aires. Bulletin de la Societe mathematique de France 79 ( 1976 ), 175\u2013184. https:\/\/doi.org\/10.24033\/bsmf.1823 10.24033\/bsmf.1823 Jean Berstel and Maurice Mignotte. 1976. Deux propri\u00e9t\u00e9s d\u00e9cidables Des Suites r\u00e9currentes lin\u00e9aires. Bulletin de la Societe mathematique de France 79 (1976), 175\u2013184. https:\/\/doi.org\/10.24033\/bsmf.1823"},{"key":"e_1_3_2_1_6_1","volume-title":"Probability and measure","author":"Billingsley Patrick","unstructured":"Patrick Billingsley . 2008. Probability and measure . John Wiley & Sons . Patrick Billingsley. 2008. Probability and measure. John Wiley & Sons."},{"key":"e_1_3_2_1_7_1","volume-title":"Blondel and Natacha Portier","author":"D.","year":"2002","unstructured":"Vincent\u00a0 D. Blondel and Natacha Portier . 2002 . The Presence of a Zero in an Integer Linear Recurrent Sequence Is Np-Hard To Decide. Linear Algebra Appl . 351-352 (2002), 91\u201398. https:\/\/doi.org\/10.1016\/s0024-3795(01)00466-9 10.1016\/s0024-3795(01)00466-9 Vincent\u00a0D. Blondel and Natacha Portier. 2002. The Presence of a Zero in an Integer Linear Recurrent Sequence Is Np-Hard To Decide. Linear Algebra Appl. 351-352 (2002), 91\u201398. https:\/\/doi.org\/10.1016\/s0024-3795(01)00466-9"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_3_2_1_9_1","volume-title":"An Introduction To Diophantine Approximation","author":"Cassels S.","unstructured":"J.\u00a0W.\u00a0 S. Cassels . 1959. An Introduction To Diophantine Approximation . Cambridge University Press . J.\u00a0W.\u00a0S. Cassels. 1959. An Introduction To Diophantine Approximation. Cambridge University Press."},{"key":"e_1_3_2_1_10_1","volume-title":"Igor Shparlinski","author":"Everest Graham","year":"2003","unstructured":"Graham Everest , Alfred\u00a0Jacobus Van Der\u00a0Poorten , Igor Shparlinski , Thomas Ward, 2003 . Recurrence sequences. Vol.\u00a0104. American Mathematical Society Providence , RI. Graham Everest, Alfred\u00a0Jacobus Van Der\u00a0Poorten, Igor Shparlinski, Thomas Ward, 2003. Recurrence sequences. Vol.\u00a0104. American Mathematical Society Providence, RI."},{"key":"e_1_3_2_1_11_1","volume-title":"On the Growth of Linear Recurrences in Function Fields. CoRR","author":"Fuchs Clemens","year":"2020","unstructured":"Clemens Fuchs and Sebastian Heintze . 2020. On the Growth of Linear Recurrences in Function Fields. CoRR ( 2020 ). arxiv:2006.11074\u00a0[math.NT] http:\/\/arxiv.org\/abs\/2006.11074v1 Clemens Fuchs and Sebastian Heintze. 2020. On the Growth of Linear Recurrences in Function Fields. CoRR (2020). arxiv:2006.11074\u00a0[math.NT] http:\/\/arxiv.org\/abs\/2006.11074v1"},{"key":"e_1_3_2_1_13_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Hansel Georges","unstructured":"Georges Hansel . 1985. A simple proof of the Skolem-Mahler-Lech theorem . In International Colloquium on Automata, Languages, and Programming . Springer , 244\u2013249. Georges Hansel. 1985. A simple proof of the Skolem-Mahler-Lech theorem. In International Colloquium on Automata, Languages, and Programming. Springer, 244\u2013249."},{"key":"e_1_3_2_1_14_1","unstructured":"Annette Huber and Gisbert W\u00fcstholz. 2018. Transcendence and linear relations of 1-periods. arXiv preprint arXiv:1805.10104(2018).  Annette Huber and Gisbert W\u00fcstholz. 2018. Transcendence and linear relations of 1-periods. arXiv preprint arXiv:1805.10104(2018)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492470"},{"key":"#cr-split#-e_1_3_2_1_16_1.1","doi-asserted-by":"crossref","unstructured":"Maxim Kontsevich and Don Zagier. 2001. Periods. Springer Berlin Heidelberg 771-808. https:\/\/doi.org\/10.1007\/978-3-642-56478-9_39 10.1007\/978-3-642-56478-9_39","DOI":"10.1007\/978-3-642-56478-9_39"},{"key":"#cr-split#-e_1_3_2_1_16_1.2","doi-asserted-by":"crossref","unstructured":"Maxim Kontsevich and Don Zagier. 2001. Periods. Springer Berlin Heidelberg 771-808. https:\/\/doi.org\/10.1007\/978-3-642-56478-9_39","DOI":"10.1007\/978-3-642-56478-9_39"},{"key":"#cr-split#-e_1_3_2_1_17_1.1","doi-asserted-by":"crossref","unstructured":"Serge Lang. 2002. Algebra. Springer New York. https:\/\/doi.org\/10.1007\/978-1-4613-0041-0 10.1007\/978-1-4613-0041-0","DOI":"10.1007\/978-1-4613-0041-0"},{"key":"#cr-split#-e_1_3_2_1_17_1.2","doi-asserted-by":"crossref","unstructured":"Serge Lang. 2002. Algebra. Springer New York. https:\/\/doi.org\/10.1007\/978-1-4613-0041-0","DOI":"10.1007\/978-1-4613-0041-0"},{"key":"e_1_3_2_1_18_1","volume-title":"A note on recurring series. Arkiv f\u00f6r Matematik 2, 5","author":"Lech Christer","year":"1953","unstructured":"Christer Lech . 1953. A note on recurring series. Arkiv f\u00f6r Matematik 2, 5 ( 1953 ), 417\u2013421. Christer Lech. 1953. A note on recurring series. Arkiv f\u00f6r Matematik 2, 5 (1953), 417\u2013421."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.2307\/2301023"},{"key":"e_1_3_2_1_20_1","unstructured":"Kurt Mahler. 1935. Eine arithmetische Eigenschaft der Taylor-koeffizienten rationaler Funktionen. Noord-Hollandsche Uitgevers Mij.  Kurt Mahler. 1935. Eine arithmetische Eigenschaft der Taylor-koeffizienten rationaler Funktionen. Noord-Hollandsche Uitgevers Mij."},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. https:\/\/doi.org\/10","author":"Ouaknine Jo\u00ebl","year":"2013","unstructured":"Jo\u00ebl Ouaknine and James Worrell . 2013 . Positivity Problems for Low-Order Linear Recurrence Sequences . In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. https:\/\/doi.org\/10 .1137\/1.9781611973402.27 10.1137\/1.9781611973402.27 Jo\u00ebl Ouaknine and James Worrell. 2013. Positivity Problems for Low-Order Linear Recurrence Sequences. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. https:\/\/doi.org\/10.1137\/1.9781611973402.27"},{"key":"e_1_3_2_1_22_1","volume-title":"Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences","author":"Ouaknine Jo\u00ebl","unstructured":"Jo\u00ebl Ouaknine and James Worrell . 2014. Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences . Springer Science + Business Media, 330\u2013341. https:\/\/doi.org\/10.1007\/978-3-662-43951-7_28 10.1007\/978-3-662-43951-7_28 Jo\u00ebl Ouaknine and James Worrell. 2014. Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences. Springer Science + Business Media, 330\u2013341. https:\/\/doi.org\/10.1007\/978-3-662-43951-7_28"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"e_1_3_2_1_24_1","unstructured":"Thoralf Skolem. 1934. Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen und diophantischer Gleichungen. C. r 8(1934) 163\u2013188.  Thoralf Skolem. 1934. Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen und diophantischer Gleichungen. C. r 8(1934) 163\u2013188."},{"key":"e_1_3_2_1_25_1","volume-title":"Calculus On Manifolds","author":"Spivak Michael","year":"1906","unstructured":"Michael Spivak . 2018. Calculus On Manifolds . CRC Press . https:\/\/doi.org\/10.1201\/978042950 1906 10.1201\/9780429501906 Michael Spivak. 2018. Calculus On Manifolds. CRC Press. https:\/\/doi.org\/10.1201\/9780429501906"},{"key":"e_1_3_2_1_26_1","volume-title":"A decision method for elementary algebra and geometry","author":"Tarski Alfred","unstructured":"Alfred Tarski . 1951. A decision method for elementary algebra and geometry . University of California Press. Alfred Tarski. 1951. A decision method for elementary algebra and geometry. University of California Press."},{"key":"#cr-split#-e_1_3_2_1_27_1.1","doi-asserted-by":"crossref","unstructured":"R. Tijdeman M. Mignotte and T.N. Shorey. 1984. The Distance Between Terms of an Algebraic Recurrence Sequence.Journal f\u00fcr die reine und angewandte Mathematik (Crelles Journal) 1984 349(1984) 63-76. https:\/\/doi.org\/10.1515\/crll.1984.349.63 10.1515\/crll.1984.349.63","DOI":"10.1515\/crll.1984.349.63"},{"key":"#cr-split#-e_1_3_2_1_27_1.2","doi-asserted-by":"crossref","unstructured":"R. Tijdeman M. Mignotte and T.N. Shorey. 1984. The Distance Between Terms of an Algebraic Recurrence Sequence.Journal f\u00fcr die reine und angewandte Mathematik (Crelles Journal) 1984 349(1984) 63-76. https:\/\/doi.org\/10.1515\/crll.1984.349.63","DOI":"10.1515\/crll.1984.349.63"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972700023042"},{"key":"#cr-split#-e_1_3_2_1_29_1.1","doi-asserted-by":"crossref","unstructured":"N.\u00a0K. Vereshchagin. 1985. Occurrence of zero in a linear recursive sequence. Mathematical notes of the Academy of Sciences of the USSR 38 2(1985) 609-615. https:\/\/doi.org\/10.1007\/BF01156238 10.1007\/BF01156238","DOI":"10.1007\/BF01156238"},{"key":"#cr-split#-e_1_3_2_1_29_1.2","doi-asserted-by":"crossref","unstructured":"N.\u00a0K. Vereshchagin. 1985. Occurrence of zero in a linear recursive sequence. Mathematical notes of the Academy of Sciences of the USSR 38 2(1985) 609-615. https:\/\/doi.org\/10.1007\/BF01156238","DOI":"10.1007\/BF01156238"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-11569-5"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC \u201911","author":"K.","year":"1993","unstructured":"Chee\u00a0 K. Yap and Michael Sagraloff. 2011. A simple but exact and efficient algorithm for complex root isolation . In Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC \u201911 . https:\/\/doi.org\/10.1145\/ 1993 886.1993938 10.1145\/1993886.1993938 Chee\u00a0K. Yap and Michael Sagraloff. 2011. A simple but exact and efficient algorithm for complex root isolation. In Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC \u201911. https:\/\/doi.org\/10.1145\/1993886.1993938"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/220346.220357"}],"event":{"name":"LICS '22: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Haifa Israel","acronym":"LICS '22","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation"]},"container-title":["Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3532399","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531130.3532399","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:09Z","timestamp":1750186929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3532399"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,2]]},"references-count":36,"alternative-id":["10.1145\/3531130.3532399","10.1145\/3531130"],"URL":"https:\/\/doi.org\/10.1145\/3531130.3532399","relation":{},"subject":[],"published":{"date-parts":[[2022,8,2]]},"assertion":[{"value":"2022-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}