{"entities":{"Q778523":{"pageid":780372,"ns":120,"title":"Item:Q778523","lastrevid":64269030,"modified":"2026-04-11T18:43:59Z","type":"item","id":"Q778523","labels":{"en":{"language":"en","value":"On normality in shifts of finite type"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7217005"}},"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":"Q778523$FE8C5AD3-B0E4-4827-9B16-12CF349D9EB2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"94cd348781b81fcc6f5b1a10d1b12f52660d0f27","datavalue":{"value":{"text":"On normality in shifts of finite type","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q778523$C5DF8110-83BC-412F-AE83-37BB2EC924DC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a969c151c5b8f24664855ee9f2b1ff23db61c41d","datavalue":{"value":"1458.37016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q778523$ACAAF7E5-335F-466A-A7CD-282D7FA1EF6C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6813c0c0d634bd244a1caeaeffa7f19b5586ee32","datavalue":{"value":{"entity-type":"item","numeric-id":494058,"id":"Q494058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$CB20BDAD-2A8C-4CF3-824F-5A28998EACC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2d93632719cc6445eb7028931bc4015e0945254f","datavalue":{"value":{"entity-type":"item","numeric-id":308971,"id":"Q308971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$CB26432D-249F-4874-AF1B-1F4101517CF0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$EE12CA94-ACBB-460C-A2EB-1C22CD8357BB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a26eff5f772b2d8b2a62dd873811b984c591713","datavalue":{"value":{"time":"+2020-07-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q778523$BC54355B-2FD7-4C30-8229-299DD9DCFC39","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c928f6fd6e068dbe8f03f172209962501d259f77","datavalue":{"value":"https://arxiv.org/abs/1807.07208","type":"string"},"datatype":"url"},"type":"statement","id":"Q778523$0991711F-16B2-4413-97AF-C32FA8AD3ACD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eb17aba753bbca3cb3502daccacb3d7a53c9fbc3","datavalue":{"value":"The contribution discusses an extension of the characterization of normality of infinite sequences in full shifts via non-compressibility by one-to-one finite-state transducers. Roughly speaking a sequence is normal if all subsequences of any given fixed length occur and occur with the same frequency. One-to-one finite-state transducers compute bijective functions that can easily be represented by a finite-state machine with output. The compression rate is defined as usual as the limit of the ratios between the lengths of the images of the finite prefixes of the sequence and the length of the prefixes. A given sequence is incompressible if there exists no one-to-one finite-state transducer that achieves a compression rate strictly below 1 for that sequence.  The authors generalize the above-mentioned result to shifts of finite type instead of just full shifts. While full shifts are essentially all the infinite sequences that can be formed given a finite alphabet, a shift of finite type is obtained by declaring a finite set of subsequences, of which each is forbidden to occur anywhere in the sequence. To this end, they first show that various definitions of normality (aligned, strongly aligned, non-aligned) yield the same notion. Next, it is demonstrated that a sequence is compressible in the shift of finite type if and only if it is compressible beyond its relative entropy in the full shift, which is then used to establish the already mentioned main characterization theorem relating normality to incompressibility.  The contribution is well written and should be generally understandable to any graduate of computer science or mathematics. It relies on a number of existing results, but full references are provided. The writing is slightly dense, but can be appreciated fully with some effort.","type":"string"},"datatype":"string"},"type":"statement","id":"Q778523$B31F6A44-206E-4FD7-9635-85FE352B372C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"26d1c218d463f30593893b3e531d81ce8bef8874","datavalue":{"value":{"entity-type":"item","numeric-id":519890,"id":"Q519890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$428AEDC8-7DC0-44CA-9B8E-462A5651872F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e9f75a1ea6a1b050032188834d6ec5de5f473dd3","datavalue":{"value":"37B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q778523$CC1583C5-3D0F-4CD9-8475-9DCE5707402D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"34c9981031b4050d34fd5486f5e15e98964980d3","datavalue":{"value":"37B51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q778523$01FDFC1E-5051-47B0-9462-F1644E760D5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"60e34aad7a008d1af33d80ab68d235c199c3462a","datavalue":{"value":"11K16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q778523$8838F3D4-E894-4A8B-8D76-6B4E43490085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q778523$1C3462B1-F1AE-4139-85F1-4CAED17DEC0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q778523$B075E1A9-5D3E-412C-9B01-DBFFBED3F264","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3d5669a9e73f853212cae760cdbf49a00ac1205a","datavalue":{"value":"7217005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q778523$67DE9491-230A-49A5-AA04-AF3639CA9EFD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e269bbc40a3436145ec6a354f8d878b3c6bcc99","datavalue":{"value":"normality","type":"string"},"datatype":"string"},"type":"statement","id":"Q778523$F6ABDA2F-A449-42A3-BA6A-24A89A3677B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4f8dd5c493bcfe457a2c05cd0b9ce65be151090","datavalue":{"value":"compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q778523$9300C4D2-9079-48F8-A231-483E5A721FE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbed6f277b21471fcad281b3c0cb549fde555ed5","datavalue":{"value":"full shift","type":"string"},"datatype":"string"},"type":"statement","id":"Q778523$D39B15B3-52AF-4678-A0D4-0C2C25527A21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff08af47f29dd424d59cd986a47ca33e49b4559b","datavalue":{"value":"finite type shift","type":"string"},"datatype":"string"},"type":"statement","id":"Q778523$87F159A3-8360-4B9A-9966-E3C47D4512E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"425b08bf298851c5c433736a39b81c37dc0b90c9","datavalue":{"value":"finite-state transducer","type":"string"},"datatype":"string"},"type":"statement","id":"Q778523$E049611F-7501-4340-981A-4FBB55687895","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":"Q778523$F7ED7F1F-0303-43D9-A428-B82C23E77317","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cce95389ec7f747030b04bd7c69a55c4b821cd28","datavalue":{"value":"W2992189211","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q778523$9D93E968-90ED-4177-BB5A-AD173D08AC84","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5ebc4ba65057135f0bd4db45195042cfd1f78f6","datavalue":{"value":{"entity-type":"item","numeric-id":5653940,"id":"Q5653940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$A956AE90-611D-4D90-82F1-9D960855D03B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b30fb00c54494686a570615690a7bb80049388c","datavalue":{"value":{"entity-type":"item","numeric-id":2353390,"id":"Q2353390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$FFE49D01-5EF8-42C4-8151-8237EF19515D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f7e96d418e3781219ac6c1d072f0964f84763ac","datavalue":{"value":{"entity-type":"item","numeric-id":494059,"id":"Q494059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$41343684-7A4A-4398-B4A7-336FC57EE6A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6756a0c73bdb129c2f86c825e40d0ce66a74947","datavalue":{"value":{"entity-type":"item","numeric-id":1945947,"id":"Q1945947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$A1B714D5-5302-421B-8CE7-51E62A947FE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77c7337244323983a7435b26e219ebb5ad91503f","datavalue":{"value":{"entity-type":"item","numeric-id":679102,"id":"Q679102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$052345DC-E5E3-4AAB-BD7C-8800C09A3612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"570787d8c3797b23e215bd734559b5ab2bbaea02","datavalue":{"value":{"entity-type":"item","numeric-id":2904676,"id":"Q2904676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$26E5A630-220A-4F6F-BB6D-77AA96E33C6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe4c14951ea467d53bb41329e148cdc73c5e6f0e","datavalue":{"value":{"entity-type":"item","numeric-id":2343136,"id":"Q2343136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$055B7D15-4579-4CAA-8F03-7CAB85973CF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84456d8b868d82b1fc00fe2b2cbd371c6191b62a","datavalue":{"value":{"entity-type":"item","numeric-id":2650030,"id":"Q2650030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$70353486-B736-46D6-B8A3-588EEACCCC7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84712a56384c8eb7be2c41a7d8dad62a5ec72951","datavalue":{"value":{"entity-type":"item","numeric-id":1884962,"id":"Q1884962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$B728769F-AC9A-4C53-87BA-16C8811D24BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f75ce1721dede21d7e0692e867fb208337c0419c","datavalue":{"value":{"entity-type":"item","numeric-id":1220734,"id":"Q1220734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$3835D861-5E4B-4687-AAC9-A2CD076B7E29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71de3f2ea38d5907966f1c5de4845c210a2e2d80","datavalue":{"value":{"entity-type":"item","numeric-id":1376246,"id":"Q1376246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$9BE1B2D6-428A-41F5-8313-FFF959A7BCDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e57fccc8c00238fd458ec81341321c0921c881c","datavalue":{"value":{"entity-type":"item","numeric-id":4174617,"id":"Q4174617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$EE6A01A6-3FDF-4E08-AA20-CF67D095842E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93c253900e4829cb5d0d6d60e214b68399dc4e6c","datavalue":{"value":{"entity-type":"item","numeric-id":4856597,"id":"Q4856597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$4E49AD9B-31B6-43FF-A750-ECC613C10879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a95a0c7f95145254d4403d77903b91e789e3e946","datavalue":{"value":{"entity-type":"item","numeric-id":4613552,"id":"Q4613552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$1AC1E33A-E39E-4BF0-B7EE-68ABA8C8F00B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18642a838491c188ef18e183a8a792128a59fc0c","datavalue":{"value":{"entity-type":"item","numeric-id":4216130,"id":"Q4216130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$E89ACB59-1461-4754-820E-429AE8CE6F6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcad196cde92ff58f605cb0c7899249dd4df74ca","datavalue":{"value":{"entity-type":"item","numeric-id":5317419,"id":"Q5317419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$C46EDD6A-E36D-48DB-98B1-8435B7642423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"221fdbaa07e825d34a5fbdba5c71943b62f4b321","datavalue":{"value":{"entity-type":"item","numeric-id":2553152,"id":"Q2553152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$F86967D2-EF8B-48B3-8337-09FABC042BA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"473cd61866e2885d9944efcf3021bb7e66a1c593","datavalue":{"value":{"entity-type":"item","numeric-id":2492010,"id":"Q2492010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$3AF75358-D826-4D2A-A139-B0DF8A4F394E","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":"Q778523$22727CA5-230C-43D1-A1A7-7349E4A6C625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a393dd2ac446840fd7d0b075e4d7cb62fe01275c","datavalue":{"value":{"entity-type":"item","numeric-id":1844957,"id":"Q1844957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q778523$652FE9D8-1E4C-420B-8759-DB9E3CB3B4B1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"57ac856cb44eb0f6b540725914e01fc45ff7ad21","datavalue":{"value":"10.1007/S00224-019-09953-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q778523$8FC482C8-B217-48C7-9008-928EF9D1ECB4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3833dfb029de5d92a9bb53b71978426ce3c9650","datavalue":{"value":{"entity-type":"item","numeric-id":494059,"id":"Q494059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d61f656e9e75cad2da7c707a6507349eeffb54d2","datavalue":{"value":{"amount":"+0.8352647423744202","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":"Q778523$C76025A4-2E2C-42D9-8B64-F3BB1E55939F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83cadb89e7f012989922039c52a6dc28e5a16d14","datavalue":{"value":{"entity-type":"item","numeric-id":1945947,"id":"Q1945947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"839b131ddf9aea164584fadc3a1da6591ab13150","datavalue":{"value":{"amount":"+0.8200320601463318","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":"Q778523$D991D5CC-3EFA-4DA7-9359-3C86D6E7B5E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58b395ed71ce73be2eb372756bb7d77d8399baf9","datavalue":{"value":{"entity-type":"item","numeric-id":259039,"id":"Q259039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c177414347b1fe0d35c4744e0ac471ea4798d1e5","datavalue":{"value":{"amount":"+0.80684494972229","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":"Q778523$A85F6504-A497-44EB-924C-D37AC102C07F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"151a96af72dc30a7bcba9c64075e5efe20124307","datavalue":{"value":{"entity-type":"item","numeric-id":5410635,"id":"Q5410635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6373e553eacc267a225e3744de9535aab938e23d","datavalue":{"value":{"amount":"+0.8010424375534058","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":"Q778523$189574DB-109E-4FF8-AB5A-AF24E086F742","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86f7ab8901f8c7ee9fa2f294c38fa8e65f42135d","datavalue":{"value":{"entity-type":"item","numeric-id":2656172,"id":"Q2656172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c983553dba687aa31c56473184db67ca0de535f","datavalue":{"value":{"amount":"+0.7957268357276917","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":"Q778523$F60A0E8C-96B2-4324-A85A-AD81DD0927B1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On normality in shifts of finite type","badges":[]}}}}}