{"entities":{"Q2515571":{"pageid":2526314,"ns":120,"title":"Item:Q2515571","lastrevid":72750957,"modified":"2026-04-14T07:31:20Z","type":"item","id":"Q2515571","labels":{"en":{"language":"en","value":"Generalized de Bruijn words for primitive words and powers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6470567"}},"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":"Q2515571$01E0AF30-035F-4EA4-9860-FD5ACBDCB8B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b31604a93bbcab804fe36e268b32b6c4b9afece","datavalue":{"value":{"text":"Generalized de Bruijn words for primitive words and powers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2515571$74ED169E-C811-4655-A75F-0CF134101238","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"22f49b98048a1604b69d5b8ccd14979c33bf783f","datavalue":{"value":"1328.68153","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515571$26E45E7C-C40C-4E7E-B156-BDEB737CDEBC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$1F7EDAFC-CC7A-4919-9907-BFD4FA310794","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"143a47b7cf174256ac299daaf18bbff0086c7a43","datavalue":{"value":{"time":"+2015-08-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2515571$A17A4E86-9936-4FBC-A8E3-12D76F81F344","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"95d29ee1fe0f13b3c042316cd4b24e59ceedf596","datavalue":{"value":"https://arxiv.org/abs/0904.3997","type":"string"},"datatype":"url"},"type":"statement","id":"Q2515571$424F3373-590F-4EBF-A4A7-0508FE005B20","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"da6875ff994e02d2d936aa7b3075cc73f5b02149","datavalue":{"value":"Let \\(\\Sigma_k=\\{0,1,\\ldots,k-1\\}\\), and let \\(\\Sigma_k^n\\) be the set of words of length \\(n\\) over \\(\\Sigma_k\\). For every subset \\(\\mathcal{D}\\) of \\(\\Sigma_k^n\\), a (generalized) de Bruijn word for \\(\\mathcal{D}\\) is a word over \\(\\Sigma_k\\) containing as a circular factor every word of \\(\\mathcal{D}\\) exactly once, and no other words of \\(\\Sigma_k^n\\) [\\textit{E. Moreno}, Inf. Process. Lett. 96, No. 6, 214--219 (2005; Zbl 1184.68323)]. A famous theorem of \\textit{H. Fredricksen} and \\textit{J. Maiorana} [Discrete Math. 23, 207--210 (1978; Zbl 0384.05004)] states that concatenating all Lyndon words over \\(\\Sigma_k\\) of length dividing \\(n\\), in lexicographic order, results in a de Bruijn word for the set \\(\\Sigma_k^n\\). The main result of the paper is the proof of the following statement (attributed by the author to Michael Domaratzki) that is strictly related to the theorem of Fredricksen and Maiorana:  {Theorem.} Concatenating all Lyndon words over \\(\\Sigma_k\\) of length exactly \\(n\\), in lexicographic order, results in a de Bruijn word for the set of primitive words in \\(\\Sigma_k^n\\).  The paper also contains a number of interesting results related to the main result, as well as algorithmic considerations about the generation of generalized de Bruijn words.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2515571$829F1A80-5FA8-465E-8F9F-E699DA80B0E0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"130d97dc1ca643e8efa64f9b07a28af4e0a2454b","datavalue":{"value":{"entity-type":"item","numeric-id":243831,"id":"Q243831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$3E411724-313A-49CE-9C4B-A4F1DA6809C3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515571$46532E39-085E-4365-BF79-8F0ED8466B1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515571$49AA7E7A-6D7D-47B0-A641-A1DD9B6E107C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"adea558de1ef7c16ea5b06db3ae3ddec708aa0e8","datavalue":{"value":"6470567","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515571$6FB98F72-ADA5-4955-9243-BD842A700F65","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1107ab5a4e5e5d78c39b214167705a7a34be04f","datavalue":{"value":"primitive words","type":"string"},"datatype":"string"},"type":"statement","id":"Q2515571$CC1AA126-204E-48FA-986C-30D088E1BF24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"087b5e70a21bc40edf5dde20c50ef6015125811d","datavalue":{"value":"de Bruijn words","type":"string"},"datatype":"string"},"type":"statement","id":"Q2515571$A7686176-6248-4BE4-B885-26DCD44FBE9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f248a4a504a499f931ffd5eabb8da7e87c1fbc32","datavalue":{"value":"de Bruijn graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2515571$4DD09CEB-0112-418E-92F6-76C6D9AE1708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09314b97c41035fd5c3138a114d545fb151a9c95","datavalue":{"value":"Lyndon words","type":"string"},"datatype":"string"},"type":"statement","id":"Q2515571$FE23BF75-E36F-4AB5-B6B8-B3044984B162","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6eecb52206f1310d4747480a4506ebedbb48e1c1","datavalue":{"value":{"entity-type":"item","numeric-id":1662112,"id":"Q1662112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$1E0C57FE-2B62-4419-9C89-EBF1AE466249","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":"Q2515571$9E33E136-CEFB-4258-ACC1-CA9260B23636","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4b0339539e66a06ec9c23b082e622e1294eb6206","datavalue":{"value":"W2963757710","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515571$A83DF135-E1A5-40BF-8B34-65BA12E731B1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6e1b6447be55f98ecfda9742a6b8cdb343d4afd","datavalue":{"value":{"entity-type":"item","numeric-id":3057811,"id":"Q3057811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$4EF9B10E-4538-4EDB-A391-E8558CF6086B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49b536973b4a33f644acb320f456d57311decf8b","datavalue":{"value":{"entity-type":"item","numeric-id":1044740,"id":"Q1044740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$96D3C1FE-006E-4003-9EF5-F6D844036CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61d80e91c73bc0301cc40457009380a612f4a5c1","datavalue":{"value":{"entity-type":"item","numeric-id":1208348,"id":"Q1208348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$35119800-ADFB-4D54-B76E-717FACDD3F83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a66cc7dddb3f00e8215ee9f0e3b79e5898c60c5","datavalue":{"value":{"entity-type":"item","numeric-id":4020354,"id":"Q4020354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$4E46B581-65E2-4013-AD1B-A6F6F2EE424C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6677725adbb0d74b2adf9337d70f1369f9f0ab5","datavalue":{"value":{"entity-type":"item","numeric-id":3940837,"id":"Q3940837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$9BF7F95B-8674-4F81-BA01-8846C7D8ED1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b17648008f83f710ec86a5e65f2569a080aa45f","datavalue":{"value":{"entity-type":"item","numeric-id":1248514,"id":"Q1248514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$12D3EE67-1E8D-46F3-9666-EC4B93F8C9D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"636b1cb6e28ebc758de77cc69e0b7551ef745825","datavalue":{"value":{"entity-type":"item","numeric-id":1121024,"id":"Q1121024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$7DE449CB-A39F-44D1-ADC9-EE6A81C8A9EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cac7a3c526e18207f0183e3e7646e5e10e5b599","datavalue":{"value":{"entity-type":"item","numeric-id":3808023,"id":"Q3808023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$070A473A-C276-435A-84B5-52A220D657DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a350a646df05af2cd765c289d28ce10d45e83b7d","datavalue":{"value":{"entity-type":"item","numeric-id":5834367,"id":"Q5834367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$5CF1BEAE-6046-4919-9D06-F58E424AFED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"817506d139757f82a084bcf8a757a810a95d7d77","datavalue":{"value":{"entity-type":"item","numeric-id":1044883,"id":"Q1044883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515571$7BF43BB2-AD4F-4B37-B9DF-2A196D638635","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7393936f8e5d337951a66ee2af4041a8b9f246c5","datavalue":{"value":"10.1016/J.DISC.2015.05.025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515571$362C5B31-D276-429C-9623-C34907C14655","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4082258fd99a17da18038c989e7c8b72df6d85d","datavalue":{"value":{"entity-type":"item","numeric-id":1704583,"id":"Q1704583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07dac2c085b02e0acc332f1672849ed6d6bd18e8","datavalue":{"value":{"amount":"+0.7480186820030212","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":"Q2515571$BC4EA8C8-6DB2-45E0-A346-88D6EC1653F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20aa92a2f7ba1eb4f641ff7a192f0b00d244541e","datavalue":{"value":{"entity-type":"item","numeric-id":4835097,"id":"Q4835097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d4dc3cfeb514a681cb6c7738b448db29d796537","datavalue":{"value":{"amount":"+0.7468143701553345","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":"Q2515571$253556E1-0DEB-435D-BCDE-4C9F7DC63C2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3de1e6b8c97255cc8fb614ca3537ebc174d10367","datavalue":{"value":{"entity-type":"item","numeric-id":4902891,"id":"Q4902891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b641aa03f38691dce7dc545d14b9f9dc35f9637a","datavalue":{"value":{"amount":"+0.7463454604148865","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":"Q2515571$650FB42A-73C1-44BB-B8D0-ABFA39E51C56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c002938c94782c8ef5eb0b42de0338c0d014deea","datavalue":{"value":{"entity-type":"item","numeric-id":5740425,"id":"Q5740425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56445ebaf041c99dfcac429f8c4fb49173326f02","datavalue":{"value":{"amount":"+0.7456425428390503","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":"Q2515571$B7A05276-7BA0-4465-A968-07B39A95BD9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89475ffad0a6e00e1b22711c6bdbe5eb657e4622","datavalue":{"value":{"entity-type":"item","numeric-id":1044740,"id":"Q1044740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6491a8959667dd0edbfa63b95b249d5a198ea9a","datavalue":{"value":{"amount":"+0.7387059926986694","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":"Q2515571$D372498F-014F-49C7-BD8A-E4B7916245BB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized de Bruijn words for primitive words and powers","badges":[]}}}}}