{"entities":{"Q1622966":{"pageid":1633706,"ns":120,"title":"Item:Q1622966","lastrevid":71537766,"modified":"2026-04-13T22:55:08Z","type":"item","id":"Q1622966","labels":{"en":{"language":"en","value":"Counting subwords and regular languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6983381"}},"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":"Q1622966$BD1B015C-4BB6-44CD-BDED-4943EDA423EE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c1bb021e0d3906846066ed27868ca73005955575","datavalue":{"value":{"text":"Counting subwords and regular languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1622966$54358B4D-639B-46A9-B559-F705B820B3A9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c3f007413a9d0a2093be96a00a0dc2ec835ecfe1","datavalue":{"value":"1404.68067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1622966$D08FAECE-FDE5-4C37-9387-9A8AACA0FEE3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"785495c6f0ea4c048894b9dd88a38e1aa0ad56d5","datavalue":{"value":"10.1007/978-3-319-98654-8_19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1622966$16407CDC-A888-4974-BC03-90C17423EE21","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbbdc3381c094a1abe2cf60ed445a4984b25837b","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1622966$64A6A380-239D-4F51-BBFA-68E8C83926C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"94a204b0c4eee29ee3d1c055bf8b47e7b8e45f74","datavalue":{"value":{"entity-type":"item","numeric-id":1622964,"id":"Q1622964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1622966$6F40AFD2-3D94-4B70-AD0A-68AAB5B5B457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"24529d47f999525a43d361dedf791d116ffd3703","datavalue":{"value":{"entity-type":"item","numeric-id":1622952,"id":"Q1622952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1622966$DB94D3AB-7F77-4300-9755-2B9B44FCF8D5","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":"Q1622966$512C2764-E94A-4DF9-990D-15C84BE7538B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"18cf30b5eb4a6f9f904a0abe2b57b56fd1dee870","datavalue":{"value":{"time":"+2018-11-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1622966$8A6DF047-E992-464D-8D41-D49104917AE8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d24bd0f9f118671cc4d28ea1946b3d8d3a7b8692","datavalue":{"value":"https://arxiv.org/abs/1804.11175","type":"string"},"datatype":"url"},"type":"statement","id":"Q1622966$181D69A1-9B57-4989-B500-876C520590FA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ff7ab077a8a4a4045edd0fc4ac0932e83b1b5cf","datavalue":{"value":"For a pair of words \\(x\\) and \\(y\\) the languages \\(L_{x=y}\\), \\(L_{x<y}\\), and \\(L_{x \\leq y}\\) consist of all words \\(z\\) such that the number of occurrences of \\(x\\) as possibly overlapping subwords of \\(z\\) is, respectively, the same, less than, or less than or equal to the number of occurrences of \\(y\\). Such languages are always deterministic context-free and the paper gives neccessary and sufficient conditions for regularity of these languages.  The word \\(z\\) is said to be bordered by a non-empty word \\(x\\), or \\(x\\)-bordered, if \\(x\\) is a prefix and a suffix of \\(z\\). If \\(y\\) is a subword of every \\(x\\)-bordered word then \\(x\\) is called interlaced by \\(y\\). The authors prove that the languages \\(L_{x=y}\\) and \\(L_{x<y}\\) are regular if and only if either \\(x\\) is interlaced by \\(y\\), or \\(y\\) is interlaced by \\(x\\). This criterion can be tested by checking the emptiness of two regular languages. The set of all \\(y\\)-bordered words \\(z\\) such that \\(x\\) is not a subword of \\(z\\) is the language \\((\\Sigma^*x\\Sigma^*)^c \\cap y\\Sigma^+ \\cap \\Sigma^+y\\), where \\(\\Sigma\\) is the underlying alphabet, and \\(L^c\\) is the complement of \\(L\\) with respect to \\(\\Sigma^*\\). Such construction leads to an algorithm that decides regularity of \\(L_{x=y}\\) and \\(L_{x<y}\\) in \\(O(|\\Sigma||x||y|)\\) time. The authors provide a more efficient procedure. They prove that \\(y\\) is interlaced by \\(x\\) if and only if \\(x\\) is a subword of \\(yty\\) for all words \\(t\\) of constant length \\(C\\), where \\(C=1\\) if \\(|\\Sigma|\\geq 3\\), and \\(C=3\\) if \\(|\\Sigma|=2\\).  In the last section the authors consider conditions for finiteness of \\(L_{x=y}\\) and a generalization for more then two words. The language \\(L_{x=y}\\) is finite if and only if \\(|\\Sigma|=1\\) and \\(x\\neq y\\) (the proof is omitted in this paper). For the generalized language \\(L_{x_1=x_2=\\ldots=x_n}\\) it is proved that this language is infinite if \\(|x_1|=|x_2|=\\ldots=|x_n|\\). General conditions for finiteness of such languages remain open.  For the entire collection see [Zbl 1398.68030].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1622966$F3810223-96D5-457D-A19B-588E0521CA13","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f114df5b76cccfc051bac5f0998d94d41f91ce92","datavalue":{"value":{"entity-type":"item","numeric-id":1622965,"id":"Q1622965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1622966$70B3377D-DB7E-4D58-9E75-4127A66A9CF2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1622966$4F1259C6-2EF8-429C-AE9E-61849804CEB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1622966$720B71E5-ED5E-4127-9E71-62643BF2C5B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f8ed4f9fe0f019a55e6738535e0efe623d6f2202","datavalue":{"value":"6983381","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1622966$18483135-479F-4928-A640-CBB4DDEBA61A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4c8dd840f6048e347b2ee34c967bfcf9cb4c134","datavalue":{"value":"subwords counting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1622966$A96951AB-75A5-4689-BB05-D4C8343F2864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7142d39c3323636bd7cc377526eabf4365b5d436","datavalue":{"value":"regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1622966$D4BD66AE-D09D-4631-8E55-BCF33845EB1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed96de97b0a609b359b7c86a233bcbfc19923f4a","datavalue":{"value":"finiteness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1622966$58EC5C5A-7A9A-448D-A3B9-7D2C91BFE46C","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":"Q1622966$23E3B8F3-13D0-4ED1-9531-9F5F85FBA5A1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c421bdd1a0a4083767ce8d2b7ff26b20dfc2ceb9","datavalue":{"value":"W2798939578","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1622966$7EAEE9B4-922F-444F-91C1-81CC1D87AF89","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"646f6933649029a5fb240c19b6a93cfb1b7fcf0b","datavalue":{"value":{"entity-type":"item","numeric-id":2380451,"id":"Q2380451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f228e36a47af4e46dc86a01a3fd0fe9629f64bec","datavalue":{"value":{"amount":"+0.9041999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1622966$1D256F46-FF7B-4CDB-BD70-0095A5AA3F0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b981322725ff7d7a1ca8489b37573abd22142dca","datavalue":{"value":{"entity-type":"item","numeric-id":5387681,"id":"Q5387681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e33dace33fccdb8d11622fc8df25c76d58497e5e","datavalue":{"value":{"amount":"+0.89770436","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1622966$14BF0B2B-33A0-4D9B-AD1F-AA537EB3EC65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6bda607e3555eb6f76d28605e5978875774500e","datavalue":{"value":{"entity-type":"item","numeric-id":3173481,"id":"Q3173481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"661705dabd206844ec295f4542372b7a27e42b21","datavalue":{"value":{"amount":"+0.89696","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1622966$83C73773-F343-4230-AB91-0F5312C9F306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58449d5da65405680653a252e2e44b84400994c0","datavalue":{"value":{"entity-type":"item","numeric-id":2352065,"id":"Q2352065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e8d00ebbfbbb5dae68b6b89e067c5b370bb7081","datavalue":{"value":{"amount":"+0.8926172","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1622966$F29BBB44-0670-47BD-BFE0-778504942F72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a139e82631b549a7c58e5ce63fa38eb31b515e8","datavalue":{"value":{"entity-type":"item","numeric-id":840765,"id":"Q840765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7a3c88491b5524e2684b63097d567a892ce2d25","datavalue":{"value":{"amount":"+0.88925993","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1622966$5833660F-70AB-40CF-B2CC-6DA79CAA2443","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9c2f7111f5769d38840473cfdaa32d255d75225","datavalue":{"value":{"entity-type":"item","numeric-id":5384333,"id":"Q5384333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19e7e7678ef955f21e9ca57aadefff512ab4251a","datavalue":{"value":{"amount":"+0.88429207","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1622966$7D4C654A-973C-4E69-BBF5-8C9739FA023C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c785c2e59aed57c0f043b0e8a4f47faf64beeb6c","datavalue":{"value":{"entity-type":"item","numeric-id":3503909,"id":"Q3503909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e4acd6ae7d3a7944785f74c3a8c763297598e86","datavalue":{"value":{"amount":"+0.88168424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1622966$6B3A0660-D9C3-44BC-96D0-FF575DB61D4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0a5ce49d9f9b891b6db1d751a718081190457a3","datavalue":{"value":{"entity-type":"item","numeric-id":4483919,"id":"Q4483919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c396186cae48119835c5ba242ddae9aa4740ab3c","datavalue":{"value":{"amount":"+0.8815565","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1622966$421E7A97-9825-4769-9A27-E4DFE2B9588F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b8c7899255d0637a7bc3762ebc46126fb1d0adb","datavalue":{"value":{"entity-type":"item","numeric-id":376559,"id":"Q376559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b79a14126098e0640cb3a2630a4db99ed0363581","datavalue":{"value":{"amount":"+0.88109857","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1622966$D9CCE0A3-50A3-40A2-B101-692A37B5DF16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94814c19adc0d566a6c5edcccb064758c53833e0","datavalue":{"value":{"entity-type":"item","numeric-id":5692151,"id":"Q5692151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48dc2b7be5abcf17d46490a2a4a9fe4d6d123619","datavalue":{"value":{"amount":"+0.88076866","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1622966$65053144-CD92-4480-9419-719AB909438F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Counting subwords and regular languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Counting_subwords_and_regular_languages"}}}}}