{"entities":{"Q1097884":{"pageid":1108636,"ns":120,"title":"Item:Q1097884","lastrevid":70305723,"modified":"2026-04-13T13:52:31Z","type":"item","id":"Q1097884","labels":{"en":{"language":"en","value":"Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4035839"}},"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":"Q1097884$D63FEF2D-6DA2-464D-9CA8-84E16BBF06AC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4e968592ecbbf7c526fe2ca1292287eea82b9093","datavalue":{"value":{"text":"Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097884$73DF5A6E-CFBB-4CBE-A500-3A58769D7CEC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cf39d168e72eb89a0cf4b58d1f94060616d1bb6c","datavalue":{"value":"0636.05003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097884$1EA2FDBD-258B-446E-89D1-0F0BB2578F44","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7f5f2579ebea09cba0a1393dfcc29041cec2643e","datavalue":{"value":"10.1007/BF02579170","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097884$7B714162-746D-4EB1-AF62-0041FB123043","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d1bf12482695cdef9e154da16db454d5e8e7444","datavalue":{"value":{"entity-type":"item","numeric-id":192152,"id":"Q192152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097884$7A4697FF-7342-4A52-A5F4-C3E76C611451","rank":"normal"},{"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":"Q1097884$18E33110-E6F1-4189-B8B3-6C8119D90145","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":"Q1097884$F4C9F3FD-BE7B-4B8C-A49F-5B8F02D7032C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1097884$2683F365-DC44-4972-9620-3CE1954A8B19","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9299ce467d060a3c26a60c706bf1daec2240fe7f","datavalue":{"value":"Davenport-Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We show that the maximal length of a Davenport-Schinzel sequence composed of n symbols is \\(\\theta(n \\alpha(n))\\), where \\(\\alpha(n)\\) is the functional inverse of Ackermann's function, and is thus very slowly increasing to infinity. This is achieved by establishing an equivalence between such sequences and generalized path compression schemes on rooted trees, and then by analyzing these schemes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097884$85D726F1-F0EF-4B10-B070-71A5CECD2A2F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"880665e99fe5de07999ef2f74a810b36dd3dabed","datavalue":{"value":"05A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097884$0102214F-8436-49E8-9DF4-769DA5C01F70","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"52f4b0b9e05737790427ba4d52e887b7cf1cd6d2","datavalue":{"value":"4035839","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097884$1FA6351E-7373-436A-B624-863C5712A663","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"900572492ff0b9c514cba808fa7fe3539b0c1cb0","datavalue":{"value":"Davenport-Schinzel sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097884$5CD3AAAC-7333-41C2-AD3E-F3AA2DE05B11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df30d260a0a8299eca168bbaab05f7b67ba40127","datavalue":{"value":"forbidden subsequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097884$5CDDE13F-88A9-4D5D-90FF-301775E1201A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e06e057065bc447905140262241f41db2e30f2c9","datavalue":{"value":"Q56457309","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097884$A754E680-DE0B-4523-A661-28E47B5461AE","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":"Q1097884$25FB81F3-67C3-4B40-BBF6-CB14C7DECA96","rank":"normal"}],"P223":[{"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":"Q1097884$43BEF8C4-F530-4840-A9C1-945A69F9F592","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":"Q1097884$36B02F3F-DE05-4507-A404-4A35A74B2DB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98a0f5ab3a82f792e215192b74a3f7485b0840ad","datavalue":{"value":{"entity-type":"item","numeric-id":5809142,"id":"Q5809142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097884$1D0F6238-5639-43CA-A9BF-4E60CDD949CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e243aafa636ab09d990564f754a991e6ab8e8228","datavalue":{"value":{"entity-type":"item","numeric-id":1168967,"id":"Q1168967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097884$BEB9810D-7E66-4D06-AD9D-63D16BB72D10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097884$96474F7C-8F6C-43E9-8B12-4E9DCF6458C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d833ab673ebd20a91b14b64621d6d105390ebc3","datavalue":{"value":{"entity-type":"item","numeric-id":5618381,"id":"Q5618381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097884$57E26207-85EE-454D-BF52-02051C0D8527","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":"Q1097884$42664B7F-ADD7-4454-920D-DC95E11B5DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932383d1ac997ed208ef47dcb574b592efaf75b3","datavalue":{"value":{"entity-type":"item","numeric-id":4065031,"id":"Q4065031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097884$094F74F2-4766-4547-A415-6F7B50E7EE42","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"23bba38baecc41f1191dfda2c5d03e7cb46334eb","datavalue":{"value":"https://doi.org/10.1007/bf02579170","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097884$9F78EBB0-B5EE-4947-AD93-EA2D91552477","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4c86db3a801fc58845fd9d26c97a8f99985d3142","datavalue":{"value":"W2019176509","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097884$22B57BA3-0112-415B-BA01-34B1906F9732","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9dc6880229342628a1986fb0acd06a192af8c10","datavalue":{"value":{"entity-type":"item","numeric-id":1119587,"id":"Q1119587"},"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":"Q1097884$CCEE8BED-3EB1-4304-8046-D771A5D8D8C2","rank":"normal"},{"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":"cc21f4494bb5086698e782c4b365e56cba27e9fe","datavalue":{"value":{"amount":"+0.858591616153717","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":"Q1097884$653F696E-B404-43FF-9830-E0CD63C9074F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5903d3cc89a0e45a34f3a425b010eb4cf7e5bc7","datavalue":{"value":{"entity-type":"item","numeric-id":4325546,"id":"Q4325546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cffb8bcdc1f788246cb395db37ce0fd0227a2b6","datavalue":{"value":{"amount":"+0.841505765914917","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":"Q1097884$F3F18F9C-AF59-434D-B693-DDB5301B1EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"225b5aee1dddfd7f4f5585463c76bd20b884a8bb","datavalue":{"value":{"entity-type":"item","numeric-id":1343170,"id":"Q1343170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff1370875766ca334bf8528dd652c94ba9b8c11d","datavalue":{"value":{"amount":"+0.8415052890777588","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":"Q1097884$35791600-217A-4843-B361-E33462A045B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be61c7002aa7849aafe034c55b9ee284d36a32d5","datavalue":{"value":{"entity-type":"item","numeric-id":3094908,"id":"Q3094908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f09aa683cf449822bb8d24e300e2c1f9c163e28","datavalue":{"value":{"amount":"+0.8413147330284119","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":"Q1097884$7F9E9CAA-D87B-40C3-80EA-5DCE06D4D7DA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nonlinearity_of_Davenport-Schinzel_sequences_and_of_generalized_path_compression_schemes"}}}}}