{"entities":{"Q1121031":{"pageid":1131780,"ns":120,"title":"Item:Q1121031","lastrevid":66172872,"modified":"2026-04-12T08:02:04Z","type":"item","id":"Q1121031","labels":{"en":{"language":"en","value":"Enumeration of irreducible binary words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4102505"}},"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":"Q1121031$C394C4DC-D02F-4E3B-B9BC-66AEE169314E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"693094765557a2b0ab477bf69a46c34b7e580696","datavalue":{"value":{"text":"Enumeration of irreducible binary words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1121031$E20BA3BD-464F-4E84-9C87-DF42E0F64028","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"56b302c9455e5539216d4bf48492d6a0dd9f0710","datavalue":{"value":"0673.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121031$2094896B-5673-4A16-B62A-52A5D2900AEC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"af2f3065b6aa37826153e509b04bcd02a3e90afc","datavalue":{"value":"10.1016/0166-218X(88)90078-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121031$025B24F2-06BB-4FD3-BECB-3A7F68B19C11","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0189ea284dbeb4d1811a67b9a764a86b15f50c48","datavalue":{"value":{"entity-type":"item","numeric-id":441852,"id":"Q441852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121031$1837F224-EB16-48FA-97A7-19332F1A3410","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121031$C9D9E09D-9BAA-4B0B-9639-0A6F8D19719D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1121031$BF532F13-A235-4CBA-9C94-D80E13F0ED8C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"897de3cbc95c3fc54bdbc2dfbb3fc88b4d00989b","datavalue":{"value":"Denote by \\(\\Sigma^*\\) the set of (finite, binary) words over an alphabet \\(\\Sigma =\\{a,b\\}\\). For a language L over \\(\\Sigma\\) the density \\(d_ L(n)\\) is defined as the number of words in L of length n.    Let \\(\\Sigma^{\\omega}\\) be the set of infinite words over \\(\\Sigma\\), i.e. of infinite (binary) sequences \\(a_ 1a_ 2...a_ n..\\). with all \\(a_ i\\in \\Sigma\\). A word \\(x\\in \\Sigma^*\\cup \\Sigma^{\\omega}\\) is called irreducible if it is overlap free, i.e. it has no subword of the form yyc, where y is a nonempty word in \\(\\Sigma^*\\) with the letter c, \\(c\\in \\Sigma\\), in the first position. A word is said to be irreducibly extensible if it is a left factor of some infinite irreducible word. Denote B the language of all irreducible words over \\(\\Sigma\\) and let \\(\\bar B\\) be the language of all irreducibly extensible words (over \\(\\Sigma)\\). Accomplishing some investigations of \\textit{A. Restivo} and \\textit{S. Salemi} [Combinatorial Algorithms on Words, NATO ASI Ser., Ser. F 12, 289-295 (1985; Zbl 0604.68100)] the author shows here that the irreducible binary words grow slowly - he proves (Th. 16) that there is a constant C such that \\(d_ B(n)<Cn^{1.587}\\) for all \\(n>0\\). He proves also (Th. 8) that there exist positive constants \\(C_ 1\\) and \\(C_ 2\\) such that \\(C_ 1n^{\\theta}<d_{\\bar B}(n)<C_ 2n^{\\theta}\\) for all \\(n>0\\) with \\(\\theta =\\log_ 2\\xi =1.155...\\), where \\(\\xi =2.226..\\). is the positive root of \\(x^ 4-2x^ 3-x^ 2+2x-2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121031$DFCE3139-0F60-4E23-A07B-88A404553B8C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121031$C839FC75-26F9-44EE-84AE-BBD5F4AAFC53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121031$FCA2DBD2-D2ED-43D2-8817-D2B628BD9D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121031$D36FB84B-72F5-4A64-A931-98320471404A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dc46b9b3e29edb0a0a0cebf3b3a1a9857779110c","datavalue":{"value":"4102505","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121031$095719A3-E494-4262-B2F8-5D033F6B5729","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01b6b0a8f3bdbe79649aeb5da44f04786e3abb40","datavalue":{"value":"irreducible binary words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121031$29F5B0FB-BC42-4F71-A27B-30C0D7E90FEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7742560bc6b514c48466087fc96d1e7475bc25a7","datavalue":{"value":"density of language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121031$81AB6486-EC80-43FC-A2CF-3197A092FD97","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"20533fcc7734c324d16abc2a4c8c149f15b6ddad","datavalue":{"value":{"entity-type":"item","numeric-id":1372655,"id":"Q1372655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121031$F2031F54-5158-4206-938C-309F2859DEAB","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":"Q1121031$D0101699-0482-43B5-84A7-C9736B56830D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dabd89d1650a3f66c63265a24f19cdd05b83a51","datavalue":{"value":{"entity-type":"item","numeric-id":1838047,"id":"Q1838047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121031$613C1C58-5437-4FDC-B08D-6B6E3705B822","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05391693ed4a5625f932e2db56d74fe52d21540b","datavalue":{"value":{"entity-type":"item","numeric-id":3914998,"id":"Q3914998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121031$4EE59278-4FD2-43DB-A86C-A1F70CE46185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edf3005b7670eb623d7b5a68242619e9bfdb9fa6","datavalue":{"value":{"entity-type":"item","numeric-id":1078338,"id":"Q1078338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121031$AF3E6DB0-6A2D-44E1-86D6-15182650F866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4cb141e01e3729ccc2ed44ca61e28ed0018c2f3","datavalue":{"value":{"entity-type":"item","numeric-id":5581642,"id":"Q5581642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121031$716A4248-3675-432D-9F4E-D3D3E16369B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20d91af4c0ac2900e53cae10e8db9e393340ca32","datavalue":{"value":{"entity-type":"item","numeric-id":2653273,"id":"Q2653273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121031$66BDDFA5-FDFA-4961-8EBA-59CAE06C38C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"677f874a17ed0c9c190e690a1f6a11ca44e356b2","datavalue":{"value":{"entity-type":"item","numeric-id":3741097,"id":"Q3741097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121031$CE66B381-A0B8-4CF0-BD48-A5A41082D9BE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a01db6d70888376a678a469add94dbd62444fea2","datavalue":{"value":{"entity-type":"item","numeric-id":610578,"id":"Q610578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b34bc3b44e61afb10baf11786849a7021c74f59","datavalue":{"value":{"amount":"+0.76477253","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121031$27BAA73F-CACA-4710-89AC-CCB58472C446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c14a8a58f9d4fce682a87972b346361f0f259eb","datavalue":{"value":{"entity-type":"item","numeric-id":1678349,"id":"Q1678349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65ceafff8edb855bbe5444477f0c355f82c10b08","datavalue":{"value":{"amount":"+0.7574643","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121031$ADB761D8-2A11-414F-899F-09F421AECACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84ea3b3b5250b654555d2b441b0914e88a942b4d","datavalue":{"value":{"entity-type":"item","numeric-id":4412109,"id":"Q4412109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0223856a770ab99da5880b1f80fdcdb7079b7354","datavalue":{"value":{"amount":"+0.74862665","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121031$5045BC8A-0948-4D0A-BB5D-F83D543F33FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d2dce3314538e87c752c6e4fda65fa7ff3d8d5c","datavalue":{"value":{"entity-type":"item","numeric-id":4289940,"id":"Q4289940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f1dec43f0817ca4af7caef865cd9b1bbc94ed18","datavalue":{"value":{"amount":"+0.746722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121031$65F03FB0-73AC-4D60-BAE5-88718685263D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46aa54644118f9de9b7919400f9041370559aa9e","datavalue":{"value":{"entity-type":"item","numeric-id":650879,"id":"Q650879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d52ac35d0793cada16540f374bf24da964143aab","datavalue":{"value":{"amount":"+0.7445104","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121031$87199DB8-3BD9-4CA8-B077-B429CF450B15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"111ad72c3075f3359c6211cbcab2b26572fc7692","datavalue":{"value":{"entity-type":"item","numeric-id":3428618,"id":"Q3428618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6633de9861cc9a012eec56b956efd00fec01b892","datavalue":{"value":{"amount":"+0.7424766","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121031$9C034DB0-38F2-40F5-9093-B055AA5E2398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d75120d842ea9612103a823e3709ac513705cd2","datavalue":{"value":{"entity-type":"item","numeric-id":1010692,"id":"Q1010692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f4c832bbebb6f86498e996e398a13b6c02bccdf","datavalue":{"value":{"amount":"+0.7388269","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121031$D62AE62D-3C23-44B9-A257-1A2A79CEC7A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fa361e7b0a8dcc1c784dd1b22424bd8116b954d","datavalue":{"value":{"entity-type":"item","numeric-id":5756719,"id":"Q5756719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36b013b24be04eaaee457ba9bf10d25c89773598","datavalue":{"value":{"amount":"+0.73843414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121031$BC4F2B25-D958-4CCB-85F7-A4CE0A7426A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97d4a06fbc58590b51ce70de3806f6af78672795","datavalue":{"value":{"entity-type":"item","numeric-id":1078338,"id":"Q1078338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d46c42c2c56462b878cfbede6ecda57809973f60","datavalue":{"value":{"amount":"+0.7377289","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121031$50895E25-4E55-4C3C-BBA2-931B2A63DD20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fda676275aab97f5f546af49b0818c724c87ac7","datavalue":{"value":{"entity-type":"item","numeric-id":598459,"id":"Q598459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"214166b72d3f3e4e8fafd3e6bf87adb26acd3871","datavalue":{"value":{"amount":"+0.7348542","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121031$E7E960F2-55E5-481E-BCE0-C9AF11E201B7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Enumeration of irreducible binary words","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Enumeration_of_irreducible_binary_words"}}}}}