{"entities":{"Q2217496":{"pageid":2228239,"ns":120,"title":"Item:Q2217496","lastrevid":57785832,"modified":"2026-04-02T12:51:21Z","type":"item","id":"Q2217496","labels":{"en":{"language":"en","value":"Automatic complexity of Fibonacci and tribonacci words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7289403"}},"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":"Q2217496$46DA8D89-84C6-4993-8B73-5185AE002D1D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cabf12321281d8ff4380e1d15bb0b05a02e524e3","datavalue":{"value":{"text":"Automatic complexity of Fibonacci and tribonacci words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2217496$BE16B991-F5C8-437B-9B01-0AECE919CF07","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"578ce269ea83ab1ec6ff85995a258c2d90c52739","datavalue":{"value":"1477.68134","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2217496$0B8A639C-07AF-406F-9D5E-09AF2B1E404B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"713c2f755459cde585837394c4916f4792e504e4","datavalue":{"value":{"entity-type":"item","numeric-id":490406,"id":"Q490406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$ED40905B-CB18-4A39-93B7-DF1FBDC2BB60","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$8DD29308-02BD-4924-A202-C0FE1DCA4776","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b761dbc0f27b7acb1c0d6c120b287f4abf7e4ea0","datavalue":{"value":{"time":"+2020-12-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2217496$8DB435B0-636E-4E36-8732-0E0361845A80","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0e5d5c4ec5a42eafb7586ed70bac920f1dfabd87","datavalue":{"value":"https://arxiv.org/abs/2010.07275","type":"string"},"datatype":"url"},"type":"statement","id":"Q2217496$CDC4FBCD-1124-47F7-BC77-276301127CFC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"de0e5628c91e31072138d58e91bb3f4125edeb0c","datavalue":{"value":"The nondeterministic automatic complexity \\(A_N(x)\\) of a word \\(x\\) is defined as the smallest number of states in a non-deterministic automaton that accepts the word \\(x\\) and does not accept any other words of the same length. The \\(A_N\\)-complexity rate \\(A_N(x)\\) of an infinite word \\(x=x_1x_2\\ldots\\) is defined as the limit of the ratio \\(A_N(x_1\\ldots x_n)/n\\). When this limit is defined, it is always between 0 and 1/2. Random infinite sequences have \\(A_N(x)=1/2\\), periodic sequences have \\(A_N(x)=0\\); however, until now, no infinite words were known with intermediate values of \\(A_N\\)-complexity rate. The paper provides the first examples of infinite words for which \\(0<A_N(x)<1/2\\): Fibonacci and tribonacci words. The Fibonacci word is defined as the limit of a sequence \\(F_0=\\varepsilon\\), \\(F_1=1\\), \\(F_2=0\\), and \\(F_n=F_{n-1}F_{n-2}\\) for \\(n\\ge 3\\). The name comes from the fact that the length of \\(F_n\\) is the \\(n\\)-th Fibonacci number. A tribonacci word is the limit of a similarly defined sequence \\(T_0=T_1=\\varepsilon\\), \\(T_2=2\\), \\(T_3=0\\), \\(T_4=01\\), and \\(T_n=T_{n-1}T_{n-2}T_{n-3}\\) for \\(n\\ge 5\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2217496$A8F780F6-183C-4179-860D-B21362324713","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2217496$C7C7E94D-E043-43CF-8CF8-77A824FD1717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2217496$2F4740E5-1719-4496-816C-06F429E589B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2217496$A096D1F4-4722-488E-8F63-127D1261D77D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"078c80a5c1c3edc772677813cef745f7bcfde2ee","datavalue":{"value":"7289403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2217496$9972E439-859F-4823-98BA-993C3F06F9FC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e947dae1075270f052c0cc67197badae8ae984e3","datavalue":{"value":"nondeterministic automatic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2217496$5F2198E7-9D6C-42D7-B2E1-D3316AD0DF50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86ab5d46e49d26840e17a84022baa8b3adda4fa3","datavalue":{"value":"Fibonacci word","type":"string"},"datatype":"string"},"type":"statement","id":"Q2217496$70B37E6D-0DF4-4342-B28B-69F245190A29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c08ece7a236cc707c3068a6e57f250a224a85db","datavalue":{"value":"tribonacci word","type":"string"},"datatype":"string"},"type":"statement","id":"Q2217496$533B974A-8E44-44D6-A9C8-95596CBA200D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7a7a7a3dd3a08360856ececf3d8a629dcc430503","datavalue":{"value":{"entity-type":"item","numeric-id":592003,"id":"Q592003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$83DCFC09-BB75-4E42-A7AA-D63952363B29","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"20d7ccb33c14effccb9b9150138ce56c47127bfd","datavalue":{"value":{"entity-type":"item","numeric-id":54633,"id":"Q54633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$D25E6950-0493-4525-B403-1611C0FFF9C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8bf42d0fd66acf369e3d5d44d7ebef6adc7ae452","datavalue":{"value":{"entity-type":"item","numeric-id":56651,"id":"Q56651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$48BE5EB9-5A4F-4EA7-B249-37B0087163D1","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":"Q2217496$DA925222-C940-4281-A3EA-C0EF7B7B124D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c872c22832d9f9dea9b6a4132ad03da22a143d6b","datavalue":{"value":"W3095808584","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2217496$49F8DE91-CD42-4EF9-95E5-5F9DE7E4CEED","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e50a4d091a937d9228a035ba2c698c3b69cc876d","datavalue":{"value":{"entity-type":"item","numeric-id":4440308,"id":"Q4440308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$17C08CC6-9EE0-46F6-B5B8-BD1787B00FBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f293a41a2e6b880324e9ffce1ef09ba62c492f37","datavalue":{"value":{"entity-type":"item","numeric-id":2373756,"id":"Q2373756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$1FD524FF-2AF7-488D-B1F9-697905E7C1F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56f18c77577668fc9a76e80339fe1296a6aeb270","datavalue":{"value":{"entity-type":"item","numeric-id":490407,"id":"Q490407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$27E01B24-4BFE-4BCB-A37D-7C2B01249741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ce8b4bbd4dd2686ac274ad2909597abfcab7ed2","datavalue":{"value":{"entity-type":"item","numeric-id":1835915,"id":"Q1835915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$077C9EE1-99D2-4301-8392-E0301A855AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fda71fa925ae621d63545d48ff776cfd0d2a1fdd","datavalue":{"value":{"entity-type":"item","numeric-id":1694011,"id":"Q1694011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$5112ED32-FFF6-4815-B7C7-4C110A7B3F46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d4aae59eeb5a86f989db9541d7207bc36bab02e","datavalue":{"value":{"entity-type":"item","numeric-id":724846,"id":"Q724846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$5C9366E2-D6D6-4824-AE9E-8FEE94A25A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1e367eb05438b3971175a80baee7f1dd29c5b30","datavalue":{"value":{"entity-type":"item","numeric-id":5743090,"id":"Q5743090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$F7439BEA-6725-4D18-9C29-67A51BA1678D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5983095f40ef90bb78831426e9cf7d0528daa89","datavalue":{"value":{"entity-type":"item","numeric-id":4012668,"id":"Q4012668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$D8BACA32-571D-4A87-A7D8-C1833EFC46A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b8425e8209e6312a4bbffa91ef01a2b5e5a251f","datavalue":{"value":{"entity-type":"item","numeric-id":4531381,"id":"Q4531381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$FFB3E3A0-6EF2-407F-AC81-0DA499B5EFD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37cb1cf49e471b64ddbfdd38bf42e75ea1f2734e","datavalue":{"value":{"entity-type":"item","numeric-id":2372431,"id":"Q2372431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2217496$11CEA2A8-4FF6-483C-BED3-BA2CE28FC380","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5c41e12afea0715d47b62014d9512316c210def3","datavalue":{"value":"10.1016/J.DAM.2020.10.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2217496$1D6A769D-3101-4DD8-B098-7DCF2984DDBF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"750cbffca39b2cb68dc951ea043da9ecf5e0c1cb","datavalue":{"value":{"entity-type":"item","numeric-id":5246244,"id":"Q5246244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"264b287c95cc2f1529a4eda3c444b49e02d497d0","datavalue":{"value":{"amount":"+0.775105893611908","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":"Q2217496$0C9E589A-B4FF-4C3B-9C4F-FF903667430A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18407251d37920a2e4d0ffba5a47a8cb72705189","datavalue":{"value":{"entity-type":"item","numeric-id":2920445,"id":"Q2920445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"866f5132a4b254f0e358000451d9d4fc15323bf8","datavalue":{"value":{"amount":"+0.7691255807876587","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":"Q2217496$C62C3287-580C-4382-BC5C-3DC2672244B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24d9b47e773b07b4ee6ff662e88aeb1fb591b19e","datavalue":{"value":{"entity-type":"item","numeric-id":490407,"id":"Q490407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98ccf01afa71a04627e45838ee93c28c860905c8","datavalue":{"value":{"amount":"+0.7687475085258484","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":"Q2217496$8F2382D9-3DFE-4B46-94D6-25730A2DE8D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72e0de0d916ba58ee599f87e090a7119c1331f6b","datavalue":{"value":{"entity-type":"item","numeric-id":5088662,"id":"Q5088662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1601b37dd2233d2923ec1ec79e7464298529d4bd","datavalue":{"value":{"amount":"+0.7672283053398132","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":"Q2217496$02CA59B7-4782-4C18-A31E-B350D97E610A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7fcfe33899093d98ae4084faa0c65f86561f810","datavalue":{"value":{"entity-type":"item","numeric-id":5384332,"id":"Q5384332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43e2a0fb0a30f24a493352985a75a9e4e5a7230a","datavalue":{"value":{"amount":"+0.7546550035476685","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":"Q2217496$1C80D32D-F2AD-418C-B544-30DB0B30DCFC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2217496","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2217496"}}}}}