×

Relatively regular languages and thin codes. (English) Zbl 1131.68054

Summary: A language is called a relatively regular language if its syntactic monoid has finite ideals. In this paper, we show that there are close relationships between the relatively regular languages and some other classes of languages such as (generalized) disjunctive languages, \(fd\)-domains and 2-codes. In particular, we prove that every relatively regular 2-code is thin. Thus, the well-known result of Bestel and Perrin in 1985 becomes an easy corollary of our result.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bestel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press Orlando
[2] Day, P. H.; Shyr, H. J., Languages defined by some partial orders, Soochow Journal of Mathematics, 9, 53-62 (1983) · Zbl 0537.68078
[3] Y.Q. Guo, H.J. Shyr, G. Thierrin, Qf-Disjunctive languages, Papers on Automata and Languages, VII, K. Marx. Univ. Economics, Budapest, 1985, pp. 1-28; Y.Q. Guo, H.J. Shyr, G. Thierrin, Qf-Disjunctive languages, Papers on Automata and Languages, VII, K. Marx. Univ. Economics, Budapest, 1985, pp. 1-28 · Zbl 0605.68067
[4] Guo, Y. Q.; Shyr, H. J.; Thierrin, G., F-disjunctive languages, International Journal of Computer Mathematics, 18, 219-237 (1986) · Zbl 0655.68100
[5] Guo, Y. Q.; Reis, C. M.; Thierrin, G., Relatively \(f\)-disjunctive languages, Semigroup Forum, 37, 289-299 (1988) · Zbl 0648.20064
[6] Howie, J. M., An Introduction to Semigroup Theory (1976), Academic Press: Academic Press London · Zbl 0355.20056
[7] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley Interscience: Wiley Interscience New York · Zbl 0421.20025
[8] Y.J. Liu, Semigroup method in combinatorics on words, Ph.D. Thesis, Zhongshan University, Guangzhou, 2001; Y.J. Liu, Semigroup method in combinatorics on words, Ph.D. Thesis, Zhongshan University, Guangzhou, 2001
[9] Paradis, A. D.; Shyr, H. J.; Thierrin, G., Quasi-disjunctive languages, Soochow Journal of Mathematics, 3, 151-161 (1982) · Zbl 0541.68047
[10] Reis, C. M.; Shyr, H. J., Some properties of disjunctive languages on a free monoid, Information and Control, 37, 3, 334-344 (1978) · Zbl 0376.68044
[11] Shyr, H. J.; Thierrin, G., Disjunctive languages and codes, Fundamentals of computation theory, (Proceedings of the 1977 Inter. FCT-Conference. Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland. Proceedings of the 1977 Inter. FCT-Conference. Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland, Lecture Notes in Computer Science, vol. 56 (1977), Springer-Verlag), 171-176 · Zbl 0366.68049
[12] Shyr, H. J., Disjunctive languages on a free monoid, Information and Control, 34, 123-129 (1977) · Zbl 0354.68108
[13] Shyr, H. J.; Yu, S. S., Midst-languages, Soochow Journal of Mathematics, 24, 2, 113-130 (1998) · Zbl 0903.68116
[14] Shyr, H. J., Free Monoids and Languages (2001), Hon Min Book Company: Hon Min Book Company Taichung, Taiwan · Zbl 0746.20050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.