SET DECIPHERABLE LANGUAGES AND GENERATORS
Author affiliations
DOI:
https://doi.org/10.15625/1813-9663/36/4/15317Keywords:
Codes, \omega-codes, Dominoes, Formal languages, Generators, Infinite wordsAbstract
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$.
Metrics
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.
Downloads
Published
How to Cite
Issue
Section
License
1. We hereby assign copyright of our article (the Work) in all forms of media, whether now known or hereafter developed, to the Journal of Computer Science and Cybernetics. We understand that the Journal of Computer Science and Cybernetics will act on my/our behalf to publish, reproduce, distribute and transmit the Work.2. This assignment of copyright to the Journal of Computer Science and Cybernetics is done so on the understanding that permission from the Journal of Computer Science and Cybernetics is not required for me/us to reproduce, republish or distribute copies of the Work in whole or in part. We will ensure that all such copies carry a notice of copyright ownership and reference to the original journal publication.
3. We warrant that the Work is our results and has not been published before in its current or a substantially similar form and is not under consideration for another publication, does not contain any unlawful statements and does not infringe any existing copyright.
4. We also warrant that We have obtained the necessary permission from the copyright holder/s to reproduce in the article any materials including tables, diagrams or photographs not owned by me/us.
