{"entities":{"Q1743715":{"pageid":1754457,"ns":120,"title":"Item:Q1743715","lastrevid":73602345,"modified":"2026-04-14T16:36:52Z","type":"item","id":"Q1743715","labels":{"en":{"language":"en","value":"Avoidability of circular formulas"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6859911"}},"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":"Q1743715$211EE415-31F8-4D66-B017-7042BE0AA2B2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1166aa30286289f6ce6f5bda67e57523138d7697","datavalue":{"value":{"text":"Avoidability of circular formulas","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1743715$6143224D-FEFD-4794-97F5-8A08DA3467CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"493dbdb228d208d10e49e6c9a516ac40aaaded1b","datavalue":{"value":"1393.68142","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743715$E72696B5-51FA-4295-85FE-647A9E72175A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38ef63f5672abdc059f6fa730c4a3f495dd41d04","datavalue":{"value":{"entity-type":"item","numeric-id":344538,"id":"Q344538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$2F067DCE-B72C-41F1-83A9-631B4BAC5C04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b3826c52088f4aa88f5af749aa0df3944c777e9","datavalue":{"value":{"entity-type":"item","numeric-id":244933,"id":"Q244933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$07CF3878-B217-463B-9891-AE5B49697EF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9b44b65dea73fc422dc7dcbaf4185327c345abf9","datavalue":{"value":{"entity-type":"item","numeric-id":344539,"id":"Q344539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$06148D70-76D7-437B-AEE7-D787855EF509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb377fbac44db69ba11902b3e6a80e3a57780b1b","datavalue":{"value":{"entity-type":"item","numeric-id":223812,"id":"Q223812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$C2316AD7-4232-4BFB-961B-DC24BEA57CEB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$2D329AC3-B728-4699-8617-61AC3859AB66","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cebd514f10184b17197e759da0a7f95e6df8d514","datavalue":{"value":{"time":"+2018-04-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":"Q1743715$891E306F-16C1-4E59-9264-0E9C7B354311","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e9a696c1fb94aff32c05f371137bf2927e2d5748","datavalue":{"value":"https://arxiv.org/abs/1610.04439","type":"string"},"datatype":"url"},"type":"statement","id":"Q1743715$EBBAAD1B-230E-4111-844B-8C869CE814AF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aad82c7026bf17eae4da390f78b4be1212bc0cd2","datavalue":{"value":"A pattern \\(p\\) is a non-empty finite word over an alphabet \\(\\Delta\\) of variables. The formula associated to \\(p\\) is obtained by replacing every variable that appears only once in \\(p\\) by a dot. The factors between the dots are called fragments. An occurrence of a formula \\(f\\) in a word \\(w\\) over an alphabet \\(\\Sigma\\) is a non-erasing morphism \\(h:\\Delta^\\ast\\to\\Sigma^\\ast\\) such that the \\(h\\)-image of every fragment of \\(f\\) is a factor of \\(w\\). The avoidability index \\(\\lambda(f)\\) of a formula \\(f\\) is the smallest size of \\(\\Sigma\\) such that an infinite word over \\(\\Sigma\\) contains no occurrence of \\(f\\).  The circular formula \\(C_t\\) is the formula over \\(t\\geq 1\\) variables \\(A_0,\\dots, A_{t-1}\\) consisting of the \\(t\\) fragments \\(A_iA_{i+1}\\dots A_{i+t}\\) such that the indices are taken modulo \\(t\\). Thus, \\(C_1 = A_0A_0\\), \\(C_2 = A_0A_1A_0.A_1A_0A_1\\), \\(C_3 = A_0A_1A_2A_0.A_1A_2A_0A_1.A_2A_0A_1A_2\\), and so on. It is known that \\(\\lambda(A_0A_0)=3\\) [\\textit{A. Thue}, Christiania Vidensk.-Selsk. Skr. 1906, No. 7, 22 p. (1906; JFM 39.0283.01)] and \\(\\lambda(A_0A_1A_0.A_1A_0A_1)=3\\) [\\textit{J. Cassaigne}, Motifs \u00e9vitables et r\u00e9gularit\u00e9 dans les mots. Paris: Universit\u00e9 Paris VI (PhD Thesis) (1994)]. The authors prove that \\(\\lambda(C_3)=3\\) and \\(\\lambda(C_t)=2\\) for all \\(t\\geq4\\) (Theorem 1). They also calculate that \\(\\lambda(ABCBA.CBABC)=2\\) and \\(\\lambda(ABCA.CABC.BCB)=3\\) (Theorem 4).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1743715$1BC60BBA-75DB-4373-BF0D-3151EB14EA56","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743715$CDE7010D-7F0C-4F36-8B78-330807245DCB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1941bb49f0666063931abae4e7b16211acf84633","datavalue":{"value":"6859911","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743715$41BC39CD-B693-4DB3-8463-82447042AD7B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b99d5dcd36ca4f6ddee80af79486b0b82119f69","datavalue":{"value":"words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1743715$965410FC-AE48-443A-8295-9D0E578EAE05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d589d1418bb454d0d57abd8c2020b4fc06552aa","datavalue":{"value":"pattern avoidance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1743715$E5912432-CFCD-47B3-BAE3-D4BC9DF805C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3483fa4b50981e59d76e40c38a0526b3b9e03769","datavalue":{"value":"formula avoidance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1743715$AF49AC0D-B94A-46DD-AEC7-F6EBCA3C6EAF","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":"Q1743715$1869D984-F69D-454D-97BE-8283A7276E94","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5edb211efea39306493cfef48b4f047937a00b68","datavalue":{"value":"W2535670093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743715$FB1B1911-BE35-447A-B7E5-B5B2B37D3C9C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"80ac228e0a8acb953c0ce04885ae6edc96ddec5c","datavalue":{"value":{"entity-type":"item","numeric-id":908709,"id":"Q908709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$C2168576-AF6D-4074-9C76-D8CA6C76CC0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c7183512e2829a55f36b5e7ad58903f071c8748","datavalue":{"value":{"entity-type":"item","numeric-id":1137038,"id":"Q1137038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$619CBB8F-EC89-45C0-A0BB-02E15A62CF5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dda6193e4e872327422deff9c753cb11c5cf4e53","datavalue":{"value":{"entity-type":"item","numeric-id":2762708,"id":"Q2762708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$9AEAEE7B-D1E0-41E4-A38E-A5BC431970CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5336d2fe644ee1d401926d7a39d849d2cbd3389c","datavalue":{"value":{"entity-type":"item","numeric-id":650879,"id":"Q650879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$01B0B7E1-33E2-4913-A4B8-5D94EBA99324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab968868a27793512725f9615e172750ff9d631","datavalue":{"value":{"entity-type":"item","numeric-id":4529547,"id":"Q4529547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$0115C377-1AA3-48B4-854F-9D3D829BFF1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7273c5b24ad72bbfbad8718f0b57ab619400c14c","datavalue":{"value":{"entity-type":"item","numeric-id":3421905,"id":"Q3421905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$EB363F54-6AB5-4654-867F-93E49823F91F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"756dee485802f0d87b220bea0f3b7679f8925171","datavalue":{"value":{"entity-type":"item","numeric-id":2635083,"id":"Q2635083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$1966322A-CDA1-4FAC-895A-963A0626F49A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7eb8ac0137b25a78b96e8ed68164a08b0f1c4e3","datavalue":{"value":{"entity-type":"item","numeric-id":1676792,"id":"Q1676792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$ADD70043-1703-4684-A76C-F39E5A759103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f414b9ea6adc0b4e47e61f4708d1d85e9b51232e","datavalue":{"value":{"entity-type":"item","numeric-id":3734729,"id":"Q3734729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743715$BFEDB1C1-A254-4CC2-806A-DBD0C9D66DDA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7c197137d0bce16c2dad3a5d7617464618731931","datavalue":{"value":"10.1016/J.TCS.2017.11.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743715$45A34996-EB91-4861-8C7C-16A133EAFFDE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b868ce7997bce7b45b57f622edb73f1f225db6e","datavalue":{"value":{"entity-type":"item","numeric-id":2817400,"id":"Q2817400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2999e84b811d3248da51b6872d21b0177dc593ee","datavalue":{"value":{"amount":"+0.7676127","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":"Q1743715$0B40F686-3BDA-4706-971F-8FA66B36FC50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c4bca64a3d15057b5750db261fd1754c23aa210","datavalue":{"value":{"entity-type":"item","numeric-id":1676792,"id":"Q1676792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"648cf671b01ff9591381b6a7f5cb4664448375d3","datavalue":{"value":{"amount":"+0.7662742","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":"Q1743715$794BE98B-DF8B-4EA9-A542-CFCA9DD80765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"807f0c722326deaf315de34df7a4c74fbe9e12ff","datavalue":{"value":{"entity-type":"item","numeric-id":2789515,"id":"Q2789515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57ec44602d7ba625bb5200ea71342828926ade27","datavalue":{"value":{"amount":"+0.7634122","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":"Q1743715$1309FC04-0428-4C5A-9FB3-20A70C7B8F07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc072a2d7f3aa79e3a80e7067a6bf86a7bdd0bdb","datavalue":{"value":{"entity-type":"item","numeric-id":2353404,"id":"Q2353404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7086e7851bede8ceecb76567b7d3a074971da67","datavalue":{"value":{"amount":"+0.7632619","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":"Q1743715$3E6DB450-A6D2-4530-81CE-A77025663BB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6483d514e801c9c2946281e1f1ab4261e53e484e","datavalue":{"value":{"entity-type":"item","numeric-id":1659986,"id":"Q1659986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f69ec75337f8eb7b478fb089917dbc4551ba7f2","datavalue":{"value":{"amount":"+0.7553309","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":"Q1743715$8D38E357-43B6-4A6B-933C-EB98EE223AE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03cfe0af65a27e16cb720d80f4e8b0d8ce78236f","datavalue":{"value":{"entity-type":"item","numeric-id":5483466,"id":"Q5483466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9aff1456f05accc282daa9ce259b3f0dae6cae59","datavalue":{"value":{"amount":"+0.7518352","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":"Q1743715$675F8A18-D6CF-4C15-903E-B785A34D9D81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"267506ad009d078515e422e27597868008d63ea3","datavalue":{"value":{"entity-type":"item","numeric-id":2223455,"id":"Q2223455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b2f077753d15e69a20887ec5e92ce778eb14741","datavalue":{"value":{"amount":"+0.75099516","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":"Q1743715$5CAD8A79-F8FE-44DF-91B4-366CB2E47F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1587594ad260eb34bd501abac99a22e6b983976e","datavalue":{"value":{"entity-type":"item","numeric-id":5894536,"id":"Q5894536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb68bd026440ac9c437d99345f7a66f4c39b1206","datavalue":{"value":{"amount":"+0.7505159","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":"Q1743715$B2683D92-4F90-4E70-B478-D6DAED4E5D82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ff6a0294c3e59edfd25267ec846cb8700764bb0","datavalue":{"value":{"entity-type":"item","numeric-id":4412125,"id":"Q4412125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c44b5dede55174071516c84eae23ccac4b31590f","datavalue":{"value":{"amount":"+0.7334815","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":"Q1743715$A60544A1-C54D-4D08-A845-E1BCD9D6A343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea9a22fc267eaadee9aa2cff95f7bd2b0e457371","datavalue":{"value":{"entity-type":"item","numeric-id":3167514,"id":"Q3167514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05f832e18a342c20a2aa318cb07c05596da7d439","datavalue":{"value":{"amount":"+0.7323159","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":"Q1743715$1A7E0B63-B5AF-4661-99DC-9CEE7149A29E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Avoidability of circular formulas","badges":[]}}}}}