{"entities":{"Q2318478":{"pageid":2329221,"ns":120,"title":"Item:Q2318478","lastrevid":57851472,"modified":"2026-04-02T19:31:57Z","type":"item","id":"Q2318478","labels":{"en":{"language":"en","value":"Nyldon words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7094556"}},"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":"Q2318478$E58BCDD7-C9CB-4284-A2BC-25DC063763D7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"12b27a88304da3b6b96d0f3bd68a3d23b7ff3a40","datavalue":{"value":{"text":"Nyldon words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2318478$6AAE1AF2-C1B8-4CF9-8B47-D5696722946A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b6f7417596570c28e09236a433200463d7847290","datavalue":{"value":"1419.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2318478$681D255E-3A25-4DA2-885A-5F49880CED6D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9f4279b04f6e4a7201c2ad8656a4e55dccc850c","datavalue":{"value":{"entity-type":"item","numeric-id":272349,"id":"Q272349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$53F8D428-B068-4102-8859-E8FCCA1AF1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"981c119a576bb5542f158647c7b3474b2adcd47f","datavalue":{"value":{"entity-type":"item","numeric-id":785579,"id":"Q785579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$3CFD870B-543C-4D29-89F1-08815D10B0A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ca309d2c74d9288d58c40dc2fe26577e2c1b1ae","datavalue":{"value":{"entity-type":"item","numeric-id":308969,"id":"Q308969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$150CB629-4017-4557-A253-0C7F618A257A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$345D9E9B-B01E-4B8F-9DA0-6863DA53AC4B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"77fd9504ab9f9a1d017ec97a7cdec039d17298a2","datavalue":{"value":{"time":"+2019-08-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2318478$BDD3408A-9641-4631-A60D-6B8F78AA5ADC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"725bb9757b55dd7304eac4692bf37370941b12a1","datavalue":{"value":"https://arxiv.org/abs/1804.09735","type":"string"},"datatype":"url"},"type":"statement","id":"Q2318478$3C00814D-1179-457B-B7E0-BEF7BC04DD16","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"50ed1250eb4f2e09df14985affa4778b521b262c","datavalue":{"value":"Consider a totally ordered alphabet. A Lyndon word is a non-empty word that is less than all its conjugates (i.e., cyclic shifts). They are of significant importance in algebra, combinatorics and computer science.  In particular, the so-called Chen-Fox-Lyndon theorem states that every finite word can be uniquely factorized as a lexicographically non-increasing sequence of Lyndon words. This theorem can be used to recursively define the family of Lyndon words.  In a Mathoverflow post, Darij Grinberg defined Nyldon words by reversing the lexicographic order: letters are Nyldon; a finite word of length greater than one is Nyldon if and only if it cannot be factorized into a non-decreasing sequence of shorter Nyldon words. Nyldon words of length up to \\(4\\) are: \\(0\\), \\(1\\), \\(10\\), \\(100\\), \\(101\\), \\(1000\\), \\(1001\\), \\(1011\\).  In this paper, the authors study in detail these words, their prefixes and suffixes. They show that the uniqueness of the Nyldon factorization implies that there are equally many Nyldon and Lyndon words of each length. Nyldon words are greater than all their Nyldon proper suffixes. This implies that Nyldon words form a complete factorization of the free monoid with respect to the decreasing lexicographic order. They also provide algorithms for computing the Nyldon factorization of a word and for generating the Nyldon words up to any given length. Nyldon words are primitive, and each primitive conjugacy class contains exactly one Nyldon word. The paper ends with a discussion of the connections between Nyldon and Lyndon words.  The interested reader will also find several problems that are left open.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2318478$21E9DD7C-A376-44D5-AD9F-49DCCA49DFB0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ee087b51e799847d019fb8239a9d1ca2f0176191","datavalue":{"value":{"entity-type":"item","numeric-id":236475,"id":"Q236475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$4C737F29-1B9F-4752-BCD8-D11943E1280F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2318478$488F6CBF-1ABA-4651-ADCF-27DE7B385F1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf807832f23b1843158a0f1abb6a671308ea384a","datavalue":{"value":"94A45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2318478$4587B75A-7223-48E7-8E52-1E6A91E93F2C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"689f0f385a75685e0c68085a6dd0973c6c3294aa","datavalue":{"value":"7094556","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2318478$89482A6F-D063-45C0-922D-DFE795229F0C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09314b97c41035fd5c3138a114d545fb151a9c95","datavalue":{"value":"Lyndon words","type":"string"},"datatype":"string"},"type":"statement","id":"Q2318478$E235BD11-966C-45BB-95BB-BD3C44F2505F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3ee359d3ae84aea24a05766eeec2520a86d9983","datavalue":{"value":"Nyldon words","type":"string"},"datatype":"string"},"type":"statement","id":"Q2318478$F95C6011-A599-48EC-91D5-5F25D5822EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd72db670fa3e553b949c49f80dfeaf439ba160a","datavalue":{"value":"complete factorization of free monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q2318478$FC6D5DED-642E-4FAD-96BB-F4551F48EAB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b754bfb251506dc6406afc6eaa49d567495cddb","datavalue":{"value":"Lazard factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2318478$AF516E74-BCEF-4EFB-B058-9690D9F53A48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08f3dc63f3b03400b725db7435aa7658595e734b","datavalue":{"value":"Hall set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2318478$AAE26252-A166-4098-BE1F-58079F40B024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5928234132235ea5d37c8429c9bc0339a75e827","datavalue":{"value":"comma-free code","type":"string"},"datatype":"string"},"type":"statement","id":"Q2318478$06088DE9-7356-4C66-80AD-767028E3E1F6","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":"Q2318478$CDDC1AEC-C980-4466-9072-AE074DBDD1A2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aae51aa61b06fe1b8d663a48c312cc5257c60cf6","datavalue":{"value":"W4206321061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2318478$99AA713B-0B2D-4F6A-A9AD-5E3C13D6A1E1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd78372e0fcd4293cba3913fb4a82b790ace9fa0","datavalue":{"value":{"entity-type":"item","numeric-id":373877,"id":"Q373877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$85DF26D1-5DFB-471E-85DA-0A3CB628E034","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c48a07edd90b543e8fca3958d14fe3adcd0e294","datavalue":{"value":{"entity-type":"item","numeric-id":1795498,"id":"Q1795498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$CC9B3522-BA86-4668-85B2-C4D29309ED6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5f9f511e34248330ddf4a7e19dbda3bcb27b59d","datavalue":{"value":{"entity-type":"item","numeric-id":872058,"id":"Q872058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$D59B9ABB-756E-423F-90FD-EF1022DF79FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0592af5fe25ccc461c687f381693281f8c96c11f","datavalue":{"value":{"entity-type":"item","numeric-id":3653240,"id":"Q3653240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$61067C5D-7F52-4AE8-AEAB-CB6C8C1F50C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7270e81e9d40062b04e29b8020c1a02f9c10feba","datavalue":{"value":{"entity-type":"item","numeric-id":5920757,"id":"Q5920757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$B6D432EA-91D2-468D-8E83-AC3B453DEC42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99627d0a96e3b61b0ecca4f33b58ced384cb3b50","datavalue":{"value":{"entity-type":"item","numeric-id":3315005,"id":"Q3315005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$C3F4636C-44AB-4274-9149-4BA011168CB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c79e0895cef6511a66f2f69942b4b62dbc4d4823","datavalue":{"value":{"entity-type":"item","numeric-id":2957449,"id":"Q2957449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$1B77DD3B-D109-43CB-B707-3D942852F9D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42b10886ca8b4810e91e18ed9a8c6b352daf84dc","datavalue":{"value":{"entity-type":"item","numeric-id":4341774,"id":"Q4341774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$222A9DB8-8A68-4763-A761-85AA2820B237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bbd318db82020f0f4be7694aefe03518816283a","datavalue":{"value":{"entity-type":"item","numeric-id":1185905,"id":"Q1185905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$8CEDFE8B-DD05-4506-83C4-ABB90FA0A543","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8003ef594afae5d736db1c7e9aa39733a05a6410","datavalue":{"value":{"entity-type":"item","numeric-id":2411623,"id":"Q2411623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$39D1E2DB-89DD-48D1-B0DA-9D60CE17FF5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dca9bfd9278fe94406b0eb6d8a19d3c3d83dd58f","datavalue":{"value":{"entity-type":"item","numeric-id":3134850,"id":"Q3134850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$55A822C4-88E4-4182-A5D5-2E38143986E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd1d433cc72240116b614609bc1ff9db015f64ca","datavalue":{"value":{"entity-type":"item","numeric-id":5623900,"id":"Q5623900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$432BDAF5-778E-479E-A31B-9E9B56432056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b742148900482b1b92a3d19352e4baabc645466e","datavalue":{"value":{"entity-type":"item","numeric-id":5522249,"id":"Q5522249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$3ECAF957-F202-4BBC-85EE-B9F40BA4B97A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3858289a6a5ccfa12fe3bfe8c28e37abd1e93d13","datavalue":{"value":{"entity-type":"item","numeric-id":1252929,"id":"Q1252929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2318478$49A59FDC-63D6-41D8-8067-5575C75CF6B1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5f5f2269be96420bbf5d8b89428f2a17d06f5003","datavalue":{"value":"Q127977283","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2318478$4B017A7B-5B12-4482-A259-1EF00B6BEE81","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e90dbdc3bd563f0b0e84945d07336ebeba728a16","datavalue":{"value":"10.1016/J.JCTA.2019.04.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2318478$7A052169-FFDF-4D1C-87EE-B04B9C8384AC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"163e1b287324eece4dd7979a6b7402816a68a214","datavalue":{"value":{"entity-type":"item","numeric-id":820920,"id":"Q820920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45e08c1f1f778ea7717c6916ee5c15f1a2e6066d","datavalue":{"value":{"amount":"+0.8960041403770447","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":"Q2318478$9123874E-C3DE-48D1-94EA-ABF9C2A03CAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39c6acd9b04378741cc5c898b8bf2f136184e24d","datavalue":{"value":{"entity-type":"item","numeric-id":2422029,"id":"Q2422029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d575f1f68276f96d0ab7d70e0447f5d4f94f178b","datavalue":{"value":{"amount":"+0.8182961940765381","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":"Q2318478$F2BADB95-ABEB-4184-A36C-5F7E8B9A8F1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ef9cf33160cf3464a262cd79fcb39599293ebe5","datavalue":{"value":{"entity-type":"item","numeric-id":1121024,"id":"Q1121024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d47e624a7da81b0fe5a455cf1b29a7ee6d72c186","datavalue":{"value":{"amount":"+0.8018448948860168","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":"Q2318478$87045AB2-F40A-41BB-A5FF-D660F0482814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20fbbae8f6eb76703ab86d49d2fca69a5baa52ed","datavalue":{"value":{"entity-type":"item","numeric-id":5140264,"id":"Q5140264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"301fcc1e78425724290f01e918eb4e7640514b65","datavalue":{"value":{"amount":"+0.794146716594696","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":"Q2318478$F4E00090-04AC-4F00-B75A-5EB44748E83F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0d47e95270f6ce0b4350cc512c9beedae37ad71","datavalue":{"value":{"entity-type":"item","numeric-id":3451100,"id":"Q3451100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e682a0277101b018ba082cec003194809b67469","datavalue":{"value":{"amount":"+0.792679488658905","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":"Q2318478$12F19A2E-E5A2-4D3F-9E92-5EA3F03BA500","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2318478","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2318478"}}}}}