{"entities":{"Q1067775":{"pageid":1078527,"ns":120,"title":"Item:Q1067775","lastrevid":69771438,"modified":"2026-04-13T09:16:49Z","type":"item","id":"Q1067775","labels":{"en":{"language":"en","value":"The analysis of simple list structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3930329"}},"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":"Q1067775$EF19140D-8DF6-41A7-8DDF-D3235913ADF5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9f1f44dc975b1f0706fa537cc931169d1510c896","datavalue":{"value":{"text":"The analysis of simple list structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1067775$355E57F6-56B1-4505-A1BF-44722037CC71","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e9b8101f9784882c81b514b8e042a996f4e4a65b","datavalue":{"value":"0581.68021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067775$A5536A93-2386-4FAF-80E8-964362699FAE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0211a3377a31b81b2a8dc0e9d838595af2732577","datavalue":{"value":"10.1016/0020-0255(86)90016-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067775$6BB52553-148D-4524-A236-FF4360B375B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4e841897d4c74a0c7a579f2ae2fa0af6ee543a6","datavalue":{"value":{"entity-type":"item","numeric-id":640841,"id":"Q640841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$A7404EF1-B6C8-4C11-89AA-E1976AD09A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"53125eaf7d85b071875b91a370fccc4afcbbe863","datavalue":{"value":{"entity-type":"item","numeric-id":1067773,"id":"Q1067773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$0A042646-B892-4F63-AF9D-AB4BCAC019EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b97bde5270147577b80be79d7539f14bdc38196d","datavalue":{"value":{"entity-type":"item","numeric-id":1145671,"id":"Q1145671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$756E4F55-0774-4433-A8C5-262EE48EFF60","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$8DEE76AB-9E1E-42F1-96D8-480C9BF9AC01","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":"Q1067775$B4CD83F4-57E7-418D-BFE3-216214489CDC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"43ad96d4d17cd7c03d9e3e7f3ebbbd17799f72bb","datavalue":{"value":"https://hal.inria.fr/inria-00076317/file/RR-0241.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q1067775$A81B9E06-4DAA-4784-9811-8F29D40184D0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ace967fb0c46c1fecc31c25026a445d442b2f577","datavalue":{"value":"We present an analysis of simple lists, either sorted or unsorted, under the set of all their possible histories (i.e. evolutions considered up to order isomorphism) of length n. Using the theory of continued fractions and orthogonal polynomials. \\textit{P. Flajolet, J. Fran\u00e7on} and \\textit{J. Vuillemin} [J. Algorithms 1, 111-141 (1980; Zbl 0445.68036)] have determined average costs of sequences of operations for many data structures of the dictionary or priority queue type. We show here that for the simplest structures variance estimates can also be obtained. The method uses continued fractions and properties of nonclassical q- generalizations of Hermite and Laguerre polynomials.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067775$6B5B0C81-7ECE-4BAC-89F5-67056BC53904","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067775$6A9E965C-CEA0-44DB-A952-D5D19A9263BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"517ace4a4f9c45a5475b4a8927a567447dbdb293","datavalue":{"value":"68N99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067775$338064A4-8E8F-4710-B4E1-09F4EF81C8B2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5690c6ad65b27d8266af0f9be83e774813c98fcb","datavalue":{"value":"3930329","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067775$0D16ECE0-0C97-496C-9443-65927B544468","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afee417564209b61e3e00baf8c5b26c09ce9029b","datavalue":{"value":"performance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067775$8B868899-E1F7-4BED-AD23-3E59A4338E68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d355ba91b7306e28e8fbac1ccabb68f8b0dbbfbb","datavalue":{"value":"analysis of simple lists","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067775$C7F6C6E5-8E88-4B00-89E9-A87312E39B6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ad86bb53b74d37af3a4d36e8a96c2c4376ac4b1","datavalue":{"value":"continued fractions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067775$141663B0-22FC-40C9-BCC7-703824482DD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a41e1dbcad6d9f1bee6da7b1ba4d857ebc56471","datavalue":{"value":"orthogonal polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067775$5E9B2D43-61D7-4D22-9EEA-266CD1064F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43d8de44b3f88bd19a871628a3509981cd748562","datavalue":{"value":"data structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067775$42D406CD-919F-4868-8CF5-51AAA502192B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21d9fdbee081817f19f8fab3d793f52d8800e5f6","datavalue":{"value":"dictionary","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067775$03626B59-F8B4-449B-9058-F66AD6B152CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"170f891b3a6d35c28ebb72165af585c2d5326a35","datavalue":{"value":"priority queue","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067775$AB6FE760-41FD-4E7F-B002-D13A0C08C971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6616558cdd3a25f72a1c050451e372f9f1c94ef1","datavalue":{"value":"q- generalizations of Hermite and Laguerre polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067775$D18467CA-A918-4F40-B208-53DD101254C9","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":"Q1067775$E97CF9D9-0104-451B-B679-F686A752251F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"49160bbb848ef892f2c9b0189c1f95e1b4ac1dd9","datavalue":{"value":"W2159186660","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067775$607FEAD5-9160-492C-B557-15ED018BEC1C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"05c9604b3974245f704cf9958fb7a196884803bf","datavalue":{"value":{"entity-type":"item","numeric-id":3910016,"id":"Q3910016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$8B6AF95F-ED00-4803-B018-40F9FD1EB3AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c173eaccf043d85fe3ba7e9ee81d83288b9c760","datavalue":{"value":{"entity-type":"item","numeric-id":3890114,"id":"Q3890114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$7D41EC70-E325-4637-AC4F-E56EC75367CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa9fce0d48b5758fbb9b79953def7348fcc6c444","datavalue":{"value":{"entity-type":"item","numeric-id":1145147,"id":"Q1145147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$8E64128A-4A0B-4BE3-B388-E9B06C803234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"155c6d32c26f70119ef41faf198dafb5cefe43bc","datavalue":{"value":{"entity-type":"item","numeric-id":4155833,"id":"Q4155833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$2934744A-CD4E-446F-9F77-394C3180672F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54361c5038a0aafb78458ac6bc44cd0418c204db","datavalue":{"value":{"entity-type":"item","numeric-id":5788319,"id":"Q5788319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$256E94ED-0F42-4F38-966E-92F27C57F257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c61863458db667259073c21f0fce496288220ca","datavalue":{"value":{"entity-type":"item","numeric-id":1245568,"id":"Q1245568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$EC70DBE9-7200-447A-9BE9-4AD0809C3C36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$E7F64DF1-1C08-42A3-9D20-878CEE787194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6abaca99af3d3bf5f44b53acaeba01877fc4bdd9","datavalue":{"value":{"entity-type":"item","numeric-id":4081259,"id":"Q4081259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$7E86D85E-1EDC-4A10-9101-06783FFEA342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea3c8fc14a745170bca600bb735de5d34d0173d1","datavalue":{"value":{"entity-type":"item","numeric-id":5812204,"id":"Q5812204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$E6F9A234-2761-4676-9E10-2720F7474DC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0ac37962d685101ffdbd3da4e5f74479c784f61","datavalue":{"value":{"entity-type":"item","numeric-id":5792555,"id":"Q5792555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067775$B0A55690-FA19-4135-95ED-8F9D22A3C9AF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebc5c41a12b97cce5343b7eb9de35bea6bbf3668","datavalue":{"value":{"entity-type":"item","numeric-id":3974864,"id":"Q3974864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"425ec59446820f64c2b1326bb8ba2427c1f65e5e","datavalue":{"value":{"amount":"+0.8335452675819397","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":"Q1067775$9D372481-C257-4001-938D-F2BCF189312C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24225636e22e08e46c6bc7c59bca0cff59386eb5","datavalue":{"value":{"entity-type":"item","numeric-id":4016510,"id":"Q4016510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b08f166a92d5fb756683aee10e17bf053c344a1a","datavalue":{"value":{"amount":"+0.8263439536094666","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":"Q1067775$4940C014-9DA2-4667-8E82-287A9241E915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db7f2e4459e084157e0876fe0f88a22ab4beeb34","datavalue":{"value":{"entity-type":"item","numeric-id":3789050,"id":"Q3789050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"106c16c93a0c5dc6c5d1cf2ba5e232f8ed12d57c","datavalue":{"value":{"amount":"+0.8225321173667908","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":"Q1067775$945A1185-B78E-4314-AFB3-8172E12C7278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6584d2a8455e00d26bc8d18654d7e72f76e34ff2","datavalue":{"value":{"entity-type":"item","numeric-id":3717966,"id":"Q3717966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"611ced29ce6ceaefc6780440faa7cd61159e79cb","datavalue":{"value":{"amount":"+0.7917516231536865","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":"Q1067775$77934000-24FB-4991-AD64-3DED67542ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96839fb93d10e5c93c8dce2a703361d5d3806e6c","datavalue":{"value":{"entity-type":"item","numeric-id":1179455,"id":"Q1179455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0adc286fb1147b83973977a1d9f5150ed9f3d552","datavalue":{"value":{"amount":"+0.7912323474884033","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":"Q1067775$5B23B649-B082-4C87-8227-D9C3C9B93561","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The analysis of simple list structures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_analysis_of_simple_list_structures"}}}}}