{"entities":{"Q6042101":{"pageid":13176257,"ns":120,"title":"Item:Q6042101","lastrevid":98592323,"modified":"2026-06-05T18:01:33Z","type":"item","id":"Q6042101","labels":{"en":{"language":"en","value":"Tight bound for the number of distinct palindromes in a tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7686433"}},"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":"Q6042101$F8A00181-6DAE-41A7-B507-8171FBDCBBDA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60d20240aac6fac405eadd6e90c7ff96bba35959","datavalue":{"value":{"text":"Tight bound for the number of distinct palindromes in a tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6042101$EC826969-2A1D-47C1-B316-1C178229ED35","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5a564b55344dab305af2eaf7f87d179a933fc6eb","datavalue":{"value":"1523.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6042101$A2051919-4947-4E07-8FA7-365DBF541417","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9df236e2dc9472f40ed9746f2abb61952a513358","datavalue":{"value":"10.37236/10842","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6042101$F387D684-07C7-4564-9A99-E63DC6F5130C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c0f29833bf40fff5fa7dc4e5775a8ea015827ff","datavalue":{"value":{"entity-type":"item","numeric-id":294944,"id":"Q294944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$6A66601F-B44A-4AD5-ABC0-958B51A8E8D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d2f0d46d96166900d38ce02a3e241a6b0f47884c","datavalue":{"value":{"entity-type":"item","numeric-id":255283,"id":"Q255283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$273F72FC-20C6-48A8-BA40-598FC9DC5C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"446a873621e510ca421dac98a0ecf4b1b1cd2e8d","datavalue":{"value":{"entity-type":"item","numeric-id":313971,"id":"Q313971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$90FD22E1-18EB-4079-8F9C-DDDAF97129EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5322cac3a3ba4d62051da303a5fcff97e119f5dc","datavalue":{"value":{"entity-type":"item","numeric-id":1010604,"id":"Q1010604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$3321F611-730B-448F-9292-7190536A2053","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$48FB2924-F8C5-4EE9-BB20-835B6CC35F92","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0ca4bbeb33b3cf853bbcc8b99434c8752c257f63","datavalue":{"value":{"time":"+2023-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6042101$126C2601-634D-49AF-8FDF-052B86451568","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"592ca8ccbf5788152c8d05630ab64ef804bd876f","datavalue":{"value":"https://arxiv.org/abs/2008.13209","type":"string"},"datatype":"url"},"type":"statement","id":"Q6042101$1B73F984-1848-467F-87A1-D2D2ECCC179D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7fe2e9180a2aaeaefa02ab31fcd7df27a58e7050","datavalue":{"value":"Summary: For an undirected tree with edges labeled by single letters, we consider its substrings, which are labels of the simple paths between two nodes. A palindrome is a word \\(w\\) equal to its reverse \\(w^R\\). We prove that the maximum number of distinct palindromic substrings in a tree of \\(n\\) edges satisfies \\(\\text{PAL}(n)=\\mathcal{O}(n^{1.5})\\). This solves an open problem of \\textit{S. Brlek} et al. [Lect. Notes Comput. Sci. 9168, 155--166 (2015; Zbl 1434.68380)], who showed that \\(\\text{PAL}(n)=\\Omega(n^{1.5})\\). Hence, we settle the tight bound of \\(\\Theta(n^{1.5})\\) for the maximum palindromic complexity of trees. For standard strings, i.e., for trees that are simple paths, the maximum palindromic complexity is exactly \\(n+1\\).  We also propose an \\(\\mathcal{O}(n^{1.5} \\log^{0.5}{n})\\)-time algorithm reporting all distinct palindromes and an \\(\\mathcal{O}(n \\log^2 n)\\)-time algorithm finding the longest palindrome in a tree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6042101$57469375-1251-4309-B472-990BD5DB844A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6042101$8F894EEB-9173-4CEC-8008-8D50C3320D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6042101$A1C50134-7D95-4C04-9BE8-6DED09188DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6042101$123AEC32-7AD2-4536-8986-3BF6A56F6B54","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"60a2d5b5d8f7e24449033175d045c283e943d677","datavalue":{"value":"7686433","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6042101$C0641853-19C7-4D6B-9AB9-B4902B50DC78","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":"Q6042101$644750DE-F63E-4537-BE3E-844F65A46494","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c41b1ed5cccbbcd4ba02a605b1199f011206941d","datavalue":{"value":{"entity-type":"item","numeric-id":1045150,"id":"Q1045150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$77EF2DB4-8A00-4CF7-AB31-D13ACE7A07C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0037a94b770b923218ce260e5fa382b3caf10982","datavalue":{"value":{"entity-type":"item","numeric-id":596133,"id":"Q596133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$A5FF6004-5AC0-49B7-838C-56426F2CA2A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e58f1108d07a99592426505bb823948dca430252","datavalue":{"value":{"entity-type":"item","numeric-id":3021999,"id":"Q3021999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$16A08D38-8DBA-4BCA-A904-FF51EEB6BC87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7335ca56cba8b4de6c7536b11ad9ccea7b45a68c","datavalue":{"value":{"entity-type":"item","numeric-id":3451098,"id":"Q3451098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$842E961A-9D53-42AB-8B21-7065F3449896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9194e9b150f8488fef979658da21ddd0e60751fc","datavalue":{"value":{"entity-type":"item","numeric-id":3651735,"id":"Q3651735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$105426CA-CB68-4199-A05E-F3F90E8BD479","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83494444c3b2d9ede0fbbd18846c175a41ba77dc","datavalue":{"value":{"entity-type":"item","numeric-id":2904476,"id":"Q2904476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$1AF2B611-4404-4A56-9990-9FD0C26CBCC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c45e9deaed077304434a612a00a0cbbef29b97e","datavalue":{"value":{"entity-type":"item","numeric-id":4451072,"id":"Q4451072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$27B24575-998E-4B57-87D4-DB633216A354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b13fc59de1056ba247b8df3c3afb993eacda84d8","datavalue":{"value":{"entity-type":"item","numeric-id":5941085,"id":"Q5941085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$A9B7E0A5-398A-488A-AC53-8DF152F86526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec063e97134a956b4adef0cc993fcbb16c7d0af9","datavalue":{"value":{"entity-type":"item","numeric-id":5340253,"id":"Q5340253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$F368D1F4-E24B-4C7F-A153-EA002AFBFB46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f360828a03a8907d2a0c8e1407e4d2e8a7cc06f","datavalue":{"value":{"entity-type":"item","numeric-id":2227497,"id":"Q2227497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$E79965A9-1575-4FB1-9F2B-4962C8655520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd7fd6aeeaa277dc7624688b4de3f0a35816976f","datavalue":{"value":{"entity-type":"item","numeric-id":3449836,"id":"Q3449836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$E560989E-CD60-4319-BBA3-C822A206285E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb35b70526cb77e3d62135b1841d5ade6f0ca6c4","datavalue":{"value":{"entity-type":"item","numeric-id":1003605,"id":"Q1003605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$7A51C25D-AA21-4485-8067-5B5699F42CF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f129e91aba8d487d8704b99fd15184c126628fb7","datavalue":{"value":{"entity-type":"item","numeric-id":5377024,"id":"Q5377024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$F5DCE7E4-84EF-466F-A1B2-171B487B3811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82261ef82751cc53edb0001f9bc818cfd77a1a30","datavalue":{"value":{"entity-type":"item","numeric-id":407601,"id":"Q407601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$56325444-18F9-4A23-9F01-4CE38061FA25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df10afe79a344f89a4f1671e80204c194845ac8a","datavalue":{"value":{"entity-type":"item","numeric-id":2765957,"id":"Q2765957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$36DB6803-0A41-48F0-B196-DD2818860E30","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":"Q6042101$F3C08FD0-C604-4179-B397-ECDC2335C96B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3f87c4c86949fe1ca2ce053a7f7c5d1473c62e4","datavalue":{"value":{"entity-type":"item","numeric-id":2250458,"id":"Q2250458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$1B65A7CB-2FFE-4B6E-A10C-EC54E3BADD6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0252f70967c6c14bde1195c127c0b2878e5b76a","datavalue":{"value":{"entity-type":"item","numeric-id":1679231,"id":"Q1679231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$2B2F4919-61B2-45ED-8A7D-500E4940FC4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3692572654c639ef5216a828e344f409c1577768","datavalue":{"value":{"entity-type":"item","numeric-id":401312,"id":"Q401312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$0359BB0B-59DD-4DBB-A4DB-6D479CB7A549","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"285b0c757494623c813fbb1b3cdd0e07caf897e6","datavalue":{"value":"bafkreigyvduaeqcltigieg65uo2sxonfddomm2qxmjgfsb7rbxo5a75emi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6042101$747CADF6-3FAC-46A6-8F24-C498800BF8EF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7550ac7c7a9188c5675d0718b981a50d29ca21f","datavalue":{"value":{"entity-type":"item","numeric-id":5377024,"id":"Q5377024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7529de2a0c67d41d2cd6a39123f77c0b8b860d4e","datavalue":{"value":{"amount":"+0.840970516204834","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":"Q6042101$A12BAB1C-A368-439E-8779-028D2779A7B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c69ff3f6e4c9e7c243cdf13674b16dccf5af2d7d","datavalue":{"value":{"entity-type":"item","numeric-id":3451098,"id":"Q3451098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d34bd83e5c064eb455a2390c4237a1d69f652b11","datavalue":{"value":{"amount":"+0.8286890983581543","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":"Q6042101$7082A82C-433B-4AC1-9360-856ED0E61286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a329feaf6774804856506325ab64f9e8fdceafe5","datavalue":{"value":{"entity-type":"item","numeric-id":5150941,"id":"Q5150941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17ff966b05e0ea3d60320c1705faa8711c35d584","datavalue":{"value":{"amount":"+0.7791051864624023","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":"Q6042101$AA2F6859-972E-43B8-85D6-A4951BE02326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"613d198df692c492f4cb0c0cb2f9e5bfc4d3e6ed","datavalue":{"value":{"entity-type":"item","numeric-id":2234804,"id":"Q2234804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"718614c4840c5746db1bedbc11fb63f61d6ebfe4","datavalue":{"value":{"amount":"+0.7675650715827942","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":"Q6042101$D30AE2F2-CB67-4EBE-9DD6-2A7554D212CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7695652ccd818be21c23ca22ca54ed2005c95fa8","datavalue":{"value":{"entity-type":"item","numeric-id":2904476,"id":"Q2904476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f2d6f806e96a4aa0156079a331e4e101d1409b4","datavalue":{"value":{"amount":"+0.7598850727081299","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":"Q6042101$18A60E32-CA8D-4D59-947C-96B7EF799A83","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6042101$9AA6734E-4285-4ACE-8EF2-C302B6A01FBB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tight bound for the number of distinct palindromes in a tree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tight_bound_for_the_number_of_distinct_palindromes_in_a_tree"}}}}}