# SET DECIPHERABLE LANGUAGES AND GENERATORS

## Authors

• Tran Vinh Duc Hanoi University of Science and Technology

## Keywords:

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

## 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$.

## 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.

2020-12-14

## How to Cite


T. V. Duc, “SET DECIPHERABLE LANGUAGES AND GENERATORS”, JCC, vol. 36, no. 4, p. 381–392, Dec. 2020.

## Section

Articles
{"ft_lang_label":"__label__en","ft_lang_prob":0.7660773,"math_prob":0.7220217,"size":4626,"snap":"2022-27-2022-33","text_gpt3_token_len":1280,"char_repetition_ratio":0.12029424,"word_repetition_ratio":0.047256097,"special_character_ratio":0.28426287,"punctuation_ratio":0.24260958,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9779749,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-08-11T08:14:05Z\",\"WARC-Record-ID\":\"<urn:uuid:4ebd6471-c8f4-4b22-b2b3-9aeafe4b7a3c>\",\"Content-Length\":\"43791\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4aa93e8c-abf8-428f-ba67-34d206ba5346>\",\"WARC-Concurrent-To\":\"<urn:uuid:19a42918-0777-4bba-a88e-dfb14a32dc93>\",\"WARC-IP-Address\":\"210.86.231.145\",\"WARC-Target-URI\":\"https://vjs.ac.vn/index.php/jcc/article/view/15317\",\"WARC-Payload-Digest\":\"sha1:4YCKJTDSES5GSYCDMYBW4X55QSJOVNTE\",\"WARC-Block-Digest\":\"sha1:J7VCORT26HWB5NJ7Q3UNYVA7E5PZAKQD\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-33/CC-MAIN-2022-33_segments_1659882571246.56_warc_CC-MAIN-20220811073058-20220811103058-00358.warc.gz\"}"}