{"entities":{"Q3216153":{"pageid":3226861,"ns":120,"title":"Item:Q3216153","lastrevid":110446709,"modified":"2026-11-17T00:29:15Z","type":"item","id":"Q3216153","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3881896"}},"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":"Q3216153$CC03F5CE-4460-4FC7-81CF-3D2863B2F850","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6968bff33940bdf971588277c67f1289e8608107","datavalue":{"value":"0553.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3216153$5FD38EF3-672E-492F-BDF3-C89C1C77A9B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae18174f96ec966ba5159ad379942ab8e70fc75e","datavalue":{"value":{"entity-type":"item","numeric-id":220253,"id":"Q220253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3216153$AC34B3FA-3482-43E1-B38D-F826732E737A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3216153$0CD7BD90-CA22-4EDC-9DE7-E2A6E337020B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3216153$08BCF733-8D70-441A-9E5A-5BB00D3BA49F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3216153$F2CA0735-FC60-4051-9372-C16DAACC63F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3216153$89D1291B-1540-4726-898D-B8FBBD7FBCB4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e22bc54d6b1d4491b0869077fcb6eeda8291c7e7","datavalue":{"value":"3881896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3216153$EF8DA3CA-2D5D-4624-BC39-06ED0A1EC813","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84f031d34ea756a6249039eba2868eeb81999b98","datavalue":{"value":"distance of words","type":"string"},"datatype":"string"},"type":"statement","id":"Q3216153$105477F3-872D-4768-8D82-3C8B562DBAB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3c81d409a96bae2243bfb8a21825bfebe2fe97c","datavalue":{"value":"Hamming metric","type":"string"},"datatype":"string"},"type":"statement","id":"Q3216153$4E17C28E-6088-4C3B-A7B9-22EEBDDCEFC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03e3531fbe0728531fb58fc7f0af6010c79045d6","datavalue":{"value":"recognition of approximate occurrence","type":"string"},"datatype":"string"},"type":"statement","id":"Q3216153$579EF23B-008A-40D9-B800-6B24C63BE53F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1e818a992e58200a05ed8e8e24a85648ff789ed","datavalue":{"value":"multi-head Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q3216153$63251B61-8AE2-4F94-8A45-B35DF635D1E6","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":"Q3216153$B93DA7A9-F9E7-476D-9203-7CAA07E6FF7C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27274bb6ef0cf203bea134fe97bae36003ba7b1b","datavalue":{"value":{"entity-type":"item","numeric-id":3830534,"id":"Q3830534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d915f8aeb63b42ac40e5c93b43397feb7551deb3","datavalue":{"value":{"amount":"+0.7789149880409241","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":"Q3216153$6880189A-9FA8-4D63-9587-95E9A1856A7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb98a1c2f7aeea452fcbca238ff6ea26c32cff0a","datavalue":{"value":{"entity-type":"item","numeric-id":3579401,"id":"Q3579401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06fe5d958ee5207c5d926dae6c8a2ecaad6ecb3e","datavalue":{"value":{"amount":"+0.7662413716316223","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":"Q3216153$95E01F55-759B-4158-9295-495FC27FE7CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfe908519277c16ce4a40874fe214838a43a7a89","datavalue":{"value":{"entity-type":"item","numeric-id":5393960,"id":"Q5393960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26f2ea4cde5836060f185c2ed7ecb6d23425c734","datavalue":{"value":{"amount":"+0.7614238262176514","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":"Q3216153$E0DD5CC9-06FF-427E-9AF1-3B923E5C59B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d9f690a8dd26aa38cf7b9b9e303712f8fcf0346","datavalue":{"value":{"entity-type":"item","numeric-id":4292787,"id":"Q4292787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e7685beaf2af6a58349d2d308e6b4d47f7e4ba2","datavalue":{"value":{"amount":"+0.7531670928001404","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":"Q3216153$68ED3754-FFE7-4E16-9732-4EBAEBFDBBD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3cf6837f9d808e1efcb4c0a8062d1a76926932f","datavalue":{"value":{"entity-type":"item","numeric-id":2380061,"id":"Q2380061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b068253457a6d482d8dbeecf4f7c86f4d413f42","datavalue":{"value":{"amount":"+0.7503869533538818","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":"Q3216153$16035FC2-1377-4E68-9C4A-7EE0D8FBC8E9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cd6f8db2331a3e6140a44f9b294e08257c4bbcfa","datavalue":{"value":"Let the alphabet \\(\\Sigma\\) consist of quotients i/\\(\\nu\\), where \\(\\nu\\) is a natural number, i is an integer from the interval [-\\(\\nu\\),\\(\\nu\\) ], \\(A=a_ 1,a_ 2,...,a_ r,\\quad B=b_ 1,b_ 2,...,b_ r\\) be two words over \\(\\Sigma\\) of equal length. The distance between A and B depends on metrics defined on the set of all words over \\(\\Sigma\\). The following metrics are considered: 1. Hamming metric \\(l^ 0:\\) \\(\\rho_ 0(A,B)=\\sum^{r}_{j=1}sign| a_ j-b_ j|;\\quad sign x=0\\quad if\\quad x=0,\\quad 1\\quad otherwise.\\) 2. Metrics \\(l^ n\\); \\(n=1,2,...:\\quad \\rho_ n(A,B)=(\\sum^{r}_{j=1}| a_ j-b_ j|^ n)^{1/n}.\\) 3. metric \\(l^{\\infty}:\\) \\(\\rho_{\\infty}(A,B)=\\max_{1\\leq j\\leq r}| a_ j-b_ j|.\\) The words A, B are \\(\\epsilon\\)-similar in a metric \\(\\mu\\) if they are of equal length and \\(\\rho_{\\mu}(A,B)\\leq \\epsilon\\). The problem of recognition of approximate occurrence is: for fixed \\(\\epsilon\\geq 0\\) and two words V, U over \\(\\Sigma\\) to determine, whether U contains a subword \\(\\epsilon\\)-similar to v in the metric \\(\\mu\\). The author considers the solution of the problem on multi-head Turing machines in real time in three different formulations depending on the way of representation of the input data. The main result is: for every \\(\\epsilon\\geq 0\\) and every metric \\(l^ n\\) (n\\(\\in N)\\) there exists a Turing machine solving the problem in two formulations. As to the third formulation, there is no Turing machine solving it in real time. For the metric \\(l^{\\infty}\\), effective algorithms were known earlier.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3216153$7DA77BCE-6007-4C5A-9E5D-E2C4D5E7D242","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3216153","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3216153"}}}}}