Computing Maximal Error-detecting Capabilities and Distances of Regular Languages

• Autorzy: Konstantinidis, S. , Silva, P.V.
• Języki publikacji: EN

Abstrakty

EN

A (combinatorial) channel consists of pairs of words representing all possible inputoutput channel situations. In a past paper, we formalized the intuitive concept of "largest amount of errors" detectable by a given language L, by defining the maximal error-detecting capabilities of L with respect to a given class of channels, and we showed how to compute all maximal error-detecting capabilities (channels) of a given regular language with respect to the class of rational channels and a class of channels involving only the substitution-error type. In this paper we resolve the problem for channels involving any combination of the basic error types: substitution, insertion, deletion. Moreover, we consider the problem of finding the inverses of these channels, in view of the fact that L is error-detecting for γif and only if it is error-detecting for the inverse of γ. We also discuss a natural method of reducing the problem of computing (inner) distances of a given regular language L to the problem of computing maximal error-detecting capabilities of L

Słowa kluczowe

EN

algorithm; automaton; combinatorial channel; edit string; error detection; maximal; regular language; string distance

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 101, nr 4
• Strony: 257-270
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Konstantinidis, S.

autor

Silva, P.V.

• Department of Mathematics and Computing Science, Saint Mary’s University, Halifax, Nova Scotia, B3H 3C3 Canada,

Bibliografia

• [1] Calude, C., Salomaa, K., Yu, S.: Additive distances and quasi-distances between words, Journal of Universal Computer Science 8, 2002, 141-152.
• [2] Choffrut, C., Pighizzini, G.: Distances between languages and reflexivity of relations, Theoretical Computer Science 286(1), 2002, 117-138.
• [3] Daka, A.: Maximal Error-detecting Capabilities of Regular Languages (tentative title). MSc APS thesis, Dept. Math. and Computing Sci., Saint Mary's University, Canada (in progress).
• [4] Duske, J., Jürgensen, H.: Codierungstheorie. BI Wissenschaftsverlag,Manheim, 1977.
• [5] Johnson, H: Rational equivalence relations, Theoretical Computer Science 47(1), 1986, 39-60.
• [6] Kari, L., Konstantinidis, S.: Descriptional complexity of error/edit systems, Journal of Automata, Languages and Combinatorics 9(2-3), 2004, 293-309.
• [7] Konstantinidis, S.: Transducers and the properties of error-detection, error-correction and finite-delay decodability, Journal of Universal Computer Science 8, 2002, 278-291.
• [8] Konstantinidis, S: Computing the edit distance of a regular language, Information and Computation 205, 2007, 1307-1316. A shorter version appears as "Computing the Levenshtein distance of a regular language," Proc. IEEE Information TheoryWorkshop on Coding and Complexity, Rotorua, New Zealand, Aug. 29 - Sep. 1, 2005, pp 113-116.
• [9] Konstantinidis, S., Silva, P.V:Maximal error-detecting capabilities of formal languages, Journal of Automata, Languages and Combinatorics 13, 2008, 55-71.
• [10] McAloney, C.L.: Error-correction and finite transductions. MSc thesis, Dept. Computing and Information Sci., Queen's University, Canada, 2003.
• [11] Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Dokl. 10, 1966, 707-710.
• [12] Peterson,W.W., Weldon, Jr., E.J.: Error-Correcting Codes. MIT Press, Cambridge, second ed., 1972.
• [13] Rozenberg, G., Salomaa, A. (eds): Handbook of Formal Languages, Vol. I. Springer-Verlag, Berlin, 1997.
• [14] Salomaa, K., Schofield, P: State complexity of additive weighted finite automata. International Journal of the Foundations of Computer Sci. 18, 2007, 1407-1416.
• [15] Sankoff, D., Kruskal, J.: TimeWarps, String Edits, andMacromolecules: The theory and practice of sequence comparison. CSLI Publications, 1999.
• [16] Yu, S.: Regular Languages. In [13], 41-110.