{"entities":{"Q1894266":{"pageid":1905008,"ns":120,"title":"Item:Q1894266","lastrevid":82029446,"modified":"2026-05-06T19:56:01Z","type":"item","id":"Q1894266","labels":{"en":{"language":"en","value":"On the construction of perfect deletion-correcting codes using design theory"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 777665"}},"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":"Q1894266$81083136-4837-4AE2-ADEB-6986F2841351","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8006733ff99d7524e2b93d25ae4616ccd3df62f8","datavalue":{"value":{"text":"On the construction of perfect deletion-correcting codes using design theory","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1894266$68125ED7-B444-4D6F-A60D-AD9B03E05A9A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6e38782643ef58a8c214283ee8f0426712e18c39","datavalue":{"value":"0866.94023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894266$27620932-8C8F-4D3F-861E-2AF6497EFD2D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0afe6fe527451dcc6ffcd5f703533a98ba29f101","datavalue":{"value":"10.1007/BF01390767","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894266$B05FEB25-4DF5-4151-9B2A-8F77F2F285B7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"df82569d0d4af90ca208907c7063c0b4a2f597e1","datavalue":{"value":{"entity-type":"item","numeric-id":1894265,"id":"Q1894265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$0DB663C3-E6C1-4256-9A31-AD2A789EF09C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fb34abbf39f11094509111953e4c62a22b1e3897","datavalue":{"value":{"entity-type":"item","numeric-id":115940,"id":"Q115940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$284C3E69-79CB-4C50-8849-DA9A27ACBDE0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"561fef158dda690e7f8fb24066d086b7abc285a0","datavalue":{"value":{"time":"+1995-07-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1894266$5DDCA4A0-B012-4600-9F5C-86095A267266","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f537d4110fc2a726ada62bd463d6529922021874","datavalue":{"value":"Let \\(F\\) be an alphabet; if \\({\\mathbf x}\\in F^n\\) and \\({\\mathbf y}\\in F^m\\) are words over \\(F\\) with \\(n\\leq m\\), then we call \\({\\mathbf x}\\) a subword of \\({\\mathbf y}\\) if \\({\\mathbf x}\\) can be obtained from \\({\\mathbf y}\\) by deleting \\(m-n\\) symbols (anywhere in the word) or, equivalently, if \\({\\mathbf y}\\) can be obtained from \\({\\mathbf x}\\) by inserting \\(m-n\\) symbols (anywhere in the word).    A code \\(C\\) of length \\(k\\) over \\(F\\) is said to be a \\(t\\)-deletion/insertion-correcting code if each word of length \\(k-t\\) over \\(F\\) is a subword of at most one codeword in \\(C\\). A variant of this definition requires that the entries in each codeword are all distinct and that each word consisting of \\(k-t\\) distinct symbols of \\(F\\) is a subword of at most one codeword in \\(C\\). In either case, the definition of a perfect code is obtained by replacing ``at most'' by ``precisely''.    Apart from some bounds on the size of a \\(t\\)-deletion/insertion-correcting code, both in the general and in the perfect case, the paper is primarily concerned with the existence problem for perfect 2- or 3-deletion/insertion-correcting codes of length 4 or 5. The author gives necessary and sufficient conditions for the existence of such codes in terms of the size \\(|F|\\) of the alphabet. The only cases for which the existence problem remains uncovered by the author's constructions are \\(|F|=13,14, 15,16\\) and \\(|F|\\equiv 7\\) or \\(8\\bmod 10\\), \\(|F|\\geq17\\).    Some of the presented constructions are based on ordered designs, that are designs in which the blocks are ordered \\(k\\)-tuples with the requirement that every ordered pair of elements is contained as a subword in a fixed number of blocks, usually one. Another series of constructions is based on modifications of existing codes to produce new ones, in particular a procedure based on the extension of the ground alphabet by adjunction of a new symbol and a procedure in which the codewords are punctured at a given symbol or pair of symbols, and then a system of distinct representatives is found for the sets formed by the remaining symbols, in order to get a suitable replacement.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894266$58F98DEA-CD12-4F4F-A01E-9498CEF34113","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0c3cdafa68da1cd8441c02cae1d4f7b344a92c14","datavalue":{"value":"94B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894266$0B19247C-4563-4414-9EF1-C8A25921A84F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0777d7ff21c1f44314f8092c977cf5f02a5fe09c","datavalue":{"value":"05B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894266$90845197-B97B-4C67-87A8-B32A4B1E0FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894266$8B600FF0-585D-4A24-B3DB-03553D843CFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5120626c87fbc492ba1414fde6695c15d7ff0d86","datavalue":{"value":"94B27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894266$2FECB25A-DB2D-4AC1-BC6D-71C9F050A459","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a8c61482c08ac1e8c28440b70ce9b3718bc54b69","datavalue":{"value":"777665","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894266$35B85E3B-E0CA-4624-96AD-2D79D5AD24FD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1702deca82a534292688ea779a0a1180a236469","datavalue":{"value":"ordered block-design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894266$1D7EED2F-3D14-4C5A-A60D-961629D839C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e10b967c4f97de23da2178cb3b583a02292083a4","datavalue":{"value":"\\(t\\)-deletion/insertion-correcting code","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894266$E8D01053-5ABD-453B-8E2E-7C53BE65CA23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69fd747d2dc250661ed6d47408fd029fa70d0c61","datavalue":{"value":"perfect code","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894266$4B54ADDC-A2CC-4232-BB16-8C3DD3281680","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"971b33ebfc3ad2ab5ce34e65c6d2dddf842ca67b","datavalue":{"value":{"entity-type":"item","numeric-id":676696,"id":"Q676696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$B2601F8F-9F78-445C-B2BC-F97801C6414A","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":"Q1894266$BDEAAF37-BD1F-477D-B61A-8EC53A2C35D1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9e850f1bd4346f097c93b02e76d17fbd9c7fad7","datavalue":{"value":{"entity-type":"item","numeric-id":5556159,"id":"Q5556159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$CED96427-770D-470C-A16B-797DBDCF9E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42c514a452083db14ddaea4887a88b8660769487","datavalue":{"value":{"entity-type":"item","numeric-id":5604958,"id":"Q5604958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$E9F78130-7A0E-44D0-9D14-523C5622499F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"630bb49ff3334127371a7f53010ef2bb1269da78","datavalue":{"value":{"entity-type":"item","numeric-id":5826130,"id":"Q5826130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$DF1CA639-D90E-4CC7-8E8F-E24A2C746D3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96fb9556bb70bd6fc88917c3eec47ba236054563","datavalue":{"value":{"entity-type":"item","numeric-id":3294602,"id":"Q3294602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$43452D3A-C329-485B-8E77-B1DF21F78EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de47eddbf25d58b5ce11327489e2afcb8ceb97bd","datavalue":{"value":{"entity-type":"item","numeric-id":2555853,"id":"Q2555853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$E6C55B50-F081-4778-AD89-92EEB6396C1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85583840807b08c407a14ab153680275899e9267","datavalue":{"value":{"entity-type":"item","numeric-id":4307351,"id":"Q4307351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$A282738F-7715-4283-BF20-437EF66D7D8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed790b782026ca0af1f2f2c8daa26146bb247bd0","datavalue":{"value":{"entity-type":"item","numeric-id":4002255,"id":"Q4002255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$F355DBD4-49F7-4490-81DD-F28315347BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70029b6af057fae98f41b34486107a0b56af97f4","datavalue":{"value":{"entity-type":"item","numeric-id":3847740,"id":"Q3847740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$D363B9A5-2797-4690-A580-3959C8736CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4eb9c77afaedc85d86ff7d3f65ead581beff499b","datavalue":{"value":{"entity-type":"item","numeric-id":3903012,"id":"Q3903012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$443B103F-4F13-463D-AD28-D00437B8F60F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7809b238773269d7c973df0cb7ef1610e880dbdc","datavalue":{"value":{"entity-type":"item","numeric-id":3901526,"id":"Q3901526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$DB4B4B2B-76BD-46CE-B117-AFC7A06F73CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4707efca0339cb58b2d42cfa6b63f48ccbc8d508","datavalue":{"value":{"entity-type":"item","numeric-id":4087069,"id":"Q4087069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$5021CE9F-DE69-478A-869A-6DDF0C47C1F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d88e8cddb21eade56ca5fb962a16b8a6ffa85e5d","datavalue":{"value":{"entity-type":"item","numeric-id":3218062,"id":"Q3218062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$CC6D7594-7E9F-4372-9006-D6D9298CDF97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c1b7635780772ba645f9b3de39a756f708a170c","datavalue":{"value":{"entity-type":"item","numeric-id":5519681,"id":"Q5519681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894266$238F1F44-BA65-4792-A982-5555882B9637","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96f7821ba2cb5a5219918d4f52bf4ccc6a476985","datavalue":{"value":{"entity-type":"item","numeric-id":4452468,"id":"Q4452468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93fe797d2248888f6459cd5555426dea0c4925fb","datavalue":{"value":{"amount":"+0.8851515650749207","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":"Q1894266$8717CB69-54A3-48D2-9C7B-37B6ACF4C672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bb29dc87fcb9a3c95847b9b78139ebbbeccf028","datavalue":{"value":{"entity-type":"item","numeric-id":3548101,"id":"Q3548101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15140308268635dcf5688417035ed09b37f0a0f3","datavalue":{"value":{"amount":"+0.8705307245254517","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":"Q1894266$695923FA-7EC0-4A29-87DE-5DC5954DCDB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fded3b7908c719a2063d3504948a7289b230840","datavalue":{"value":{"entity-type":"item","numeric-id":1379664,"id":"Q1379664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6a38f768415bae492ff978ac8d5962d293c7c71","datavalue":{"value":{"amount":"+0.8541172742843628","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":"Q1894266$2F09A30B-E2D1-40C2-B6DC-2DC672948D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd37dc91118899a7813ac8ba400ba5d822f8b775","datavalue":{"value":{"entity-type":"item","numeric-id":3084211,"id":"Q3084211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6a38f768415bae492ff978ac8d5962d293c7c71","datavalue":{"value":{"amount":"+0.8541172742843628","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":"Q1894266$56CEC29C-4550-49BC-9350-EF10FA2F2EE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09e26a82767acc3a2e9ecd93930a208e122470ea","datavalue":{"value":{"entity-type":"item","numeric-id":3360124,"id":"Q3360124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faf6f7a188c74ef7c0a9a5820f79c91253a07e22","datavalue":{"value":{"amount":"+0.8473989963531494","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":"Q1894266$CCAB4E22-A8DF-4CF1-9C2D-D2672CCB62A5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the construction of perfect deletion-correcting codes using design theory","badges":[]}}}}}