Open Access Open Access  Restricted Access Subscription Access

SET DECIPHERABLE LANGUAGES AND GENERATORS

Tran Vinh Duc

Abstract


We investigate the problem to characterize whether the infinite product of a given language $L$ is generated by an $\omega$-code. Up to now, this problem is open even if language $L$ is a finite language.

In this work, we consider a class of languages named $\omega$-set decipherable languages which are very close to the $\omega$-codes. We solve the problem in the restricted case where $L$ is $\omega$-set decipherable and $L^*$ is the greatest generator of $L^\omega$.


Keywords


Codes, \omega-codes; Dominoes, Formal languages; Generators; Infinite words

Full Text:

PDF

References


P. C. Bell, D. Reidenbach, and J. O. Shallit, ``Unique decipherability in formal languages,'' emph{Theoretical Computer Science}, vol. 804, pp. 149 -- 160, 2020.

J. Berstel, D. Perrin, and C. Reutenauer, emph{{Codes and Automata}}, ser. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009, vol. 129.

T. Dang Quyet, H. Nguyen Dinh, and H. Phan Trung, ``Algorithms based on finite automata for testing of $omega$-codes,'' in emph{Future Information Technology, Application, and Service}. Springer Netherlands, 2012, pp. 271--279.

J. Devolder, ``Generators with bounded deciphering delay for rational $omega$-languages,'' Journal of Automata, Languages and Combinatorics, vol. 4, no. 3, pp. 183--204, 1999.

J. Devolder, M. Latteux, I. Litovsky, and L. Staiger, ``Codes and infinite words,'' emph{Acta Cybernetica}, vol. 11, no. 4, pp. 241--256, 1994.

F. Guzm'an, ``Decidability of codes,'' emph{Journal of Pure and Applied Algebra}, pp. 13--35, 1999.

T. Head and A. Weber, ``Deciding multiset decipherability,'' emph{{IEEE} Trans. Inf. Theory}, vol. 41, no. 1, pp. 291--297, 1995.

S. Julia, ``On $omega$-generators and codes,'' in emph{$23^d$ ICALP, Lecture Notes in Computer Sciences, vol. 1099. Berlin: Springer, 1996, pp. 393--402.

S. Julia, I. Litovsky, and B. Patrou, ``On codes, $omega$-codes and $omega$-generators,'' emph{Information Processing Letters}, vol. 60, no. 1, pp. 1--5, oct 1996.

I. Litovsky, ``G{'e}n{'e}rateurs des langages rationnels de mots infinis,'' Ph.D. dissertation, Universit{'e} de Lille, 1988.

I. Litovsky, ``Prefix-free languages as $omega$-generators,'' emph{Information Processing Letters}, vol. 37, pp. 61--65, 1991.

I. Litovsky and E. Timmerman, ``On generators of rational $omega$-power languages,'' emph{Theoretical Computer Science}, vol. 53, pp. 187--200, 1987.

M. Lothaire, emph{Algebraic combinatorics on words}, ser. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002, vol. 90.

D. Perrin and J. E. Pin, emph{Infinite Words}. Academic Press, 2002.

A. Saarela, ``Independent systems of word equations: From Ehrenfeucht to eighteen,'' in emph{Combinatorics on Words}, R. Merca{c{s}} and

D.~Reidenbach, Eds. Springer International Publishing, 2019, pp. 60--67.

A. Saarela,``Word equations with kth powers of variables,'' emph{Journal of Combinatorial Theory, Series A}, vol. 165, pp. 15 -- 31, 2019.

L. Staiger, ``On infinitary finite length codes,'' emph{Theoretical Informatics and Applications}, vol. 20, no. 4, pp. 483--494, 1986.

V. D. Tran and I. Litovsky, ``One-relation languages and $omega$-code generators,'' in emph{Proc. of the $13^{th}$ Mons Theoretical Computer Science Days}, 2010.




DOI: https://doi.org/10.15625/1813-9663/36/4/15317 Display counter: Abstract : 90 views. PDF : 32 views.

Oktrik

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology