{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T22:00:34Z","timestamp":1775340034436,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439500","type":"print"},{"value":"9783662439517","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_27","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T08:37:49Z","timestamp":1402475869000},"page":"318-329","source":"Crossref","is-referenced-by-count":18,"title":["On the Positivity Problem for Simple Linear Recurrence Sequences,"],"prefix":"10.1007","author":[{"given":"Jo\u00ebl","family":"Ouaknine","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James","family":"Worrell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM J. Comput.\u00a038(5) (2009)","DOI":"10.1137\/070697926"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Amoroso, F., Viada, E.: Small points on subvarieties of a torus. Duke Mathematical Journal\u00a0150(3) (2009)","DOI":"10.1215\/00127094-2009-056"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Amoroso, F., Viada, E.: On the zeros of linear recurrence sequences. Acta Arithmetica\u00a0147(4) (2011)","DOI":"10.4064\/aa147-4-4"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Bell, J.P., Gerhold, S.: On the positivity set of a linear recurrence. Israel Jour. Math.\u00a057 (2007)","DOI":"10.1007\/s11856-006-0015-1"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Berstel, J., Mignotte, M.: Deux propri\u00e9t\u00e9s d\u00e9cidables des suites r\u00e9currentes lin\u00e9aires. Bull. Soc. Math. France\u00a0104 (1976)","DOI":"10.24033\/bsmf.1823"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry. Springer (1998)","DOI":"10.1007\/978-3-662-03718-8"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/11817963_34","volume-title":"Computer Aided Verification","author":"M. Braverman","year":"2006","unstructured":"Braverman, M.: Termination of integer linear programs. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol.\u00a04144, pp. 372\u2013385. Springer, Heidelberg (2006)"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Burke, J.R., Webb, W.A.: Asymptotic behavior of linear recurrences. Fib. Quart.\u00a019(4) (1981)","DOI":"10.1080\/00150517.1981.12430066"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Everest, G., van der Poorten, A., Shparlinski, I., Ward, T.: Recurrence Sequences. American Mathematical Society (2003)","DOI":"10.1090\/surv\/104"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Evertse, J.H., Schlickewei, H.P., Schmidt, W.M.: Linear equations in variables which lie in a multiplicative group. Ann. Math.\u00a0155(3) (2002)","DOI":"10.2307\/3062133"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Gyori, I., Ladas, G.: Oscillation Theory of Delay Differential Equations. Oxford Mathematical Monographs. Oxford University Press (1991)","DOI":"10.1093\/oso\/9780198535829.001.0001"},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"Halava, V., Harju, T., Hirvensalo, M.: Positivity of second order linear recurrent sequences. Discrete Appl. Math.\u00a0154(3) (2006)","DOI":"10.1016\/j.dam.2005.10.009"},{"key":"27_CR13","unstructured":"Halava, V., Harju, T., Hirvensalo, M., Karhum\u00e4ki, J.: Skolem\u2019s problem \u2014 on the border between decidability and undecidability. Technical Report 683, Turku Centre for Computer Science (2005)"},{"key":"27_CR14","unstructured":"Laohakosol, V.: Personal communication (July 2013)"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Laohakosol, V., Tangsupphathawat, P.: Positivity of third order linear recurrence sequences. Discrete Appl. Math.\u00a0157(15) (2009)","DOI":"10.1016\/j.dam.2009.06.021"},{"key":"27_CR16","unstructured":"Lipton, R.J.: Mathematical embarrassments. Blog entry (December 2009), http:\/\/rjlipton.wordpress.com\/2009\/12\/26\/mathematical-embarrassments\/"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Liu, L.L.: Positivity of three-term recurrence sequences. Electr. J. Comb.\u00a017(1) (2010)","DOI":"10.37236\/329"},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"Mignotte, M., Shorey, T.N., Tijdeman, R.: The distance between terms of an algebraic recurrence sequence. Journal f\u00fcr die reine und angewandte Mathematik\u00a0349 (1984)","DOI":"10.1515\/crll.1984.349.63"},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"Nagasaka, K., Shiue, J.-S.: Asymptotic positiveness of linear recurrence sequences. Fib. Quart.\u00a028(4) (1990)","DOI":"10.1080\/00150517.1990.12429472"},{"key":"27_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-642-33512-9_3","volume-title":"Reachability Problems","author":"J. Ouaknine","year":"2012","unstructured":"Ouaknine, J., Worrell, J.: Decision problems for linear recurrence sequences. In: Finkel, A., Leroux, J., Potapov, I. (eds.) RP 2012. LNCS, vol.\u00a07550, pp. 21\u201328. Springer, Heidelberg (2012)"},{"key":"27_CR21","doi-asserted-by":"crossref","unstructured":"Ouaknine, J., Worrell, J.: On the Positivity Problem for simple linear recurrence sequences (full version). arXiv:1309.1550 (2013)","DOI":"10.1137\/1.9781611973402.27"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Ouaknine, J., Worrell, J.: Positivity problems for low-order linear recurrence sequences. In: Proc. Symp. on Discrete Algorithms (SODA). ACM-SIAM (2014)","DOI":"10.1137\/1.9781611973402.27"},{"key":"27_CR23","unstructured":"Ouaknine, J., Worrell, J.: Ultimate Positivity is decidable for simple linear recurrence sequences. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol.\u00a08573, pp. 330\u2013341. Springer, Heidelberg (2014); Full version as arXiv:1309.1914"},{"key":"27_CR24","unstructured":"Rozenberg, G., Salomaa, A.: Cornerstones of Undecidability. Prentice Hall (1994)"},{"key":"27_CR25","unstructured":"Salomaa, A.: Growth functions of Lindenmayer systems: Some new approaches. In: Lindenmayer, A., Rozenberg, G. (eds.) Automata, Languages, Development. North-Holland (1976)"},{"key":"27_CR26","unstructured":"Soittola, M.: On D0L synthesis problem. In: Lindenmayer, A., Rozenberg, G. (eds.) Automata, Languages, Development. North-Holland (1976)"},{"key":"27_CR27","doi-asserted-by":"crossref","unstructured":"Tangsupphathawat, P., Punnim, N., Laohakosol, V.: The positivity problem for fourth order linear recurrence sequences is decidable. Colloq. Math.\u00a0128(1) (2012)","DOI":"10.4064\/cm128-1-11"},{"key":"27_CR28","doi-asserted-by":"crossref","unstructured":"Tao, T.: Structure and Randomness. American Mathematical Society (2008)","DOI":"10.1090\/mbk\/059"},{"key":"27_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-642-20712-9_24","volume-title":"Computer Science \u2013 Theory and Applications","author":"S. Tarasov","year":"2011","unstructured":"Tarasov, S., Vyalyi, M.: Orbits of linear maps and regular languages. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 305\u2013316. Springer, Heidelberg (2011)"},{"key":"27_CR30","doi-asserted-by":"crossref","unstructured":"Vereshchagin, N.K.: The problem of appearance of a zero in a linear recurrence sequence. Mat. Zametki 38(2) (1985) (in Russian)","DOI":"10.1007\/BF01156238"},{"key":"27_CR31","doi-asserted-by":"crossref","unstructured":"Yokoyama, K., Li, Z., Nemes, I.: Finding roots of unity among quotients of the roots of an integral polynomial. In: Proc. Intern. Symp. on Symb. and Algebraic Comp. (1995)","DOI":"10.1145\/220346.220357"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:23:34Z","timestamp":1746264214000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}