{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:44:12Z","timestamp":1777596252350,"version":"3.51.4"},"reference-count":28,"publisher":"EDP Sciences","issue":"2-3-4","license":[{"start":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T00:00:00Z","timestamp":1548720000000},"content-version":"vor","delay-in-days":303,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2018,4]]},"abstract":"<jats:p>We introduce the concept of an -maximal error-detecting block code, for some parameter in (0,1), in order to formalize the situation where a block code is close to maximal with respect to being error-detecting. Our motivation for this is that it is computationally hard to decide whether an error-detecting block code is maximal. We present an output-polynomial time randomized algorithm that takes as input two positive integers <jats:italic>N<\/jats:italic>, <jats:italic>\u2113<\/jats:italic> and a specification of the errors permitted in some application, and generates an error-detecting, or error-correcting, block code of length <jats:italic>\u2113<\/jats:italic> that is 99%-maximal, or contains <jats:italic>N<\/jats:italic> words with a high likelihood. We model error specifications as (nondeterministic) transducers, which allow one to represent any rational combination of substitution and synchronization errors. We also present some elements of our implementation of various error-detecting properties and their associated methods. Then, we show several tests of the implemented randomized algorithm on various error specifications. A methodological contribution is the presentation of how various desirable error combinations can be expressed formally and processed algorithmically.<\/jats:p>","DOI":"10.1051\/ita\/2018015","type":"journal-article","created":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T09:02:17Z","timestamp":1548752537000},"page":"169-184","source":"Crossref","is-referenced-by-count":2,"title":["Randomized generation of error control codes with automata and transducers"],"prefix":"10.1051","volume":"52","author":[{"given":"Stavros","family":"Konstantinidis","sequence":"first","affiliation":[]},{"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[]},{"given":"Rog\u00e9rio","family":"Reis","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2019,1,29]]},"reference":[{"key":"R1","unstructured":"Almeida A., \nAlmeida M., \nAlves J., \nMoreira N. and \nReis R., \nFAdo and GUItar: Tools for automata manipulation and visualization. In Proc. of CIAA 2009, Sydney, Australia, edited by \nManeth. S. \nVol. 5642 of Lecture Notes in Computer Science. \nSpringer-Verlag \n(2009) 65\u201374"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Berstel J., \nTransductions and Context-Free Languages.\nB.G. Teubner, Stuttgart \n(1979)","DOI":"10.1007\/978-3-663-09367-1"},{"key":"R3","unstructured":"Chen E.Z., \nComputer construction of quasi-twisted two-weight codes. \nIn Sixth International Workshop on Optimal Codes and Related Topics \n(2009) 62\u201368"},{"key":"R4","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1142\/S0129054112400059","volume":"23","author":"Dudzinski","year":"2012","journal-title":"Int. J. Found. Comput. Sci"},{"key":"R5","unstructured":"FAdo , \nTools for formal languages manipulation. \nAccessed in January 2016. Available at: http:\/\/fado.dcc.fc.up.pt\/."},{"key":"R6","unstructured":"Jaffe D.B., \nOptimal binary linear codes of length \u2264 30. \nIn Proc. ofthe 1998 International Symposium on Information Theory \n(1998) 17"},{"key":"R7","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"Johnson","year":"1988","journal-title":"Inf. Process. Lett"},{"key":"R8","first-page":"563","volume":"26","author":"J\u00fcrgenesen","year":"1990","journal-title":"Elektron. Informationsverarbeit. Kybernetik"},{"key":"R9","doi-asserted-by":"crossref","first-page":"1916","DOI":"10.1137\/120862612","volume":"28","author":"Kant\u00e9","year":"2014","journal-title":"SIAM J. Discrete Math."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Konstantinidis S., \nMeijer C., \nMoreira N. and \nReis R., \nImplementation of code properties via transducers. In Proc. of CIAA 2016, edited by \nHan Y.-S. and \nSalomaa K.. \nVol. 9705 in Lecture Notes in Computer Science. \nSpringer-Verlag \n(2016) 189\u2013201","DOI":"10.1007\/978-3-319-40946-7_16"},{"key":"R11","first-page":"55","volume":"13","author":"Konstantinidis","year":"2008","journal-title":"J. Autom. Lang. Comb."},{"key":"R12","unstructured":"Lam C.W.H., \nFinding error-correcting codes using computers. \nIn Information Security, Coding Theory and Related Combinatorics \n(2011) 278\u2013284"},{"key":"R13","first-page":"707","volume":"10","author":"Levenshtein","year":"1966","journal-title":"Sov. Physi. Dokl"},{"key":"R14","first-page":"355","volume":"6","author":"Levenshtein","year":"1973","journal-title":"Probl. Inform. Trans"},{"key":"R15","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1002\/jcd.10071","volume":"12","author":"Levenshtein","year":"2004","journal-title":"J. Comb. Des."},{"key":"R16","unstructured":"Lewis H.and \nPapadimitriou C.H., \nElements of the Theory of Computation, 2nd ed. \nPrentice Hall \n(1998)"},{"key":"R17","unstructured":"Lin S. and \nCostello D.J. \nError control coding, 2nd ed. \nPearson \n(2005)"},{"key":"R18","unstructured":"Liu Z. and \nMitzenmacher M., \nCodes for deletion and insertion channels with segmented errors. \nIn Proc. of ISIT, Nice, France, 2007 \n(2007) 846\u2013849"},{"key":"R19","unstructured":"MacWilliams F.J. and \nSloane N.J.A., \nThe Theory of Error-Correcting Codes. \nAmsterdam \n(1977)"},{"key":"R20","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1109\/SURV.2010.020110.00079","volume":"12","author":"Mercier","year":"2010","journal-title":"IEEE Commun. Surv. Tutor"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and \nUpfal E., \nProbability and Computing. \nCambridge University Press \n(2005)","DOI":"10.1017\/CBO9780511813603"},{"key":"R22","doi-asserted-by":"crossref","first-page":"5935","DOI":"10.1109\/TIT.2013.2264825","volume":"59","author":"Paluncic","year":"2013","journal-title":"IEEE Trans. Inf. Theory"},{"key":"R23","unstructured":"Pless V.S. and \nHuffman W.C., editors. \nHandbook of Coding Theory. \nElsevier \n(1998)"},{"key":"R24","unstructured":"PyPy PyPy, \na fast, compliant alternative implementation of the Python language. \nAvailable at: \nhttp:\/\/pypy.org \n(2017)"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Rozenberg G. and \nSalomaa A., \nHandbook of Formal Languages, Vol. I. \nSpringer-Verlag, Berlin \n(1997)","DOI":"10.1007\/978-3-642-59126-6"},{"key":"R26","unstructured":"Shannon C.E. and \nWeaver W., \nThe Mathematical Theory of Communication. \nUniversity of Illinois Press, Urbana \n(1949)"},{"key":"R27","unstructured":"Shyr H.J., \nFree Monoids and Languages, 2nd ed. \nHon Min Book Company, Taichung \n(1991)"},{"key":"R28","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1109\/TIT.2002.806155","volume":"49","author":"Swart","year":"2003","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2018015\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T16:44:34Z","timestamp":1584636274000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2018015"}},"subtitle":[],"editor":[{"given":"Henning","family":"Bordihn","sequence":"first","affiliation":[]},{"given":"Benedek","family":"Nagy","sequence":"additional","affiliation":[]},{"given":"Gy\u00f6rgy","family":"Vaszil","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2018,4]]},"references-count":28,"journal-issue":{"issue":"2-3-4"},"alternative-id":["ita180060"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2018015","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4]]}}}