{"entities":{"Q727190":{"pageid":729039,"ns":120,"title":"Item:Q727190","lastrevid":63875805,"modified":"2026-04-11T16:08:29Z","type":"item","id":"Q727190","labels":{"en":{"language":"en","value":"Grasshopper avoidance of patterns"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6661369"}},"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":"Q727190$D4EF4642-D921-4BFA-B54B-D6EE0A6C609B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3214f0b8d6a48da2a4df75de4d6784e0a6ec3f3b","datavalue":{"value":{"text":"Grasshopper avoidance of patterns","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q727190$DC2FFD86-BCC1-4D60-8ADD-5BBBB944469C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c20c4111e2feef707543332e144fd2fbf3eb15e6","datavalue":{"value":"1351.05007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q727190$74E00D41-D71E-4B79-8071-25F382BDB256","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d01afa9d2fe3aa4ecba131b11633fd93bbe51a11","datavalue":{"value":{"entity-type":"item","numeric-id":322247,"id":"Q322247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$EE861BAF-7348-4386-9F96-9DB62027CB92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a20906073e03b653b20e2541f6c6e9ff8720259","datavalue":{"value":{"entity-type":"item","numeric-id":727189,"id":"Q727189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$D9F2E0C8-0C9A-4306-A332-4A7D0AEB704F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e9273ae4b74d03f49143c0e32ecc8970d7b5c8a","datavalue":{"value":{"entity-type":"item","numeric-id":249554,"id":"Q249554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$A9EE3FB6-FB94-49DB-8EAE-2218854F53B4","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":"Q727190$FC23671B-0102-4E84-9390-DA5AE7135C17","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f5a5fb6149ff482096cebaf0b894e1861dc804b1","datavalue":{"value":{"time":"+2016-12-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q727190$49758E66-D958-4A97-B2F3-66B2506C8AEB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3e9534acf90212c5e318a1170236176d73a42e02","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p17","type":"string"},"datatype":"url"},"type":"statement","id":"Q727190$429341F5-0A42-48B0-A310-64CC660D3B48","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8e59d8e7654baf73fe33832825f0bea00f03d4b7","datavalue":{"value":"Summary: Motivated by a geometrical Thue-type problem, we introduce a new variant of the classical pattern avoidance in words, where jumping over a letter in the pattern occurrence is allowed. We say that pattern \\(p\\in E^+\\) occurs with jumps in a word \\(w=a_1a_2\\ldots a_k \\in A^+\\), if there exist a non-erasing morphism \\(f\\) from \\(E^\\ast\\) to \\(A^*\\) and a sequence \\((i_1, i_2, \\ldots, i_l)\\) satisfying \\(i_{j+1}\\in\\{i_j+1, i_j+2 \\}\\) for \\(j=1, 2, \\ldots, l-1\\), such that \\(f(p) = a_{i_1}a_{i_2}\\ldots a_{i_l}.\\) For example, a pattern \\(xx\\) occurs with jumps in a word \\(abdcadbc\\) (for \\(x \\mapsto abc\\)). A pattern \\(p\\) is grasshopper \\(k\\)-avoidable if there exists an alphabet \\(A\\) of \\(k\\) elements, such that there exist arbitrarily long words over \\(A\\) in which \\(p\\) does not occur with jumps. The minimal such \\(k\\) is the grasshopper avoidability index of \\(p\\). It appears that this notion is related to two other problems: pattern avoidance on graphs and pattern-free colorings of the Euclidean plane. In particular, we show that a sequence avoiding a pattern \\(p\\) with jumps can be a tool to construct a line \\(p\\)-free coloring of \\(\\mathbb{R}^2\\).  In our work, we determine the grasshopper avoidability index of patterns \\(\\alpha^n\\) for all \\(n\\) except \\(n=5\\). We also show that every doubled pattern is grasshopper \\((2^7+1)\\)-avoidable, every pattern on \\(k\\) variables of length at least \\(2^k\\) is grasshopper 37-avoidable, and there exists a constant \\(c\\) such that every pattern of length at least \\(c\\) on 2 variables is grasshopper 3-avoidable (those results are proved using the entropy compression method).","type":"string"},"datatype":"string"},"type":"statement","id":"Q727190$179D4A12-C211-4DAD-9703-BAA91FCFCB81","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q727190$A93126B6-000E-43F2-A4E0-362F037C73E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q727190$2667EE51-9073-4872-8866-2EC328CFAC4F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c010bc593363ceafed239b3f1ca822bc12ed938f","datavalue":{"value":"6661369","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q727190$411C88F9-C71D-4881-B303-5DC3C8517E1A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"488c0c66ae5cedd2c082b34e706c29b594b84665","datavalue":{"value":"Thue sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q727190$E8E70A58-3570-475A-9BB2-D9465A365BBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68f934702f36ff78c7f8d499f1ba40cef4d5d660","datavalue":{"value":"avoidable pattern","type":"string"},"datatype":"string"},"type":"statement","id":"Q727190$8A9D2355-15C4-412D-9172-6B906642E72B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13f37f55b2aa8ed3aeca864fa8be46306b3ae686","datavalue":{"value":"entropy compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q727190$CF3519A8-9C11-4006-9B80-E68205ED31CD","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":"Q727190$3B714409-A559-47E7-A045-A011DF5A37A4","rank":"normal"}],"P223":[{"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":"Q727190$568DE673-EDC8-48C1-B890-065BF37F236D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95fa878fb2c02613b94617992debe081ca5a953e","datavalue":{"value":{"entity-type":"item","numeric-id":2381499,"id":"Q2381499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$9AE1D1AF-81E4-43EF-8BE9-CE142624BE7C","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":"Q727190$ED48500F-D3BD-4DC5-87CE-B21C51A7A06F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04d5bc440b7d66f171204ac0728d34298f69953b","datavalue":{"value":{"entity-type":"item","numeric-id":1323331,"id":"Q1323331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$B1634403-B731-4283-98B4-430680E3714F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"443e248a38fe0f368829deb54dc1e0399bba75e5","datavalue":{"value":{"entity-type":"item","numeric-id":5483466,"id":"Q5483466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$B9231FA0-B635-43C1-A36C-1D6C6ADC2BB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdb7931b71f3eb9325745ad9d541802500c41854","datavalue":{"value":{"entity-type":"item","numeric-id":557911,"id":"Q557911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$8E4D67FA-E5EF-41AE-A47C-31AD31B9E241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ed496ed642105301d7e6447d21cd3b7786ae730","datavalue":{"value":{"entity-type":"item","numeric-id":1605623,"id":"Q1605623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$184FBA8D-8604-4730-9104-C2F485E3E932","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e06096dda0103afa28ef857fadd788ff132a5e6d","datavalue":{"value":{"entity-type":"item","numeric-id":1856338,"id":"Q1856338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$238A68D7-EF6E-4FAB-93EE-2F53CC128DDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35912017dd6aa8092ff0d53f45f1ad24825db48c","datavalue":{"value":{"entity-type":"item","numeric-id":878624,"id":"Q878624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$18AA68F8-6333-4F5B-ABF9-5F55715E8E14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"683a43415087f1adbb46b9286475847dfd19768c","datavalue":{"value":{"entity-type":"item","numeric-id":941381,"id":"Q941381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$B04D562C-4B50-4EF4-814E-5B83CD4CE4BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d348c083d124440d2ce2eaf8e3cd17bdc3bf26a","datavalue":{"value":{"entity-type":"item","numeric-id":499479,"id":"Q499479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$698E6700-B393-4679-A4CD-924FFE100BB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b416ef5243e683f4588d7ea167aeb9dbc0aaa61","datavalue":{"value":{"entity-type":"item","numeric-id":2346472,"id":"Q2346472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$9F1E0F70-1A6C-46C9-A365-718C7C983D85","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":"Q727190$CDC3584E-6271-49E0-A94E-07A75EC25B58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ba75693b6124fe57a706fee318668736345dcfb","datavalue":{"value":{"entity-type":"item","numeric-id":4681771,"id":"Q4681771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$EFC3F0F3-AE14-4A2D-9299-1112CBA40FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4afd6af18f6b3e851b76214fa76a694c5f4b58bc","datavalue":{"value":{"entity-type":"item","numeric-id":5172728,"id":"Q5172728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$BF54EDF5-DE6B-43D2-84B1-472C0E9B4317","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":"Q727190$E1C98242-8898-4216-83F9-4083CC33011D","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":"Q727190$5F7C6F7A-7631-4937-8EC8-37E05495238C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3db50cc9b0933259e9a4a82636adcdcb84e1f2c4","datavalue":{"value":{"entity-type":"item","numeric-id":405191,"id":"Q405191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$200D177F-4062-4680-A5FF-F22FA530B287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef6397b0459e4b59017759e272fe7fd547caa52e","datavalue":{"value":{"entity-type":"item","numeric-id":1186515,"id":"Q1186515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$45EC7C1C-1ABD-419A-8E54-30CF510E264C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83918f11c85d9fbafa46bde62e6b734e5a04061e","datavalue":{"value":{"entity-type":"item","numeric-id":1114419,"id":"Q1114419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$3FB94D99-E9B9-4987-A83C-137AF4D7215E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c069f30e8731888714cfd3a0ca225ecbd681312","datavalue":{"value":{"entity-type":"item","numeric-id":3064182,"id":"Q3064182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$9FD56DD8-F410-4BEE-867C-F3401D2140E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20cf53e4d7eaa36930ae90e870a77ae18ba8bd6","datavalue":{"value":{"entity-type":"item","numeric-id":5964253,"id":"Q5964253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727190$DCC2E103-4FFD-4805-AE2B-97353F4C0B1B","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":"Q727190$CA26427C-C4D9-4B36-A13A-C88AFEFD2FC3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"14a2bfcb6a4e98f7b5382d1227d45b14f856cbf5","datavalue":{"value":"bafkreibcamtrutdvstwl6z27mwmzv6na3fnfdxua3xrsjukvx2gwkz2jvi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q727190$F1D284FC-8D2A-4BA2-A620-1FA80A29CF2E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1673b169e7f69bf8b023477b59d1ef5f360ad2c","datavalue":{"value":{"entity-type":"item","numeric-id":1114419,"id":"Q1114419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bd0d55a044eaa6d5bfda0605ada2d9ed3c9bd13","datavalue":{"value":{"amount":"+0.7762696146965027","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":"Q727190$9DBF6DB7-0B1D-4A78-8F52-CEDE4A9ED6F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b0d08b54a83694ff1ff383415c69079a07c18c2","datavalue":{"value":{"entity-type":"item","numeric-id":3774970,"id":"Q3774970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4eae051f0e0d478c7f104157521ef55740cebeb","datavalue":{"value":{"amount":"+0.7737757563591003","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":"Q727190$37A337BB-CB73-439B-804D-5BE3BD0A6407","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":"5ad3fe16525788e5149885b20e8db9eb6c44ba73","datavalue":{"value":{"amount":"+0.7621814608573914","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":"Q727190$8AEAFE18-75FA-4366-A4E2-434AA7AE2020","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccd093423f88af304c43a7f3c154972252b6b9be","datavalue":{"value":{"entity-type":"item","numeric-id":405191,"id":"Q405191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f1595c2d80a9bf010071a874a64a9ac6a5163b2","datavalue":{"value":{"amount":"+0.7610986828804016","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":"Q727190$96A17326-73A9-46A9-9788-A56F90EDF98B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ff7455d0fcbdc9b6e6f6b94abcd6377dc239136","datavalue":{"value":{"entity-type":"item","numeric-id":1753110,"id":"Q1753110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"108a575d52312d1806a9c83e5c5b1c6fdc851443","datavalue":{"value":{"amount":"+0.7599247097969055","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":"Q727190$364BC314-21B2-4904-A9AD-3310051A5532","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Grasshopper avoidance of patterns","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Grasshopper_avoidance_of_patterns"}}}}}