One-Relation Languages and Code Generators
RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 2

We investigate the open problem to characterize whether the infinite power of a given language is generated by an ω-code. In case the given language is a code (i.e. zero-relation language), the problem was solved. In this work, we solve the problem for the class of one-relation languages.

DOI : 10.1051/ita/2021002
Classification : 68Q45, 68R15
Keywords: Formal languages, infinite words, $$-generators, code, $$-code 
@article{ITA_2021__55_1_A4_0,
     author = {Tran, Vinh Duc and Litovsky, Igor},
     title = {One-Relation {Languages} and {Code} {Generators}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ita/2021002},
     mrnumber = {4245319},
     zbl = {1508.68205},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2021002/}
}
TY  - JOUR
AU  - Tran, Vinh Duc
AU  - Litovsky, Igor
TI  - One-Relation Languages and Code Generators
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2021
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2021002/
DO  - 10.1051/ita/2021002
LA  - en
ID  - ITA_2021__55_1_A4_0
ER  - 
%0 Journal Article
%A Tran, Vinh Duc
%A Litovsky, Igor
%T One-Relation Languages and Code Generators
%J RAIRO. Theoretical Informatics and Applications
%D 2021
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2021002/
%R 10.1051/ita/2021002
%G en
%F ITA_2021__55_1_A4_0
Tran, Vinh Duc; Litovsky, Igor. One-Relation Languages and Code Generators. RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 2. doi: 10.1051/ita/2021002

[1] E. Czeizler and J. Karhumäki, On non-periodic solutions of independent systems of word equations over three unknowns. Int. J. Found. Computer Sci. 18 (2007) 873–897. | MR | Zbl | DOI

[2] J. Devolder, M. Latteux, I. Litovsky and L. Staiger, Codes and infinite words. Acta Cybern. 11 (1994) 241–256. | MR | Zbl

[3] F. Guzmán, Decipherability of codes. J. Pure Appl. Algebra 141 (1999) 13–35. | MR | Zbl | DOI

[4] S. Julia, On ω-generators and codes. In 23d ICALP (Int. Coll. on Automata, Languages and Programming). Vol. 1099 of Lecture Notes in Computer Sciences. Springer, Berlin (1996) 393–402. | MR | Zbl

[5] S. Julia, I. Litovsky and B. Patrou, On codes, ω-codes and ω-generators. Inf. Process. Lett. 60 (1996) 1–5. | MR | Zbl | DOI

[6] S. Julia and T. V. Duc, Families and ω -ambiguity removal. 𝐼𝑛 𝑃𝑟𝑜𝑐 . 7 𝑡ℎ 𝐼𝑛𝑡 . 𝐶𝑜𝑛𝑓 . 𝑜𝑛 𝑊𝑜𝑟𝑑𝑠 ( 𝑊𝑂𝑅𝐷𝑆 ) , Salerno (2009).

[7] I. Litovsky, Générateurs des langages rationnels de mots infinis. Ph.D. thesis, Université de Lille (1988).

[8] I. Litovsky, Prefix-free languages as ω-generators. Inf. Process. Lett. 37 (1991) 61–65. | MR | Zbl | DOI

[9] I. Litovsky and E. Timmerman, On generators of rational ω-power languages. Theor. Comput. Sci. 53 (1987) 187–200. | MR | Zbl | DOI

[10] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002). | Zbl | MR | DOI

[11] M. Nivat, Infinitary Relations. In CAAP ’81: Proceedings of the 6th Colloquium on Trees in Algebra and Programming. Springer (1981) 46–75. | Zbl | DOI

[12] L. Staiger, On infinitary finite length codes. Theor. Inf. Appl. 20 (1986) 483–494. | MR | Zbl | Numdam | DOI

[13] C. Wrathall, Confluence of One-Rule Thue Systems. Word Equations and Related Topics. Vol. 572 of Lecture Notes in Computer Sciences. Springer (1992) 237–246. | MR | Zbl | DOI

Cité par Sources :