{"entities":{"Q1190468":{"pageid":1201217,"ns":120,"title":"Item:Q1190468","lastrevid":66517674,"modified":"2026-04-12T10:36:56Z","type":"item","id":"Q1190468","labels":{"en":{"language":"en","value":"Pattern spectra, substring enumeration, and automatic sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 55528"}},"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":"Q1190468$11D6A3FB-9334-4B34-85DE-43AE590394CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d14db6bc68596aeed230822a5c2da118514b2ebf","datavalue":{"value":{"text":"Pattern spectra, substring enumeration, and automatic sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1190468$D763B065-3E67-40DA-8CB7-3BDF00852263","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5902efc1f493a8cd004a3eac3bbfaf0cdb72203f","datavalue":{"value":"0753.11012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190468$1E322607-C7E2-4C10-ADA7-C273B24EA7D3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"47a8ef690302b0cd9cd39b0a84d146f90038e8f9","datavalue":{"value":"10.1016/0304-3975(92)90032-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190468$E97CDAF5-EC4F-4799-A068-38395B30A0D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2567c660209f6562a38c120275cc4718c295466a","datavalue":{"value":{"entity-type":"item","numeric-id":466151,"id":"Q466151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$BBC2D16C-D092-4850-A11B-79ECE8A0962C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab96f30ed40d3ebcd6538eddee3d78ff2ad4c7ea","datavalue":{"value":{"entity-type":"item","numeric-id":187638,"id":"Q187638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$BEABBB18-E728-4D36-A191-27B446C8EDD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"acbe3fcdaa2e72f3bce067779bfee150bff0b503","datavalue":{"value":{"entity-type":"item","numeric-id":405317,"id":"Q405317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$69EBBA07-5446-4E24-8768-137BBA6EC0A1","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":"Q1190468$A85DFB46-38CB-4324-9245-DB720DC11BFA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9b40ce89936be2de8343a01d1ced7ff59f76b3e","datavalue":{"value":{"time":"+1992-09-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1190468$E74B95B1-EAB7-4E5C-A00A-39C116D1F322","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"23d8dfd39e586a604d10344ef7c7c5efc5cf6a98","datavalue":{"value":"Let \\(P=p_ 1\\ldots p_ h\\) be a binary pattern, i.e., a string of 0's and 1's such that \\(p_ 1=1\\) and let \\(a_ P\\) be the corresponding pattern sequence defined by \\(a_ P(n)=(-1)^{e_ P(n)}\\) where \\(e_ P(n)\\) counts the number of occurrences of \\(P\\) in the binary expansion of an integer \\(n\\geq 0\\). \\textit{P. Morton} and \\textit{W. J. Mourant} [Proc. Lond. Math. Soc., III. Ser. 59, 253-293 (1989; Zbl 0694.10009)] showed that every sequence \\(s\\) on \\(\\{+1,-1\\}\\) can be uniquely expressed as the product \\(s(n)=s(0)\\prod_{P\\in{\\mathcal P}}a_ P(n)\\) where \\({\\mathcal P}\\) is a finite or infinite set of patterns. One of the main results of this paper (Theorem 2.1) says that the sequence \\(s\\) is 2-automatic if and only if \\({\\mathcal P}\\) is a regular set of words on the alphabet \\(\\{0,1\\}\\) that is to say \\({\\mathcal P}\\) is recognizable by a finite 2-automaton.   This theorem is introduced by some interesting examples and is extended to the following purely language-theoretic result: Let \\(\\Sigma\\) be a finite alphabet and let \\(\\Sigma^*\\) be the set of strings drawn from \\(\\Sigma\\). For strings \\(r\\) and \\(w\\) define \\(\\sigma_ r(w)\\) to count the number of occurrences of \\(r\\) as a substring of \\(w\\) (for \\(r\\) equal to the empty string, \\(\\sigma_ r(w)\\) counts the length of \\(w\\) plus 1) and for any language \\(L\\subset\\Sigma^*\\) define \\(\\sigma_ L:\\Sigma^*\\to\\mathbb{N}\\) by \\(\\sigma_ L(w)=\\sum_{r\\in L}\\sigma_ r(w)\\). Now we consider, for any integer \\(k\\geq 2\\), the Nerode equivalence \\(\\sim_ k\\) on \\(\\Sigma^*\\) given by  \\[ w\\sim_ kw'\\Leftrightarrow\\forall v\\in\\Sigma^*,\\quad\\sigma_ L(wv)=\\sigma_ L(w'v)\\bmod k. \\]  We shall say that \\(\\sim_ k\\) is finite if the set of classes \\({\\Sigma/\\sim_ k}\\) is finite. Then (Theorem 4.1) the following properties are equivalent: (i) The language \\(L\\) is regular; (ii) The equivalent relations \\(\\sim_ k\\) all are finite; (iii) At least one relation \\(\\sim_ k(k\\geq 2)\\) is finite (in other words, following the terminology of the authors, the map \\(w\\mapsto\\sigma_ L(w)\\bmod k\\) is given by a finite \\(\\Sigma\\)-automaton with outputs). In the definition of \\(\\sim_ k\\), without changing the result, the map \\(\\sigma_ L\\) can be replaced by \\(\\pi_ L:w\\mapsto\\pi_ L(w)\\) where \\(\\pi_ L(w)\\) counts the number of strings in \\(L\\) which occur as a prefix of \\(w\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190468$6B423612-9133-4445-8BA5-754EBCD5EC97","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1d3e055a17ce7fb6036131cf10d782136e2d9314","datavalue":{"value":"11B85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190468$355AD416-690F-4937-93BE-84AC8020970D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190468$BF5E786B-6D88-4DED-9E8C-39F2EC4CD42D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2c065bbf9959c8ea7b0b915b4d7d25857cdd6f14","datavalue":{"value":"55528","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190468$F76CE562-E0D4-432C-B62C-2ECC72ED92D5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e50b734d7a3583a654f5eb3937fc5e003966b3cc","datavalue":{"value":"automatic sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190468$4213F36C-ED31-4FF8-82B2-461505F237DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1afa9cba412830e2a1c834561a16562439984d00","datavalue":{"value":"formal regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190468$1BE2A8BC-7C70-4B21-BF48-329C81076277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae07fe120276ee4c21c2b056394433e1dd18622","datavalue":{"value":"automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190468$6282A054-D0B5-461C-89F2-AC6F07E5B7E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"663c45697158eb2353e18a33d07994589a1aae66","datavalue":{"value":"subsequence of Prouhet-Thue-Morse sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190468$A8836A1D-A9C1-4265-B0A5-C0EEC922AA73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d8f59b7eebf99e1b74b0da94e6e0b9f845c9166","datavalue":{"value":"sequences given by special infinite products","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190468$8A063A8C-A2CD-4A15-AFE7-E689DEBCF206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7171a0238a96e0e07bbcbea3ece39fe64cb30815","datavalue":{"value":"pattern spectrum","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190468$7574C72F-09CC-47CE-B67A-A1CD71F4EC71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8314cda3d2b7b8b4a21b97ec24e8c574614b6059","datavalue":{"value":"substring enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190468$B165F42B-AB8C-4284-8C09-7F2D4E57B235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d823df02b962d6384b5fa0c910061a1d734d8845","datavalue":{"value":"pattern sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190468$1E706537-9BA7-426D-AE4C-16A6A0818404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77af32316044d22e902ea4e89f97a84245d55c66","datavalue":{"value":"binary expansion","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190468$28801586-8B29-4DB3-A63B-5FADAEE3AF6B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e6366161d478a65d3fe79748e17a49e2ece69d8c","datavalue":{"value":{"entity-type":"item","numeric-id":194683,"id":"Q194683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$4E454EAF-817D-4626-9667-1B1555B252CE","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":"Q1190468$34008756-639D-41F3-8D08-57FA941E7752","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d26cf36123e2dfb617bc2e6b72d6da09946a13a","datavalue":{"value":{"entity-type":"item","numeric-id":1100506,"id":"Q1100506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$FDA97095-26C5-468F-989E-9806FD0BD3BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7c43117cea60c59d3bfb4db352e1aefefce7397","datavalue":{"value":{"entity-type":"item","numeric-id":3975928,"id":"Q3975928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$173CA952-996F-49F2-9286-A70F3F1BCF4A","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":"Q1190468$12990195-00EA-43C1-8D36-120C34ADFF67","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":"Q1190468$E5FB5CC2-0CF3-40FB-A40D-40B3E5DEF6CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2332710ae4e4b459778c57d49f4efb8c84a736b","datavalue":{"value":{"entity-type":"item","numeric-id":786842,"id":"Q786842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$05C7C92A-695C-4EB6-88F3-A4FCFE6E360E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$8CDF1B4E-55BA-4457-AC51-E0B94E8CE46F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96f74cb6e126315d1083901b94dce5325c33cdbc","datavalue":{"value":{"entity-type":"item","numeric-id":3469156,"id":"Q3469156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$E68B256F-676C-4D8A-BB6F-2AEF1287421F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"651260f858bb6df7e41de61da0a769fc2139fc9d","datavalue":{"value":{"entity-type":"item","numeric-id":5590132,"id":"Q5590132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$7371E426-17FF-481D-A8EE-9DCF5103AD81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da419e5610e78114924a84f37ebd2a5928559968","datavalue":{"value":{"entity-type":"item","numeric-id":4087299,"id":"Q4087299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$80202D4F-55A1-412B-9BDF-1CFD94B7A0E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4721bce81f625ef17f4eb7dd84348febbe033861","datavalue":{"value":{"entity-type":"item","numeric-id":3348041,"id":"Q3348041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190468$F1B6CA4E-9132-45B8-A871-93003B14172F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2daa41747b6802cbdb298db6ba6076896b37433","datavalue":{"value":{"entity-type":"item","numeric-id":1193879,"id":"Q1193879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d84f516d56b167d1e37b4f38dfc51139d3299d53","datavalue":{"value":{"amount":"+0.7954198122024536","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":"Q1190468$18B1D340-0700-49FD-9406-100F5DF15DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e00f13bcd2e66914ced4c2d7bd1259013a1ae37a","datavalue":{"value":{"entity-type":"item","numeric-id":4902892,"id":"Q4902892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c2107768261798cab69248ca9e9cd76f8805f96","datavalue":{"value":{"amount":"+0.7937455177307129","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":"Q1190468$FE7057E6-579A-4926-8528-72A538B8F2D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d0954c26525fa75b47292c1606a37d1ddb4abd1","datavalue":{"value":{"entity-type":"item","numeric-id":4431260,"id":"Q4431260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3baec9b703f534d9eaefedbe916e0ceb1792d4a6","datavalue":{"value":{"amount":"+0.788250207901001","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":"Q1190468$CD818BE2-9EF6-4ECB-B660-543FBB3D10D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"816c48a57484c61ee0d5df4eaddebecc6d082471","datavalue":{"value":{"entity-type":"item","numeric-id":2973213,"id":"Q2973213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ac23e7b3e4992b7c25c5d7119de77e357cd9f08","datavalue":{"value":{"amount":"+0.7879320383071899","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":"Q1190468$05C3F0B8-580E-4B23-8B45-3A5C3273783D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"171452d600f094d69082da5ef7bb8292a16b6359","datavalue":{"value":{"entity-type":"item","numeric-id":3975928,"id":"Q3975928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a45f6f672bd4496c7fce997c0a9e7a135a33566f","datavalue":{"value":{"amount":"+0.785362184047699","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":"Q1190468$F3D2316A-D2ED-4BF0-B4B5-41A5A15DE2AE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Pattern spectra, substring enumeration, and automatic sequences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Pattern_spectra,_substring_enumeration,_and_automatic_sequences"}}}}}