Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Hypercodes, right convex languages and their syntactic monoids


Author: G. Thierrin
Journal: Proc. Amer. Math. Soc. 83 (1981), 255-258
MSC: Primary 20M35; Secondary 68F05
DOI: https://doi.org/10.1090/S0002-9939-1981-0624909-7
MathSciNet review: 624909
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: If $ {X^ * }$ is the free monoid generated by the alphabet $ X$, then any subset $ L$ of $ {X^ * }$ is called a language over $ X$. If $ {P_L}$ is the principal congruence determined by $ L$, then the quotient monoid $ {\text{syn}}(L) = {X^ * }/{P_L}$ is called the syntactic monoid of $ L$. A hypercode over $ X$ is any set of nonemtpy words that are noncomparable with respect to the embedding order of $ {X^ * }$. If $ H$ is a hypercode, then the language $ \tilde H = \{ x\vert x \in {X^ * }$ and $ a \leqslant x$ for some $ a \in H\} $ is a right convex ideal of $ {X^ * }$. The syntactic monoid $ {\text{syn}}(\tilde H)$ can be characterized as a monoid with a disjunctive $ \mu $-zero. The two particular interesting cases when $ {\text{syn}}(\tilde H)$ is a nil monoid and when $ {\text{syn}}(\tilde H)$ is a semillatice are also characterized.


References [Enhancements On Off] (What's this?)

  • [1] L. H. Haines, On free monoids partially ordered by embedding, J. Combin. Theory 6 (1969), 94-98. MR 0240016 (39:1370)
  • [2] G. Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. 2 (1952), 225-336. MR 0049867 (14:238e)
  • [3] M. P. Jullien, Sur un théorème d'extension dans la théorie des mots, C. R. Acad. Sci. Paris Sér. A 266 (1968), 651-654.
  • [4] H. Jürgensen, Inf-halbverbände als syntaktische Halbgruppen, Acta Math. Acad. Sci. Hungar. 31 (1978), 37-41. MR 0489043 (58:8525)
  • [5] G. Lallement, Semigroups and combinatorial applications, Wiley, New York, 1978. MR 530552 (81j:20082)
  • [6] B. M. Schein, Homomorphisms and subdirect decompositions of semigroups, Pacific J. Math. 17 (1966), 529-547. MR 0197603 (33:5768)
  • [7] H. J. Shyr and G. Thierrin, Hypercodes, Inform. and Control 24 (1974), 45-54. MR 0345712 (49:10443)
  • [8] G. Thierrin, Convex languages, Proc. IRIA Sympos. Automata, Languages and Programming (Paris, 1972), North-Holland, Amsterdam, 1972, pp. 481-492. MR 0375851 (51:12041)
  • [9] -, The syntactic monoid of a hypercode, Semigroup Forum 6 (1973), 227-231. MR 0376935 (51:13110)
  • [10] -, Decomposition of some classes of subsets in a semigroup, Proc. Conf. Semigroups and Applications (Oberwolfach, 1978), Springer-Verlag, Berlin and New York, 1981. MR 618855 (82g:20093)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 20M35, 68F05

Retrieve articles in all journals with MSC: 20M35, 68F05


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1981-0624909-7
Keywords: Monoid, language, syntactic monoid, embedding order, hypercode, convex, nil monoid, semilattice
Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society