{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T20:57:35Z","timestamp":1783198655198,"version":"3.54.6"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1986,6,1]],"date-time":"1986-06-01T00:00:00Z","timestamp":517968000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1986,6]]},"DOI":"10.1007\/bf02579170","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T21:15:33Z","timestamp":1174598133000},"page":"151-177","source":"Crossref","is-referenced-by-count":179,"title":["Nonlinearity of davenport\u2014Schinzel sequences and of generalized path compression schemes"],"prefix":"10.1007","volume":"6","author":[{"given":"Sergiu","family":"Hart","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF02579170_CR1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF01459088","volume":"99","author":"W. Ackermann","year":"1928","unstructured":"W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen,Math. Ann. 99 (1928), 113\u2013133.","journal-title":"Math. Ann."},{"key":"BF02579170_CR2","doi-asserted-by":"crossref","unstructured":"M. Atallah, Dynamic Computational Geometry,Proc. 24th Symp. on Foundations of Computer Science, 1983, 92\u201399.","DOI":"10.1109\/SFCS.1983.13"},{"key":"BF02579170_CR3","doi-asserted-by":"crossref","first-page":"363","DOI":"10.4064\/aa-17-4-363-372","volume":"17","author":"H. Davenport","year":"1971","unstructured":"H. Davenport, A Combinatorial Problem Connected with Differential Equations, II,Acta Arithmetica 17 (1971), 363\u2013372.","journal-title":"Acta Arithmetica"},{"key":"BF02579170_CR4","doi-asserted-by":"crossref","first-page":"684","DOI":"10.2307\/2373068","volume":"87","author":"H. Davenport","year":"1965","unstructured":"H. Davenport andA. Schinzel, A Combinatorial Problem Connected with Differential Equations,Amer. J. Math. 87 (1965), 684\u2013694.","journal-title":"Amer. J. Math."},{"key":"BF02579170_CR5","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-1-4684-2001-2_14","volume-title":"Complexity of Computer Computations","author":"M. J. Fisher","year":"1972","unstructured":"M. J. Fisher, Efficiency of Equivalence Algorithms,in: Complexity of Computer Computations, (R. E. Miller and J. W. Thatcher, Eds.), Plenum Press, New York, 1972, 153\u2013168."},{"key":"BF02579170_CR6","volume-title":"Ramsey Theory","author":"R. L. Graham","year":"1980","unstructured":"R. L. Graham, B. L. Rothschild andJ. H. Spencer,Ramsey Theory, Wiley-Interscience, New York, 1980."},{"key":"BF02579170_CR7","doi-asserted-by":"crossref","first-page":"43","DOI":"10.2307\/2267457","volume":"17","author":"G. Kreisel","year":"1952","unstructured":"G. Kreisel, On the Interpretation of Nonfinitistic Proofs, II,J. Symbolic Logic 17 (1952), 43\u201358.","journal-title":"J. Symbolic Logic"},{"key":"BF02579170_CR8","doi-asserted-by":"crossref","first-page":"267","DOI":"10.2307\/2006985","volume":"113","author":"J. Ketonen","year":"1981","unstructured":"J. Ketonen andR. M. Solovay, Rapidly Growing Ramsey Functions,Ann. of Math. 113 (1981), 267\u2013314.","journal-title":"Ann. of Math."},{"key":"BF02579170_CR9","doi-asserted-by":"crossref","unstructured":"R. Livne andM. Sharir, On Minima of Functions, Intersection Patterns of Curves, and Davenport\u2014Schinzel Sequences,Proc. 26th IEEE Symposium on Foundations of Computer Science, Portland, Ore., October 1985, 312\u2013320.","DOI":"10.1109\/SFCS.1985.40"},{"key":"BF02579170_CR10","doi-asserted-by":"crossref","unstructured":"J. Paris andL. Harrington, A Mathematical Incompleteness in Peano Arithmetic,in: Handbook of Mathematical Logic, (ed: J. Barwise), North-Holland 1977, 1133\u20131142.","DOI":"10.1016\/S0049-237X(08)71130-3"},{"key":"BF02579170_CR11","unstructured":"H. Rogers,Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967."},{"key":"BF02579170_CR12","doi-asserted-by":"crossref","first-page":"355","DOI":"10.4064\/aa-17-4-355-362","volume":"17","author":"D. P. Roselle","year":"1971","unstructured":"D. P. Roselle andR. G. Stanton, Some Properties of Davenport\u2014Schinzel Sequences,Acta Arithmetica 17 (1971), 355\u2013362.","journal-title":"Acta Arithmetica"},{"key":"BF02579170_CR13","doi-asserted-by":"crossref","unstructured":"M. Sharir, Almost Linear Upper Bounds on the Length of General Davenport\u2014Schinzel Sequences,Combinatorica 7 (1987),to appear.","DOI":"10.1007\/BF02579209"},{"key":"BF02579170_CR14","unstructured":"M. Sharir, On the Two-dimensional Davenport\u2014Schinzel Problem,Techn. Rep. 193, Comp. Sci. Dept., Courant Institute, 1985."},{"key":"BF02579170_CR15","doi-asserted-by":"crossref","first-page":"213","DOI":"10.4064\/aa-25-2-213-224","volume":"25","author":"E. Szemer\u00e9di","year":"1974","unstructured":"E. Szemer\u00e9di, On a Problem by Davenport and Schinzel,Acta Arithmetica 25 (1974), 213\u2013224.","journal-title":"Acta Arithmetica"},{"key":"BF02579170_CR16","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan, Efficiency of a Good but not Linear Set-union Algorithm,J. Assoc. Computing Machinery 22 (1975), 215\u2013225.","journal-title":"J. Assoc. Computing Machinery"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579170.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579170\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T05:05:43Z","timestamp":1736917543000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,6]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1986,6]]}},"alternative-id":["BF02579170"],"URL":"https:\/\/doi.org\/10.1007\/bf02579170","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,6]]}}}