{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T07:45:45Z","timestamp":1790754345984,"version":"4.1.0"},"publisher-location":"New York, NY, USA","reference-count":31,"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:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DFG","award":["389792660"],"award-info":[{"award-number":["389792660"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,8,2]]},"DOI":"10.1145\/3531130.3533328","type":"proceedings-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T20:23:38Z","timestamp":1659644618000},"page":"1-9","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["On the Skolem Problem and the Skolem Conjecture"],"prefix":"10.1145","author":[{"given":"Richard","family":"Lipton","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florian","family":"Luca","sequence":"additional","affiliation":[{"name":"Wits, South Africa"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joris","family":"Nieuwveld","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Software Systems, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jo\u00ebl","family":"Ouaknine","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Software Systems (MPI-SWS), Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Purser","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Software Systems, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Worrell","sequence":"additional","affiliation":[{"name":"University of Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"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\/2629417"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.08.013"},{"key":"e_1_3_2_1_3_1","volume-title":"Proc. ACM Program. Lang. 5, POPL","author":"Almagor S.","year":"2021","unstructured":"S. Almagor , T. Karimov , E. Kelmendi , J. Ouaknine , and J. Worrell . 2021. Deciding \u03c9-regular properties on linear recurrence sequences . Proc. ACM Program. Lang. 5, POPL ( 2021 ). S. Almagor, T. Karimov, E. Kelmendi, J. Ouaknine, and J. Worrell. 2021. Deciding \u03c9-regular properties on linear recurrence sequences. Proc. ACM Program. Lang. 5, POPL (2021)."},{"key":"e_1_3_2_1_4_1","volume-title":"The Orbit Problem for Parametric Linear Dynamical Systems. In 32nd International Conference on Concurrency Theory, CONCUR 2021, August 24-27, 2021, Virtual Conference(LIPIcs, Vol.\u00a0203)","author":"Baier C.","unstructured":"C. Baier , F. Funke , S. Jantsch , T. Karimov , E. Lefaucheux , F. Luca , J. Ouaknine , D. Purser , M.\u00a0 A. Whiteland , and J. Worrell . 2021 . The Orbit Problem for Parametric Linear Dynamical Systems. In 32nd International Conference on Concurrency Theory, CONCUR 2021, August 24-27, 2021, Virtual Conference(LIPIcs, Vol.\u00a0203) , Serge Haddad and Daniele Varacca (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 28:1\u201328:17. C. Baier, F. Funke, S. Jantsch, T. Karimov, E. Lefaucheux, F. Luca, J. Ouaknine, D. Purser, M.\u00a0A. Whiteland, and J. Worrell. 2021. The Orbit Problem for Parametric Linear Dynamical Systems. In 32nd International Conference on Concurrency Theory, CONCUR 2021, August 24-27, 2021, Virtual Conference(LIPIcs, Vol.\u00a0203), Serge Haddad and Daniele Varacca (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 28:1\u201328:17."},{"key":"e_1_3_2_1_5_1","volume-title":"A Comprehensive Course in Number Theory","author":"Baker A.","unstructured":"A. Baker . 2012. A Comprehensive Course in Number Theory . Cambridge University Press . A. Baker. 2012. A Comprehensive Course in Number Theory. Cambridge University Press."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394746"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa159-2-1"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"J. Berstel and C. Reutenauer. 2011. Noncommutative Rational Series with Applications. Cambridge University Press.  J. Berstel and C. Reutenauer. 2011. Noncommutative Rational Series with Applications. Cambridge University Press.","DOI":"10.1017\/CBO9780511760860"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3002"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00605-018-1169-8"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(00)00050-9"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"V.\u00a0D. Blondel and N. Portier. 2002. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and Its Applications 351\u2013352 (2002).  V.\u00a0D. Blondel and N. Portier. 2002. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and Its Applications 351\u2013352 (2002).","DOI":"10.1016\/S0024-3795(01)00466-9"},{"key":"e_1_3_2_1_13_1","volume-title":"Stochastic Processes with Expected Stopping Time. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021","author":"Chatterjee K.","year":"2021","unstructured":"K. Chatterjee and L. Doyen . 2021 . Stochastic Processes with Expected Stopping Time. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021 , Rome, Italy, June 29 - July 2, 2021 . IEEE, 1\u201313. K. Chatterjee and L. Doyen. 2021. Stochastic Processes with Expected Stopping Time. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021. IEEE, 1\u201313."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015","author":"Chonev V.","year":"2015","unstructured":"V. Chonev , J. Ouaknine , and J. Worrell . 2015. The Polyhedron-Hitting Problem . In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 , San Diego, CA, USA , January 4-6, 2015 , Piotr Indyk (Ed.). SIAM, 940\u2013956. V. Chonev, J. Ouaknine, and J. Worrell. 2015. The Polyhedron-Hitting Problem. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, Piotr Indyk (Ed.). SIAM, 940\u2013956."},{"key":"e_1_3_2_1_15_1","volume-title":"I. Shparlinski, and T. Ward.","author":"Everest G.","year":"2003","unstructured":"G. Everest , A. van\u00a0der Poorten , I. Shparlinski, and T. Ward. 2003 . Recurrence Sequences. American Mathematical Society . G. Everest, A. van\u00a0der Poorten, I. Shparlinski, and T. Ward. 2003. Recurrence Sequences. American Mathematical Society."},{"key":"e_1_3_2_1_16_1","first-page":"342","article-title":"Sur les s\u00e9ries enti\u00e8res \u00e0 coefficients entiers","volume":"138","author":"Fatou P.","year":"1904","unstructured":"P. Fatou . 1904 . Sur les s\u00e9ries enti\u00e8res \u00e0 coefficients entiers . Comptes Rendus Acad. Sci. Paris 138 , 130 (1904), 342 \u2013 344 . P. Fatou. 1904. Sur les s\u00e9ries enti\u00e8res \u00e0 coefficients entiers. Comptes Rendus Acad. Sci. Paris 138, 130 (1904), 342\u2013344.","journal-title":"Comptes Rendus Acad. Sci. Paris"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2019, Montreal, QC, Canada","author":"Fijalkow N.","year":"2019","unstructured":"N. Fijalkow , J. Ouaknine , A. Pouly , J.\u00a0 Sousa Pinto , and J. Worrell . 2019. On the decidability of reachability in linear time-invariant systems . In Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2019, Montreal, QC, Canada , April 16-18, 2019 , Necmiye Ozay and Pavithra Prabhakar (Eds.). ACM, 77\u201386. N. Fijalkow, J. Ouaknine, A. Pouly, J.\u00a0Sousa Pinto, and J. Worrell. 2019. On the decidability of reachability in linear time-invariant systems. In Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2019, Montreal, QC, Canada, April 16-18, 2019, Necmiye Ozay and Pavithra Prabhakar (Eds.). ACM, 77\u201386."},{"key":"e_1_3_2_1_18_1","volume-title":"p-adic Numbers: An Introduction","author":"Gouvea F.","unstructured":"F. Gouvea . 1997. p-adic Numbers: An Introduction . Springer . F. Gouvea. 1997. p-adic Numbers: An Introduction. Springer."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"T. Karimov E. Lefaucheux J. Ouaknine D. Purser A. Varonka M.\u00a0A. Whiteland and J. Worrell. 2022. What\u2019s decidable about linear loops?Proc. ACM Program. Lang. 6 POPL (2022).  T. Karimov E. Lefaucheux J. Ouaknine D. Purser A. Varonka M.\u00a0A. Whiteland and J. Worrell. 2022. What\u2019s decidable about linear loops?Proc. ACM Program. Lang. 6 POPL (2022).","DOI":"10.1145\/3498727"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1857.53.173"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"M. Mignotte T.\u00a0N. Shorey and R. Tijdeman. 1984. The distance between terms of an algebraic recurrence sequence. Journal f\u00fcr die reine und angewandte Mathematik 349 (1984).  M. Mignotte T.\u00a0N. Shorey and R. Tijdeman. 1984. The distance between terms of an algebraic recurrence sequence. Journal f\u00fcr die reine und angewandte Mathematik 349 (1984).","DOI":"10.1515\/crll.1984.349.63"},{"key":"e_1_3_2_1_22_1","volume-title":"Proc. Intern. Workshop on Reachability Problems (RP)(LNCS, Vol.\u00a07550)","author":"Ouaknine J.","unstructured":"J. Ouaknine and J. Worrell . 2012. Decision Problems for Linear Recurrence Sequences . In Proc. Intern. Workshop on Reachability Problems (RP)(LNCS, Vol.\u00a07550) . Springer. J. Ouaknine and J. Worrell. 2012. Decision Problems for Linear Recurrence Sequences. In Proc. Intern. Workshop on Reachability Problems (RP)(LNCS, Vol.\u00a07550). Springer."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766189.2766191"},{"key":"e_1_3_2_1_24_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference)(LIPIcs, Vol.\u00a0168)","author":"Piribauer J.","unstructured":"J. Piribauer and C. Baier . 2020. On Skolem-Hardness and Saturation Points in Markov Decision Processes. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference)(LIPIcs, Vol.\u00a0168) , Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 138:1\u2013138:17. J. Piribauer and C. Baier. 2020. On Skolem-Hardness and Saturation Points in Markov Decision Processes. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference)(LIPIcs, Vol.\u00a0168), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 138:1\u2013138:17."},{"key":"e_1_3_2_1_25_1","unstructured":"G. Rozenberg and A. Salomaa. 1994. Cornerstones of Undecidability. Prentice Hall.  G. Rozenberg and A. Salomaa. 1994. Cornerstones of Undecidability. Prentice Hall."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa-32-3-245-274"},{"key":"e_1_3_2_1_27_1","first-page":"147","article-title":"On the congruence Math 370 where un is a recurring sequence of the second order","volume":"30","author":"Schinzel A.","year":"2003","unstructured":"A. Schinzel . 2003 . On the congruence Math 370 where un is a recurring sequence of the second order . Acta Acad. Paedagog. Agriensis Sect. Math. 30 (2003), 147 \u2013 165 . A. Schinzel. 2003. On the congruence Math 370 where un is a recurring sequence of the second order. Acta Acad. Paedagog. Agriensis Sect. Math. 30 (2003), 147\u2013165.","journal-title":"Acta Acad. Paedagog. Agriensis Sect. Math."},{"key":"e_1_3_2_1_28_1","first-page":"1","article-title":"Anwendung exponentieller Kongruenzen zum Beweis der Unl\u00f6sbarkeit gewisser diophantischer Gleichungen","author":"Skolem Th.","year":"1937","unstructured":"Th. Skolem . 1937 . Anwendung exponentieller Kongruenzen zum Beweis der Unl\u00f6sbarkeit gewisser diophantischer Gleichungen . Avhdl. Norske Vid. Akad. Oslo I 12 (1937), 1 \u2013 16 . Th. Skolem. 1937. Anwendung exponentieller Kongruenzen zum Beweis der Unl\u00f6sbarkeit gewisser diophantischer Gleichungen. Avhdl. Norske Vid. Akad. Oslo I 12 (1937), 1\u201316.","journal-title":"Avhdl. Norske Vid. Akad. Oslo"},{"key":"e_1_3_2_1_29_1","unstructured":"M. Soittola. 1976. On D0L Synthesis Problem. In Automata Languages Development A.\u00a0Lindenmayer and G.\u00a0Rozenberg (Eds.). North-Holland.  M. Soittola. 1976. On D0L Synthesis Problem. In Automata Languages Development A.\u00a0Lindenmayer and G.\u00a0Rozenberg (Eds.). North-Holland."},{"key":"e_1_3_2_1_30_1","volume-title":"Structure and Randomness","author":"Tao T.","unstructured":"T. Tao . 2008. Structure and Randomness . American Mathematical Society . T. Tao. 2008. Structure and Randomness. American Mathematical Society."},{"key":"e_1_3_2_1_31_1","volume-title":"The problem of appearance of a zero in a linear recurrence sequence (in Russian). Mat. Zametki 38, 2","author":"Vereshchagin K.","year":"1985","unstructured":"N.\u00a0 K. Vereshchagin . 1985. The problem of appearance of a zero in a linear recurrence sequence (in Russian). Mat. Zametki 38, 2 ( 1985 ). N.\u00a0K. Vereshchagin. 1985. The problem of appearance of a zero in a linear recurrence sequence (in Russian). Mat. Zametki 38, 2 (1985)."}],"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.3533328","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531130.3533328","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.3533328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,2]]},"references-count":31,"alternative-id":["10.1145\/3531130.3533328","10.1145\/3531130"],"URL":"https:\/\/doi.org\/10.1145\/3531130.3533328","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"}}]}}