{"entities":{"Q1995561":{"pageid":2006303,"ns":120,"title":"Item:Q1995561","lastrevid":57640692,"modified":"2026-03-31T18:24:44Z","type":"item","id":"Q1995561","labels":{"en":{"language":"en","value":"The relationship between word complexity and computational complexity in subshifts"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7314925"}},"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":"Q1995561$D900A076-DE3C-4B32-8751-9C8D58743E57","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"91c2a02fc6b2a7e6eee763884f4d051eadaf500e","datavalue":{"value":{"text":"The relationship between word complexity and computational complexity in subshifts","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1995561$C8EF3BDC-710D-493E-8586-CA5153207B9C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cec5919cbd0d7c208500dc8f48c6073e932b2817","datavalue":{"value":"1472.37017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1995561$F3B1A1F2-325A-49DB-A6E1-97E0F56E64BD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"74cac255e6366eb611dacc6ca1e343f583b827ea","datavalue":{"value":{"entity-type":"item","numeric-id":271734,"id":"Q271734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$DCFD486A-D159-468B-A1C5-3F43B3C8D4EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f0b7b2a91ff626708fc9788fc7434ea7587a660","datavalue":{"value":{"entity-type":"item","numeric-id":393139,"id":"Q393139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$8E5FC83A-8BA7-4F92-BA27-16D8BE63E3A4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"12360f81ee541e586ca46b53d6a0b87af7080802","datavalue":{"value":{"entity-type":"item","numeric-id":187060,"id":"Q187060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$2F62F504-37B2-4C92-9F52-8D5FF712391D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1adf4f4ff00d375f9dadfee22b395ad0bd8222ce","datavalue":{"value":{"time":"+2021-02-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1995561$775274D4-2138-46A2-80D0-2DA25D5E26DF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"68ad193eea9016a3630105a73aef8c3017e7866a","datavalue":{"value":"https://arxiv.org/abs/1903.04325","type":"string"},"datatype":"url"},"type":"statement","id":"Q1995561$E47B6930-E78D-4432-8307-94BD0BFD847B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c5a70583092395ddca9c2ffa899608a5792a3e5a","datavalue":{"value":"Given a finite set \\(A\\), a subshift over \\(A\\) is a subset of \\(A^\\mathbb{Z}\\) which is closed in the product topology and invariant under the shift map \\(\\sigma\\) defined by \\((\\sigma x)(n)=x(n+1)\\). The word complexity function \\(c_n(X)\\) of a subshift \\(X\\) is defined by \\(c_n(X)=|{\\mathcal L}_n(X)|\\), where \\({\\mathcal L}_n(X)\\) is the set of all words of length \\(n\\), i.e., \\(c_n(X)\\) is the number of all words with length \\(n\\) appearing in some \\(x\\in X\\).  The Turing spectrum of a subshift \\(X\\), denoted by \\(\\mathrm{Sp} (X)\\), is the set \\(\\{\\mathbf{d} | \\exists x\\in X, \\mathrm{deg}_T (x) = \\mathbf{d}\\}\\) of all Turing degrees of all points of \\(X\\). \\par The authors study the relationship between the word complexity function of a subshift and the Turing spectrum of the subshift. In particular, it is proved that a Turing spectrum can be realized via a subshift of linear complexity if and only if it consists of the union of a finite set and a finite number of cones, that a Turing spectrum can be realized via a subshift of exponential complexity if and only if it contains a cone, and that every Turing spectrum which either contains degree \\(\\mathbf 0\\) or is a union of cones is realizable by subshifts with a wide range of ``intermediate'' complexity growth rates between linear and exponential.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1995561$C6181ED4-6CB1-4A9C-8B13-A09361C1A171","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b559307b5b2969939e6945d65ee127220f8f6f4b","datavalue":{"value":"37B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1995561$787F1B22-35DD-4D3E-B97B-C67CB9CF3B79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1995561$04980E5F-F93D-4277-8D9F-8936A953D88A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1995561$E93C2633-85A9-48B3-82F8-7F78A0D327D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1995561$E2A5E5C3-584A-4315-9ABE-EA48DCD5588E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1995561$ABCC41DC-6F85-48E1-8375-3719A3BBA76F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"318ab3012e23384150250d82b0afa4dc627b55c2","datavalue":{"value":"7314925","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1995561$611B2A76-A4A4-46D5-8C41-64737C6C16EE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fc27f13195d7d8cb048669ac88dc081dcb2f69c","datavalue":{"value":"symbolic dynamics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1995561$D9162F01-8500-4BA5-829B-3B71EFDF1509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"948cc8cdb885a280b485e2da2b71f5dbbc318ce4","datavalue":{"value":"Turing degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1995561$3B70CEF8-95D1-45B1-A454-BB56BE4A429F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e800a7b30cf174bf647e50618a644756839f08f","datavalue":{"value":"word complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1995561$7F210054-7534-4261-9E84-C8D0B2525D00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4f2891ec95ee556b0ac2cc2dddee3d77811bd94","datavalue":{"value":"computability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1995561$90E5EF73-0A28-4268-8442-D658D904F9A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f499971506bb7d13eebf3a41582911b6f7a30bdf","datavalue":{"value":"spectrum","type":"string"},"datatype":"string"},"type":"statement","id":"Q1995561$7B6F4715-D238-4381-9C5C-AA53C51B9F86","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7c0f9a5de2afd25d103c132e1617d4201a3c58e4","datavalue":{"value":{"entity-type":"item","numeric-id":591972,"id":"Q591972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$92E67FDB-6144-4DE2-87AF-BA57AB2AF8BE","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":"Q1995561$AD5F3CA6-5649-4357-A61E-9FC756FDD128","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"528506d863b7e506f7d96867bdfc457fdc0e99b9","datavalue":{"value":"W3092921271","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1995561$3BA1C548-32D2-4793-9B39-CBE87312C53F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dba39c8ad68be6177af234d7be1a6377587a58f","datavalue":{"value":{"entity-type":"item","numeric-id":5486009,"id":"Q5486009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$0B10050E-6544-4DBC-B024-B59AB1E7CE13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da9d94ee13fb5ecca8b20e9dac6ff80f0c10426a","datavalue":{"value":{"entity-type":"item","numeric-id":4417312,"id":"Q4417312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$BCEEC1F1-BDC3-4F15-8533-961A8ABD04DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d09a9e1b36c32d4ab07017a79026d0f0cacdc0f","datavalue":{"value":{"entity-type":"item","numeric-id":4438708,"id":"Q4438708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$83183DBF-A257-49F7-A160-A6313642942D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"339affecbad8ac0ffbc190baa1e909e964635fc3","datavalue":{"value":{"entity-type":"item","numeric-id":974081,"id":"Q974081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$2134FCBA-AF6C-4D4A-B557-ABC874B4E265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f678cae38596e5d290b578426513a6d523a25aab","datavalue":{"value":{"entity-type":"item","numeric-id":2399371,"id":"Q2399371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$1C3BBD2C-4827-434D-87C7-78C9E5E58962","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f401438d63fc66d6263139f935a1a216f164d73c","datavalue":{"value":{"entity-type":"item","numeric-id":393140,"id":"Q393140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$87F97B56-9D24-4F02-91B5-865360ACFE09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b99c29cdf89c89d4c38d341512cc79b7d442800","datavalue":{"value":{"entity-type":"item","numeric-id":3053473,"id":"Q3053473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$0A80C4DE-DDBF-4C94-8E12-E71D165FD632","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":"Q1995561$F12BF749-85DA-4ED8-9A43-478C64D090EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98c1bd0cfa45f26d02860c95bbf722bd54fd9e88","datavalue":{"value":{"entity-type":"item","numeric-id":4563667,"id":"Q4563667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$1A6E85F6-49D3-4364-8E86-E41EE19D46F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35b843483a357ed6f19fa8197ec08dbd38f89a86","datavalue":{"value":{"entity-type":"item","numeric-id":5390213,"id":"Q5390213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$84FFD2AE-E272-4E72-8E2E-71B8A6DCDF22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5b9564b979a9d0175ba3c8db086470676cce61b","datavalue":{"value":{"entity-type":"item","numeric-id":3931654,"id":"Q3931654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1995561$F634A078-3FC6-4A1B-87FD-E314CE52B87D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6e6786bf10d8bfeae6626b7003f4c20a98ee9890","datavalue":{"value":"10.3934/DCDS.2020334","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1995561$0CB19142-4531-4F08-80A2-376C1B8EDBBC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46024387b64c6c1564a5a09b5a59d69b85aee92f","datavalue":{"value":{"entity-type":"item","numeric-id":2399371,"id":"Q2399371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54494106fffb6b927bb91c6e078e020d44139c9b","datavalue":{"value":{"amount":"+0.7892100811004639","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":"Q1995561$7EFBDC67-7B2E-4344-A4D3-A3429C569640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51d28dd2b254dd5b790f14116875c7302e479825","datavalue":{"value":{"entity-type":"item","numeric-id":5390213,"id":"Q5390213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e26ad3432fddcb0ea56194cb185a715b4ab902ae","datavalue":{"value":{"amount":"+0.7526050209999084","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":"Q1995561$2FD59D46-C835-4FC9-8187-F4EFD52B5D61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25df8c183fcb2d23800c3bd420248997b3f9c572","datavalue":{"value":{"entity-type":"item","numeric-id":393140,"id":"Q393140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c021f9cfccdabf0e1cf172235020fc88b1a5171","datavalue":{"value":{"amount":"+0.737308144569397","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":"Q1995561$72BCFFA4-B9AA-44DF-A81B-4438501D28BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5e9a0aee512a5aa9ee0be85e013aeeebf1d583b","datavalue":{"value":{"entity-type":"item","numeric-id":3576194,"id":"Q3576194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"baf938ace7aa29a899a698985800735cb1f6088e","datavalue":{"value":{"amount":"+0.7302455306053162","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":"Q1995561$3558AF85-EC19-48DE-855D-A0CD099BE857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a04bb85943bd99b6ec6df829d93d722208a3f505","datavalue":{"value":{"entity-type":"item","numeric-id":3575432,"id":"Q3575432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"594945fe99feae7a3a4092a3d8d114d31ba89de3","datavalue":{"value":{"amount":"+0.7255667448043823","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":"Q1995561$AC54A614-9FCD-42ED-A234-E18B078E671E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1995561","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1995561"}}}}}