Applications of Transducers in Independent Languages, Word Distances, Codes

Abstract : A (nondeterministic) transducer t is an operator mapping an input word to a set of possible output words. A few types of transducers are important in this work: input-altering, input-preserving, and input-decreasing. Two words are t-dependent, if one is the output of t when the other one is used as input. A t-independent language is one containing no two t-dependent words. Examples of independent languages are found in noiseless coding theory, noisy coding theory and DNA computing. We discuss how the above transducer types can provide elegant solutions to some cases of the following broad problems: (i) computing two minimum distance witness words of a given regular language; (ii) computing witness words for the non-satisfaction, or non-maximality, of a given regular language with respect to the independence specified by a given transducer t; (iii) computing, for any given t and language L, a maximal t-independent language containing L; (iv) computing, for any given positive integer n and transducer t, a t-independent language of n words. The descriptional complexity cost of converting between transducer types is discussed, when this conversion is possible. We also explore methods of defining more independences in a way that some of the above problems can still be computed.
Type de document :
Communication dans un congrès
Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.45-62, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_4〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01657012
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:44:29
Dernière modification le : mercredi 6 décembre 2017 - 13:46:17

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Stavros Konstantinidis. Applications of Transducers in Independent Languages, Word Distances, Codes. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.45-62, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_4〉. 〈hal-01657012〉

Partager

Métriques

Consultations de la notice

18