{"entities":{"Q544872":{"pageid":546639,"ns":120,"title":"Item:Q544872","lastrevid":62640438,"modified":"2026-04-11T07:27:45Z","type":"item","id":"Q544872","labels":{"en":{"language":"en","value":"Infinite permutations of lowest maximal pattern complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5908421"}},"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":"Q544872$A70CCF37-4484-4E7E-90E3-0E6176E91AAB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"73a2f28bdac8bae49494ec8ec0365dabeb8933bd","datavalue":{"value":{"text":"Infinite permutations of lowest maximal pattern complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q544872$35980521-33CE-40A3-BC8E-F8B935FB93BD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dc327d69ebbe76da7f2ea53adae5ea0adf47a405","datavalue":{"value":"1232.68095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544872$0CD476A2-3485-4C52-B73C-FEA3DC1AEFEF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d75d28b470ea2cbede3b521f9e73fd45aef50ac","datavalue":{"value":{"entity-type":"item","numeric-id":477554,"id":"Q477554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544872$0FECB590-9292-4E43-837A-F6C3678A77EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3994b3ea7b242f980d845d7f38f3a45e589bc28","datavalue":{"value":{"entity-type":"item","numeric-id":592710,"id":"Q592710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544872$40889514-BE92-4A4F-83E6-9664AE70074A","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":"Q544872$D3854EAC-D33D-4A36-8AE0-E7DB3CAA7301","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d7df6680843dddfb28886aa6e25aecb0a721c189","datavalue":{"value":{"time":"+2011-06-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":"Q544872$4BDC288D-67D0-4A61-861A-096756036AC6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e463e7d3a390b7bceb3cdfa30c65e32cbd1cd4da","datavalue":{"value":"https://arxiv.org/abs/0910.5696","type":"string"},"datatype":"url"},"type":"statement","id":"Q544872$CF71479E-12A5-4280-932D-5BB3C3762491","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"58af0185e3a66b0313fee8636d411682ea9cb438","datavalue":{"value":"An \\(\\mathbb{N}\\)-permutation is a linear ordering of \\(\\mathbb{N}\\) represented by \\ a sequence of pairwise distinct real numbers \\(\\alpha=\\left\\{ \\alpha _{i}\\right\\} _{i=1}^{\\infty}\\).\\ The ordering may be encoded using the symbols \\(\\gamma_{ij}\\in\\left\\{ <,>\\right\\} \\), where \\(\\gamma_{ij}=\\,<\\) if \\(\\alpha _{i}<\\alpha_{j}\\), and \\(\\gamma_{ij}=\\,>\\) otherwise. The sequence \\(\\alpha\\) is [ultimately] periodic if, for some \\(t\\geq1,\\) \\(\\gamma_{ij}=\\gamma_{i+tj+t}\\) for all \\(i,j\\) (starting from some \\(n_{0}\\)). A \\(T\\)-pattern in \\(\\alpha\\), where \\(T=\\left\\{ 0<m_{1}<\\cdots<m_{n-1}\\right\\} \\), is the \\(n\\)-permutation corresponding to a finite subsequence \\(\\alpha_{k}\\alpha_{m_{1}+k}\\cdots \\alpha_{m_{n-1}+k}\\), \\(k\\geq0\\). The number of distinct \\(T\\)-patterns in \\(\\alpha\\) is denoted as \\(p_{\\alpha}\\left( T\\right) \\). A \\(\\left\\{ 0,1,\\ldots,n-1\\right\\} \\)-pattern\\ in \\(\\alpha\\) is called an \\(n\\)-factor of \\(\\alpha\\). A characterization of (ultimate) periodicity of \\(\\mathbb{N}\\)-permutations based on the number \\(f_{\\alpha}\\left( n\\right) \\) of distinct factors of \\(\\alpha\\) of length \\(n\\) is known and just partially corresponds to the similar characterization for infinite words.  In the current paper the authors consider the maximal pattern complexity \\(p_{\\alpha}^{\\ast}\\left( n\\right) =\\max_{\\left| T\\right| =n}p_{\\alpha}\\left( T\\right).\\) Their main result states that an infinite word is ultimately periodic if and only if \\(p_{\\alpha}^{\\ast}\\left( n\\right) \\geq n\\). This is an analogue of a similar fact known for infinite words (where the right-hand side is to be replaced by \\(2n\\)). Moreover, they prove that equality holds exactly for those \\(\\mathbb{N}\\)-permutations that are Sturmian. An \\(\\mathbb{N}\\)-permutation \\(\\alpha\\) is said to be Sturmian if it can be described using some Sturmian word \\(w=w_{0}w_{1}\\cdots\\) and fixed real numbers \\(\\alpha_{0},x,y\\) by the formula \\(\\alpha_{i+1}=\\alpha_{i}+x\\) if \\(w_{i}=0\\) and \\(\\alpha_{i+1}=\\alpha_{i}-y\\) if \\(w_{i}=1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q544872$F01E5A7C-29A8-4D11-A584-D8EC50D32A71","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544872$E0E6B136-D1A1-45EB-9070-66862839B3DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544872$A9D52B48-1738-4DA6-A5C9-863D69E5A7A2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dc99c7b2ccc0f8bbcb97ab9740fea73f5750d178","datavalue":{"value":"5908421","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544872$38267CF3-EFEB-4D61-A127-9E5D1DBDC6FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ff5813ea387a85d3011a9d07294b71682f2f64e","datavalue":{"value":"infinite permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q544872$E6415E0E-6DA0-4D53-A5E0-424721B7281E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"12d3038b86bd8eca9cc438a24056aeeb757ee1f5","datavalue":{"value":"subword complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q544872$D194DA8B-3D1C-4833-8A8F-5241F263BCF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"376c5ba6db3848c5b96f358f8e703e6e621d9889","datavalue":{"value":"Sturmian word","type":"string"},"datatype":"string"},"type":"statement","id":"Q544872$9188399A-18EF-43FA-9962-7ABC70F8D4DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6d2e1696ea8ace064b841fdfd165b3803d13095","datavalue":{"value":"Sturmian permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q544872$0EDDA62F-5A9B-412B-A101-706545A42B8A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1709c704ca283e54ed81f03ca60bb288bae9e53d","datavalue":{"value":{"entity-type":"item","numeric-id":355508,"id":"Q355508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544872$1440BE6E-6C33-4AD2-A4D5-B00EA5BF432B","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":"Q544872$1D4221A1-EB09-455F-9F58-87151FF142A7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"87d135aff9b29d37cc104685b5e8282313cf4389","datavalue":{"value":"W2008695999","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544872$1828881D-E7D6-435C-8871-448EDF1D5C71","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09fdb84ec6020ecc6539924dac741ab4f044ea78","datavalue":{"value":{"entity-type":"item","numeric-id":4365012,"id":"Q4365012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544872$A0FC6A52-8A69-4EE7-8F6D-88DB269CDBAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"301a991a562ee97af1dcb42d6f4734cc8b5747e8","datavalue":{"value":{"entity-type":"item","numeric-id":1304818,"id":"Q1304818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544872$225891F4-3045-4FA9-8E1A-528DB0A11CA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"320a638027aa3e76319a7c76127d41887daadffc","datavalue":{"value":{"entity-type":"item","numeric-id":2461768,"id":"Q2461768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544872$A6AC1EEC-71F4-4E13-BC55-D078A5C9A1DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"142727bb61f5f8756f6b0b5ec7ac11b4e18390e0","datavalue":{"value":{"entity-type":"item","numeric-id":2502894,"id":"Q2502894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544872$6A099719-1C44-4C6C-A660-5DF37BFFDADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e73db4b2b3144cbdcd9cf64803d1447dc9fd047","datavalue":{"value":{"entity-type":"item","numeric-id":4781863,"id":"Q4781863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544872$48A7A964-BD44-4863-8219-160B72E4FB5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94cd5222176fb74f5436796f7602c66020e9cad2","datavalue":{"value":{"entity-type":"item","numeric-id":4781864,"id":"Q4781864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544872$6B724706-0BD4-46AC-A411-9A565A7D614C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4c000d77353a71a636a4331a911083a0b39639c","datavalue":{"value":{"entity-type":"item","numeric-id":5391598,"id":"Q5391598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544872$175D5E7E-3B40-43C1-BA34-A6FCDD63BE6F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c20781b7f2038901011a9639c021779a2b1cdec1","datavalue":{"value":"10.1016/J.TCS.2010.12.062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544872$7CA85DEA-3A04-42FE-8223-A3ACABA51B3F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f5b67e9c3d3570392010b69bca151c6f7465874","datavalue":{"value":{"entity-type":"item","numeric-id":2461768,"id":"Q2461768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49dd21b905ca10310559671360f40109ea80f729","datavalue":{"value":{"amount":"+0.8813194036483765","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":"Q544872$F2A6B010-A4FB-448F-BA6E-FD533E2BE596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48b001b8b7dbb050055a6787c46a4e2295818ecb","datavalue":{"value":{"entity-type":"item","numeric-id":3576702,"id":"Q3576702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d8fcc624e6fe8f48418b572077ff148f978fe19","datavalue":{"value":{"amount":"+0.8648430109024048","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":"Q544872$00369EF0-2C74-4F67-B0C0-3AF5C83ACB50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5050cd993e3eb0155c09c4d3c5a99651c2ec4a5","datavalue":{"value":{"entity-type":"item","numeric-id":5391598,"id":"Q5391598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79fd7546d1075fd4f8cc2e86ce9b7f9734a89b67","datavalue":{"value":{"amount":"+0.8637570738792419","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":"Q544872$C457E711-A4FA-427E-8458-5F555A81E851","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Infinite permutations of lowest maximal pattern complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Infinite_permutations_of_lowest_maximal_pattern_complexity"}}}}}