{"entities":{"Q1340682":{"pageid":1351421,"ns":120,"title":"Item:Q1340682","lastrevid":68504412,"modified":"2026-04-13T00:09:30Z","type":"item","id":"Q1340682","labels":{"en":{"language":"en","value":"Automata calculating the complexity of automatic sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 703940"}},"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":"Q1340682$9286618D-478D-4246-968C-5D10B4ACB88A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6c33d32eba41f330598307ffc2f34ed20ffd95eb","datavalue":{"value":{"text":"Automata calculating the complexity of automatic sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1340682$46C60070-4FAD-4CB3-8760-8BED25EC2394","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6dcca16b9262e2ee75af605f5aa61b8e2bfcd618","datavalue":{"value":"0815.11015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340682$D120F494-6F0A-4C9F-A179-5FE5A2C9C608","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"20c36d3fd96a8b8353287e0161cfbefcd7e6e333","datavalue":{"value":{"entity-type":"item","numeric-id":1340681,"id":"Q1340681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$ADB99713-D1C6-4D50-BE4F-1EA2E1FA9AB1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2af5fe3b27a04082f1eae9cf17090e68be06cc07","datavalue":{"value":{"entity-type":"item","numeric-id":194678,"id":"Q194678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$ADF49726-BDBC-440A-919B-68152065877B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cec237c4fe9357e0c2c90ebd7504d070f6073cc3","datavalue":{"value":{"time":"+1995-07-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1340682$60CB15AF-EA84-456C-9D35-327C2DBEEB8E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4de424ea60deb9624159244beebc17e8b3bd8d95","datavalue":{"value":"http://www.numdam.org/item?id=JTNB_1994__6_1_127_0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1340682$56239B7B-24B7-466E-89EF-8EC1BD729FE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c0ea6e7ebeb9a8b438fb2fc3f21b5fb700ab17d6","datavalue":{"value":"https://eudml.org/doc/225850","type":"string"},"datatype":"url"},"type":"statement","id":"Q1340682$71F90F6A-5450-4B4B-8004-67ECFECFC2B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"e3d5a9aa13a8c50d6c198e2e8692e03c46b80208","datavalue":{"value":"http://www.emis.de/journals/JTNB/1994-1/jtnb6-1.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1340682$C4E7A262-689F-4221-99C5-F21D4F8A16F0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ed74e33aff138125cf0d68dd3ce03c40eae59ed8","datavalue":{"value":"The complexity of a sequence on a finite alphabet is the function \\(n \\to \\rho (n)\\), where \\(\\rho (n)\\) is the number of factors (blocks) of length \\(n\\) of the sequence. In the case where the sequence is a fixed point of a uniform injective substitution and where the sequence takes only two values, the author shows that if the sequence is minimal, then \\(n \\to \\rho (n+1) - \\rho (n)\\) is generated by an automaton which is explicitly constructed. Note that, as indicated by the author, B. Moss\u00e9 has obtained more general results (Preprint, LMD).   The paper ends with an example, the Thue-Morse sequence, for which the result of the author implies the previously known result of complexity [see \\textit{A. de Luca} and \\textit{S. Varricchio}, Theor. Comput. Sci. 63, 333-348 (1989; Zbl 0671.10050) and \\textit{S. Brlek}, Discrete Appl. Math. 24, 83-96 (1989; Zbl 0683.20045)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340682$9039A701-EB5D-4825-8129-DEEFD3390FD6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1d3e055a17ce7fb6036131cf10d782136e2d9314","datavalue":{"value":"11B85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340682$37F67925-CBF1-4241-84D6-8715575B66FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340682$3AC9EC94-4B18-42C4-BDB8-7181C0923647","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340682$D6CD8260-D5DD-468A-99DF-F9A9429B2B4F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0d4a43efe6c4fb82fbb81220b174c61604366c96","datavalue":{"value":"703940","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340682$DDA747E1-53DC-483E-ACD2-1EF3EA66872E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e50b734d7a3583a654f5eb3937fc5e003966b3cc","datavalue":{"value":"automatic sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340682$B5EA40DB-59A0-474D-BDA6-1555D1B3106D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340682$912C52DE-5E50-483D-ACDB-645BC5A3FFAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1484d9165527900f2ecd9e3b2a7c6e8b90cf1370","datavalue":{"value":"Thue-Morse sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340682$7ECB2D91-1AD3-4073-8630-369707FB6FED","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"845abdf0c3e7df8eeaf94dc258fde16321cf5952","datavalue":{"value":{"entity-type":"item","numeric-id":187638,"id":"Q187638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$7CE921B0-1A11-4C49-A677-4D1E785CFA33","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":"Q1340682$3691FF53-0ECD-4B45-9464-193E496EB0DC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1135e4b2e0c24f646c6845af9e35807539730cda","datavalue":{"value":"W2314536985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340682$FF80D117-39E7-4928-A395-7390808F0D56","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a498955fd34a199b0e67a6f5978c928e4e5f1c69","datavalue":{"value":{"entity-type":"item","numeric-id":3700861,"id":"Q3700861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$2210E005-610B-4EF8-B790-201F6FA5508F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ca115817f94a9c98084ad7802061163cd4c63d7","datavalue":{"value":{"entity-type":"item","numeric-id":1824700,"id":"Q1824700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$B8E4BDFD-DD06-4AA7-8D08-2AE5444132F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3afd0c4cd5e96965dc58343fdb8134a63c6270c","datavalue":{"value":{"entity-type":"item","numeric-id":3926680,"id":"Q3926680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$7B39AC57-5646-4521-B756-B8FF4DD01BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e26ec61ad0b114755bec335b704577f3e8ceefbc","datavalue":{"value":{"entity-type":"item","numeric-id":5666530,"id":"Q5666530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$C5983CF8-3A9C-4112-AD91-46211AE923E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c035d92c562e4fd0990964f780131597f506546","datavalue":{"value":{"entity-type":"item","numeric-id":3228119,"id":"Q3228119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$E61385B9-51CF-42A2-8761-38E2761193F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2355482dbc37a911cde9b74ab32ffb5b6939f6","datavalue":{"value":{"entity-type":"item","numeric-id":3659988,"id":"Q3659988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$9ACBEFB4-DF5C-48C0-87A0-C3FAEEE8A0D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d569f9d620c09b82670d57dea945ca55100a0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1119694,"id":"Q1119694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$E3FD15DB-D1A3-47AD-B198-AC48213FA9D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77ca7621c1af71ca8f8e621631fbcaec70faa0e0","datavalue":{"value":{"entity-type":"item","numeric-id":3348040,"id":"Q3348040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$BFCA95EC-6C74-49B1-865D-01CFFD6F7657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66bd879155e83de9d1db3f55df1a2d92e93be14b","datavalue":{"value":{"entity-type":"item","numeric-id":1340682,"id":"Q1340682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340682$0A259D4A-225C-4DB9-B09C-264C5345698B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4efbf8471e7147024611c377e9f7c678c979fc41","datavalue":{"value":"10.5802/JTNB.109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340682$DEA6F43A-D6F4-4CE1-B125-0F704E981FFB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0a5dc1a1a498c4e0567135cb24960b3f6995503","datavalue":{"value":{"entity-type":"item","numeric-id":4716073,"id":"Q4716073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90ba5906b353fd9b4d6a1c42e50fc2922933edcc","datavalue":{"value":{"amount":"+0.8504922986030579","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":"Q1340682$F95B3B0A-3D8E-4CA2-BE87-A12C2CD1192F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6029c814b0fd77cda5eee953dfd6cfc276547a7d","datavalue":{"value":{"entity-type":"item","numeric-id":1280227,"id":"Q1280227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f18689c62ba9c6d6fd2032e312b26d3188d3de4c","datavalue":{"value":{"amount":"+0.8473183512687683","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":"Q1340682$74C5EC8C-2FCF-4B41-9EB9-63D156253A27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1384d2c540be6478ac48ace8a8ce4a0353e019f7","datavalue":{"value":{"entity-type":"item","numeric-id":5896135,"id":"Q5896135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5785ea693f262380c08048d6cf4584c42d0386fa","datavalue":{"value":{"amount":"+0.8466421961784363","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":"Q1340682$27AC10BC-07BB-4589-830F-48421B97EA7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9592386299797e597439dcace1e345f0197749e","datavalue":{"value":{"entity-type":"item","numeric-id":1320516,"id":"Q1320516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ffbb503c5d9d50ed3afa34e49ecf971552a931f","datavalue":{"value":{"amount":"+0.8137534856796265","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":"Q1340682$F1530366-BE93-473D-9C9D-3DFFEA8EB09B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c2f72cace8e2e7cab23f157fb5d2b988595d6ac","datavalue":{"value":{"entity-type":"item","numeric-id":837149,"id":"Q837149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5caee6709febebbb1f1c0fb93e8aaf09bcd1fc31","datavalue":{"value":{"amount":"+0.8084332346916199","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":"Q1340682$6ED086F7-E3F4-4FD4-8376-D0D98423B47D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Automata calculating the complexity of automatic sequences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Automata_calculating_the_complexity_of_automatic_sequences"}}}}}