{"entities":{"Q490407":{"pageid":492174,"ns":120,"title":"Item:Q490407","lastrevid":57040767,"modified":"2026-03-26T10:00:24Z","type":"item","id":"Q490407","labels":{"en":{"language":"en","value":"Nondeterministic automatic complexity of overlap-free and almost square-free words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6476276"}},"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":"Q490407$6851D0BD-DFEF-402B-8F54-68AB83CC679D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b61a2c3f5717f1dec56fd9ab2f73039daf619008","datavalue":{"value":{"text":"Nondeterministic automatic complexity of overlap-free and almost square-free words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q490407$8B4D86A2-FC08-4312-B51C-C74AADEB176D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2c14cf2010caf52b5da3e6a5369991a90577cc29","datavalue":{"value":"1334.68173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490407$F47BBB84-1E2B-4711-AAAB-0C96471C7A4B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"afad77ebaeae38681aed326e705c8be9c0c0fe1c","datavalue":{"value":{"entity-type":"item","numeric-id":490405,"id":"Q490405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$F6256E76-F9F2-4E46-B19D-063A69631995","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"713c2f755459cde585837394c4916f4792e504e4","datavalue":{"value":{"entity-type":"item","numeric-id":490406,"id":"Q490406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$3CFD822D-7EF3-47FC-897F-EB987105E163","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":"Q490407$5652CDB9-E67C-4BCD-9BDA-9C146C24A19C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f5d7e575ce06abec1e01331d693d8d1b08ceff3b","datavalue":{"value":{"time":"+2015-08-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q490407$524029BC-2212-40E1-920F-C0D93F92F798","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"826091f60b564e5dc0148b6b45c526488c5bf264","datavalue":{"value":"https://arxiv.org/abs/1402.3856","type":"string"},"datatype":"url"},"type":"statement","id":"Q490407$ED8E0CCB-24B0-4B57-BE78-B101311D28D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"6a25a8b570833e663266cee15caf02a635b32a6d","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p22","type":"string"},"datatype":"url"},"type":"statement","id":"Q490407$2FBBE8A9-F17C-45D2-B9A6-DEF4C6DDBC11","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1fd5a710aff703acb6dd19883805baf706de3300","datavalue":{"value":"Summary: \\textit{J. Shallit} and \\textit{M.-W. Wang} [J. Autom. Lang. Comb. 6, No. 4, 537--554 (2001; Zbl 1004.68077)] studied deterministic automatic complexity of words. They showed that the automatic Hausdorff dimension \\(I(\\mathbf t)\\) of the infinite Thue word satisfies \\(1/3\\leq I(\\mathbf t)\\leq 1/2\\). We improve that result by showing that \\(I(\\mathbf t)= 1/2\\). We prove that the nondeterministic automatic complexity \\(A_N(x)\\) of a word \\(x\\) of length \\(n\\) is bounded by \\(b(n):=\\lfloor n/2\\rfloor + 1\\). This enables us to define the complexity deficiency \\(D(x)=b(n)-A_N(x)\\). If \\(x\\) is square-free then \\(D(x)=0\\). If \\(x\\) is almost square-free in the sense of \\textit{A. S. Fraenkel} and \\textit{R. J. Simpson} [Electron. J. Comb. 2, Research paper R2, 9 p. (1995; Zbl 0816.11007)], or if \\(x\\) is a overlap-free binary word such as the infinite Thue-Morse word, then \\(D(x)\\leq 1\\). On the other hand, there is no constant upper bound on \\(D\\) for overlap-free words over a ternary alphabet, nor for cube-free words over a binary alphabet.  The decision problem whether \\(D(x)\\geq d\\) for given \\(x\\), \\(d\\) belongs to \\(\\mathrm{NP}\\cap \\mathrm{E}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q490407$CA6E46A4-8201-40F0-B457-C50C3D2AD644","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490407$67CC1E82-6E83-4B20-8DE8-1C5F813734DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490407$6BDA5F6F-0F06-4A2D-BD02-B05AA20E601A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490407$BC7B06E4-F76A-4942-B624-C91FB5E33B79","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9748c36963ce1d47bb51aa26e5f6f43658a9fdcc","datavalue":{"value":"6476276","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490407$ADF99634-67F8-4A29-AFB7-1E3F26848812","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"230101dab4b11c4b0f82f0353cfbc011ef9d7f24","datavalue":{"value":"automatic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q490407$560E0A5D-0F7C-4427-AB37-6F8B24392507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"135d8aedfa48efbdf272187bb5e64a07ac5bbe92","datavalue":{"value":"nondeterministic finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q490407$81CC53E2-D8BE-4F66-9A6C-D22272C70DFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bced5d56dd0c744d17317b87dcff234b6abe752a","datavalue":{"value":"almost square-free words","type":"string"},"datatype":"string"},"type":"statement","id":"Q490407$6F0195E3-AAD8-4DB6-B2F3-E9F0F1991195","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b49d91a51e6902c9d75602a31416540f24f0056","datavalue":{"value":"strongly cube-free words","type":"string"},"datatype":"string"},"type":"statement","id":"Q490407$959F3712-9894-4699-B913-F25065954B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8967d0a934eaa6194b5afbe1fbb4e78c8127645d","datavalue":{"value":"combinatorics on words","type":"string"},"datatype":"string"},"type":"statement","id":"Q490407$4F5FE44E-CFD3-4A91-96A7-38DD170C4C26","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":"Q490407$FE2E39DA-DADF-49D1-8B47-0D22E84D0F89","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a905b90013a6e6ae75ac23fe1a913b80b559a6cb","datavalue":{"value":{"entity-type":"item","numeric-id":719308,"id":"Q719308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$18C4D746-5912-4815-8AD1-1719777AED89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45131a38ff53f12b9952d52e2962c28740fef2f7","datavalue":{"value":{"entity-type":"item","numeric-id":3161424,"id":"Q3161424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$47FB49A8-AF77-488F-8A8E-7E3C08799E6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eba8ed73dd1b442c38aeee6c8a4684d89ee39d7b","datavalue":{"value":{"entity-type":"item","numeric-id":1346736,"id":"Q1346736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$10BD5FC7-AFF4-475B-8901-35D759F15EE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b91a481ff7e05f4785cd2c3cc63e4cdc5bce3f94","datavalue":{"value":{"entity-type":"item","numeric-id":5537777,"id":"Q5537777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$2E036D80-9871-4361-A79C-BEF3E591897C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55ca34fe94cbf494863af77ec148aceea3d9965b","datavalue":{"value":{"entity-type":"item","numeric-id":775458,"id":"Q775458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$628486E7-C8F8-436D-AE17-B2DB41AF3C57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"434e737e41daaa416c48d5d7f2e1390af29737e0","datavalue":{"value":{"entity-type":"item","numeric-id":538176,"id":"Q538176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$37DB5B2B-03D2-44E0-A9DF-1D317FEC4954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f99d516f03f630b465144bf2edfacff7e586661f","datavalue":{"value":{"entity-type":"item","numeric-id":3549457,"id":"Q3549457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$19C5AAB0-E5DF-4A56-9AD9-FB13CD87D373","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b8425e8209e6312a4bbffa91ef01a2b5e5a251f","datavalue":{"value":{"entity-type":"item","numeric-id":4531381,"id":"Q4531381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$6B4D0E79-F40A-4153-B0BE-82ECFD4D16F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e44b03369583618c105fb1dde9ef9f92bbe3a85","datavalue":{"value":{"entity-type":"item","numeric-id":2266018,"id":"Q2266018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490407$35A3250E-E9C1-48B3-8D10-2BB75A029A22","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"8db1bb5f6732dc84f12f5bb1a43d91331c6ef16f","datavalue":{"value":"bafkreia77txjkcpnj37fguzqwo64bcmbxeam2hraanss3dmmrbwrhzgxca","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490407$CA86F2E0-F288-4E14-98A0-BD1FD4C48434","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18407251d37920a2e4d0ffba5a47a8cb72705189","datavalue":{"value":{"entity-type":"item","numeric-id":2920445,"id":"Q2920445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88af6c2fb4c14acaf1e7e6b28390859ce9804ae4","datavalue":{"value":{"amount":"+0.9646751284599304","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":"Q490407$2FA8FB31-4055-4C41-A944-905FA328DC7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbdbf9ecdc39011c9a06a4e7f6721849a75c398b","datavalue":{"value":{"entity-type":"item","numeric-id":1694011,"id":"Q1694011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1086777bca31638a62a8dddb48aff4d6d2770a40","datavalue":{"value":{"amount":"+0.7889003157615662","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":"Q490407$48DF0AF7-60D2-4784-B279-37484A7353DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66d26529991990e0f1a963fe6b0717d87c7da7fa","datavalue":{"value":{"entity-type":"item","numeric-id":2217496,"id":"Q2217496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb41015f8bba811a063e4a69597aebcabc1fa513","datavalue":{"value":{"amount":"+0.7702417373657227","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":"Q490407$7F5DB5E3-797B-4D7E-B4D5-628C52A78773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be277dcd1da5b6dbb50ee82ef5436bfe74a91d4b","datavalue":{"value":{"entity-type":"item","numeric-id":1816738,"id":"Q1816738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98ccf01afa71a04627e45838ee93c28c860905c8","datavalue":{"value":{"amount":"+0.7687475085258484","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":"Q490407$FDAC5E61-7594-4736-8AB3-4B23B6E68E57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4de9add70b68fb60f7e80ca8df114037746a04e","datavalue":{"value":{"entity-type":"item","numeric-id":1390867,"id":"Q1390867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44251cb91ee5a667b6c624d291c38582f622fff3","datavalue":{"value":{"amount":"+0.7577453255653381","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":"Q490407$E9E4E88F-AD43-4903-9725-9AA8D17DE45B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:490407","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:490407"}}}}}