{"entities":{"Q1098314":{"pageid":1109066,"ns":120,"title":"Item:Q1098314","lastrevid":66126213,"modified":"2026-04-12T07:43:31Z","type":"item","id":"Q1098314","labels":{"en":{"language":"en","value":"Computing on a free tree via complexity-preserving mappings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4037245"}},"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":"Q1098314$5DDDC164-1619-4DC4-B13A-9DFA4982E04D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e2b20835b0004e0dcfd4527f0f6e1eb50b25360a","datavalue":{"value":{"text":"Computing on a free tree via complexity-preserving mappings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098314$2359C767-3A6E-440C-BFF9-24E4E21C05CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d59b373e647e55fbffcfaa8c63d10fb5d9a7b259","datavalue":{"value":"0636.68092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098314$84066EC5-5C4B-48DD-8BDD-DF9E1919104B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d8232490a5604174388cca692880aeb213208515","datavalue":{"value":"10.1007/BF01840366","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098314$234D9334-E6FE-43BA-A465-5518C70200AB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$5775E5CC-1995-4029-9300-A4E017BF9E30","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1098314$0F092D44-5F7E-45FE-935C-B4AA02CF8A7D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ea915b8a09cc6514e90a271e2d5e2a0c54e5ca80","datavalue":{"value":"The relationship between linear lists and free trees is studied. We examine a number of well-known data structures for computing functions on linear lists and show that they can be canonically transformed into data structures for computing the same functions defined over free trees. This is used to establish new upper bounds on the complexity of several query- answering problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098314$1F76397F-50BB-4CDF-83B7-DE568AB2EAF1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098314$B802B695-7493-4328-8674-3D5A7A8EE031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098314$C27F84FC-6C52-4A01-800E-2EFC14FA6CCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098314$8225AF06-9E64-4BCC-B210-7F40B8B8F79F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098314$026A77E1-69C5-4D57-B529-6D179F6DBBB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098314$BF1B69FE-2D79-41BA-8AB3-FA721FAC10A7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"46ca8eb6fa3be5444f8ffcfff0c1a7166923f8db","datavalue":{"value":"4037245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098314$EA3144EF-A67B-457B-BE42-393144286379","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1daee68cedeeadccdf496f924561e3065e4444","datavalue":{"value":"abstract data types","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098314$C3FC0141-6353-49D1-9CDE-C17B4EA713FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4a70f6bcff9d5e2174fb1517ba93acbfd0b4dad","datavalue":{"value":"inverse Ackermann function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098314$C23605D8-4FFA-470F-8847-282BDCEEDB35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b1357bbb77d5c3f9264830beee293e71d813c54","datavalue":{"value":"linear lists","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098314$2B0EB77F-6318-49BF-9587-B964D9B1C7D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9958275bb537b52c54b53810ec050a2fcd7199fc","datavalue":{"value":"free trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098314$9EB0DC24-2EC2-4359-AD46-773F89A60CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9592485cf04ef68f347e7a3da52d03b48fbd617f","datavalue":{"value":"query-answering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098314$F5D36879-FF43-478B-BDE4-90263CB44114","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ad91bd4a1378a015ef9d0cfb2ca621b16347f71","datavalue":{"value":{"entity-type":"item","numeric-id":525971,"id":"Q525971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$E154D64E-22D2-4BDA-A9F6-9618A301B6EA","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":"Q1098314$71067365-B691-4319-91E1-01348527C443","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$434D42B0-4180-414E-8BB4-8964442BAE05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dc7eb8caf969204b8972e6206e244f9c8f10485","datavalue":{"value":{"entity-type":"item","numeric-id":148390,"id":"Q148390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$60A498FC-00AE-4B54-9CAF-64D5CFB0368C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76ce173cdd6420ed78061b92000307f2e179c306","datavalue":{"value":{"entity-type":"item","numeric-id":1099957,"id":"Q1099957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$516A08F8-7C3C-44D3-B70D-7049973B34DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f13f2ff759bf0a1f3125e9a629e6a5c6d8aa719","datavalue":{"value":{"entity-type":"item","numeric-id":3659159,"id":"Q3659159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$8EE97F4E-E50E-4A48-9887-D2F90D54DB0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05e150681c1d0241ecb463ace4c088cbd7d131cd","datavalue":{"value":{"entity-type":"item","numeric-id":3319776,"id":"Q3319776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$A8D3F46B-6286-4A74-847D-BB6892AD423A","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":"Q1098314$5396815F-9B89-4966-95D5-CFC2A53133C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdc80085f51274788196b5be4e7f9615585e8b2f","datavalue":{"value":{"entity-type":"item","numeric-id":3678686,"id":"Q3678686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$3FBBA51E-241A-4871-B9D0-F028043B47AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7b76c498f5c4968b18e0a5cf8a7bb4513c31822","datavalue":{"value":{"entity-type":"item","numeric-id":1838310,"id":"Q1838310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$85837FFD-EB1E-45E3-A7A0-FDA100268BA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0f53d9231bc5ff64922d7dd218bb49071786117","datavalue":{"value":{"entity-type":"item","numeric-id":3768416,"id":"Q3768416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$1FCF2174-1E25-4BC5-AAC1-1232EF72DE67","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":"Q1098314$7F36AB57-DD3D-4D4C-B61F-80D0DB956585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb4bb8ecc53694b95953f765733c32a872021462","datavalue":{"value":{"entity-type":"item","numeric-id":3048273,"id":"Q3048273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$B5BE66FB-E52F-4D1D-9315-24E13FC9DB90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d30fe4fc429ab20e1cf52b13b1054b4c845f8b15","datavalue":{"value":{"entity-type":"item","numeric-id":3873557,"id":"Q3873557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$C9B9934A-3B88-4ACE-AAD2-9BAF7A2F4DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db8343e526f156f1469a28b5688ff6513e9b7246","datavalue":{"value":{"entity-type":"item","numeric-id":3678701,"id":"Q3678701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098314$A66F6BD0-ADE2-4966-BB27-1AE3032D04CE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcfd785e0076476df3193f36cdd42bbfc0f3d07d","datavalue":{"value":{"entity-type":"item","numeric-id":3315554,"id":"Q3315554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"596ab1f742cc920d53393e7652c92a8aa25b253c","datavalue":{"value":{"amount":"+0.7090132236480713","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":"Q1098314$8B1E1510-CC47-4829-98F3-67F0DD37D29C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fbc62846a997abb5ad412298f36fa96c3349e1c","datavalue":{"value":{"entity-type":"item","numeric-id":3723711,"id":"Q3723711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e27538faffca369280731ad9d0be5ab9357819c7","datavalue":{"value":{"amount":"+0.7087544202804565","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":"Q1098314$A0BCFFA6-3250-49BD-AEA6-90E0086C2B19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90f8b1657354046ad3914c06f58a3550c15690a2","datavalue":{"value":{"entity-type":"item","numeric-id":4536402,"id":"Q4536402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23668aa3a6031ff15df5bc910f48c6db9a466a1d","datavalue":{"value":{"amount":"+0.7022765874862671","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":"Q1098314$B3F473FA-5CE5-43D2-A77C-533E7521BF70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21e7249b1760305b2792b02e3a73e6b9702e9d6c","datavalue":{"value":{"entity-type":"item","numeric-id":1916363,"id":"Q1916363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed06e9e8474ffd6dbfd1db6bf1ca18b213956a1d","datavalue":{"value":{"amount":"+0.6990959048271179","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":"Q1098314$D113C7B4-DBF5-4CC5-B438-055C24CA3EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1a974435eb6f2d64fa759358f6aebe4a7c5f319","datavalue":{"value":{"entity-type":"item","numeric-id":4834384,"id":"Q4834384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61c4164b7ec23f489915ea1915f36ece8b3f2a31","datavalue":{"value":{"amount":"+0.6967136263847351","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":"Q1098314$225B125B-4ADC-42A8-8370-36DE17801D29","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing on a free tree via complexity-preserving mappings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_on_a_free_tree_via_complexity-preserving_mappings"}}}}}