Sub-classes of the monoid of left cancellative languages

Abstract

A language A is left cancellative if from AB=AC, it follows that B=C, for any two languages B and C. Semi-singular and inf-singular languages are two disjoint sub-sets of left cancellative languages and are introduced by Hsieh and Shyr [Left cancellative elements in the monoid of languages, Soochow J. Math. 4 (1978), pp. 7–15]. In this paper, we further study them. It is shown that all non-dense and all maximal left cancellative languages are semi-singular while all right dense left cancellative languages are inf-singular. Finally, a theorem shows that there is a left cancellative language which is neither semi-singular nor inf-singular.

Keywords:

• left cancellative language
• semi-singular language
• inf-singular language
• dense language
• maximal left cancellative language

2000 AMS Subject Classifications :

• 68Q70
• 68Q45
• 94A45

Acknowledgements

The authors would like to thank the referees for their careful reading of the manuscript and useful suggestions. The research is supported by Natural Science Foundation of Yunnan Province of China #2010CD21.