Email this article 
Hide
Show all
Open Access
Subscription Access
SET DECIPHERABLE LANGUAGES AND GENERATORS
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
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 : 43 views. PDF : 26 views.
Oktrik
Journal of Computer Science and Cybernetics ISSN: 1813-9663
Published by Vietnam Academy of Science and Technology