{"entities":{"Q1119587":{"pageid":1130336,"ns":120,"title":"Item:Q1119587","lastrevid":66168552,"modified":"2026-04-12T08:00:17Z","type":"item","id":"Q1119587","labels":{"en":{"language":"en","value":"Improved lower bounds on the length of Davenport-Schinzel sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4099314"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$361E14F9-E459-403D-9312-61EEFB030D7C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0c09e5ee89fffd241d0fc3f8ac23469c73cba168","datavalue":{"value":{"text":"Improved lower bounds on the length of Davenport-Schinzel sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1119587$E7C23C11-73E2-4994-81A1-AF835723565C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"67bcc344027270139df122dfb4808b8719b9aa96","datavalue":{"value":"0672.05015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119587$8E00018F-2AE7-4B96-AB4E-53B2B521F96D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"82331655e827c3e021714712998dda1228f0d751","datavalue":{"value":"10.1007/BF02122559","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119587$BDC6DB28-297F-439F-961B-7721E62F75A1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"05973d4747711a904c4eb354f325fda834906623","datavalue":{"value":{"entity-type":"item","numeric-id":396765,"id":"Q396765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$B9FDAE8D-03DA-471E-9874-89DA7DF24A1D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$CBAB7CB1-5E9B-41B8-B44C-8BA745F15A3B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1119587$56A64340-F9DD-43B8-A3E6-B2E91AA2F2B5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"07cecf21e05b5ea4bad59f7648c617745b2486d8","datavalue":{"value":"For the longest length of general Davenport-Schinzel sequences, i.e. sequences of n letters with no immediate repetitions and no subsequence of type a..b..a..b..a.. of length \\(s+2\\), the estimate \\(\\Omega (n\\alpha^ s(n))\\) is established, where \\(\\alpha\\) (n) is the inverse of the Ackermann function. This improves earlier bounds. The proof uses generalized path compression schemes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119587$FEAF0FE7-ABD5-4471-BB12-3B0F45CA57CB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"826db22c8ad0fdc537525e95eba03f39da931f90","datavalue":{"value":{"entity-type":"item","numeric-id":178041,"id":"Q178041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$7F11FCAF-E495-4CB3-92EE-9A3C4E49A958","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d36e3867d5946e3717838aa146c58da76ecefaf","datavalue":{"value":"05A99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119587$43BC239D-C6B5-4561-B58D-CD91CB68B856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119587$8FC5D76C-FF42-4167-9694-52CC50C8E93C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119587$2676BACC-EFB2-44FC-B039-A2F5D1C78780","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"80d53aa9cf64475759e1f3d60f9e36b10739d3d9","datavalue":{"value":"4099314","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119587$DF80096A-50E8-47C3-A032-059CC9A16E1A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"900572492ff0b9c514cba808fa7fe3539b0c1cb0","datavalue":{"value":"Davenport-Schinzel sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119587$B4143C27-099B-44E6-BFD4-92AB748C4562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c366d9e44e0d6a9e2cdc753868eab05ee1b2ecc","datavalue":{"value":"Ackermann function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119587$B8A296CA-0D12-4CE3-94BA-76CA7D225D2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e396eab21bddb5f44dfdf6067fa15ff34883085","datavalue":{"value":"generalized path compression schemes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119587$EC74EFE7-6B21-46F5-8A79-B16E27EF78F6","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$FBB6E28A-5909-4691-87F0-268091AC2FE2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9576a5fe2c992317af23885c5add5f63d0b929dc","datavalue":{"value":{"entity-type":"item","numeric-id":3798231,"id":"Q3798231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$09A72E68-B0C1-4583-AA80-3ACB505D9BC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a242496d908b6d1e30e137bd48db323e9a6e17e","datavalue":{"value":{"entity-type":"item","numeric-id":5340927,"id":"Q5340927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$411C6C25-4312-45C6-BA89-EEEC4DB6E6CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7f962d4b7bceadb914a43cc05d640fec4e9860f","datavalue":{"value":{"entity-type":"item","numeric-id":5619850,"id":"Q5619850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$02658409-1CAA-46F2-8C6E-3941F68602DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c368a550cf5b4e92a6d4f0e58d9ca1eb20b223cd","datavalue":{"value":{"entity-type":"item","numeric-id":1097884,"id":"Q1097884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$7560F7AE-9503-407D-A072-0CFD98B8E011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb9ce8a84b3ae2d93c43f6026772aa9721f7d7b1","datavalue":{"value":{"entity-type":"item","numeric-id":1821354,"id":"Q1821354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$482946E3-1FA7-4053-91F6-CB69A12E1509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dca04568c4dfb5342a35fa8c21257c511b7967fb","datavalue":{"value":{"entity-type":"item","numeric-id":1094871,"id":"Q1094871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$3CB84895-FA36-4AD9-B06E-42D5355072D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3be39f64690d4cb3f58df35a467dec31b3420776","datavalue":{"value":{"entity-type":"item","numeric-id":1097885,"id":"Q1097885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119587$F3665DF3-DE17-47E8-9F75-06DA75067B18","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"70b0ff9d3fd2987e0378be3e44c21f48bb8e1f00","datavalue":{"value":"https://doi.org/10.1007/bf02122559","type":"string"},"datatype":"url"},"type":"statement","id":"Q1119587$E814ED1A-B007-4438-AEDF-42359E845CE1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a2f6f28065959b8a0f662e8312c597d32924340","datavalue":{"value":"W2093966347","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119587$945EA154-E0FB-48A8-9421-CE8B51E0FD6B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c76a95f491ff34ff517091d2745b090fcf8966ed","datavalue":{"value":{"entity-type":"item","numeric-id":1097885,"id":"Q1097885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1244d748e2b8afa98bf302ef6c0a0dce56be787","datavalue":{"value":{"amount":"+0.9037508368492126","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119587$C5832271-E271-4DE1-883E-73E92B5448BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbef73deca305c9a236cbe8af1d0206592f5c3c1","datavalue":{"value":{"entity-type":"item","numeric-id":911595,"id":"Q911595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0314697fdb989fa3213b9a89fcda68f0bea7313","datavalue":{"value":{"amount":"+0.8870258927345276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119587$68CA6858-25E1-4C57-8225-AC1D2C35665C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f51da463431e60834a117135a61f94e9ec28121f","datavalue":{"value":{"entity-type":"item","numeric-id":4633804,"id":"Q4633804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2593eb3b24e3e411450e9f1da00872de3340926d","datavalue":{"value":{"amount":"+0.8829913139343262","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119587$285A87A8-6ED6-4EF2-96EC-03B4EC06B8F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86413ba6be88481277107ac40b784fecca852057","datavalue":{"value":{"entity-type":"item","numeric-id":3578194,"id":"Q3578194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7eefc017555b931e6221e752220fbbe49785d3de","datavalue":{"value":{"amount":"+0.8769392371177673","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119587$576F7CCF-44E6-4984-BF2B-6AFEDBA79BE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92269594d95f5638786ba1e069d33c8738bc0259","datavalue":{"value":{"entity-type":"item","numeric-id":1097884,"id":"Q1097884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05b5a9320c11a8526525b4dff17808bb95adf257","datavalue":{"value":{"amount":"+0.8743900656700134","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119587$EE930F54-D8D7-449A-88B7-2D6D2217104D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improved lower bounds on the length of Davenport-Schinzel sequences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Improved_lower_bounds_on_the_length_of_Davenport-Schinzel_sequences"}}}}}