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)



Congruences associated with DOL-schemes

Authors: Mario Petrich and Gabriel Thierrin
Journal: Proc. Amer. Math. Soc. 102 (1988), 787-793
MSC: Primary 68Q45; Secondary 20M05, 20M35
MathSciNet review: 934843
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For a DOL-scheme $ (X,\varphi )$, where $ X$ is a finite alphabet and $ \varphi $ is an endomorphism of $ {X^*}$, we study the properties of the congruence $ \bar \varphi $ induced by $ \varphi $ in terms of the properties of $ {X^*}\varphi $. We prove that every submonoid of $ {X^*}$ has a disjunctive subset (for any $ X$) and deduce that $ \bar \varphi $ is a syntactic congruence. As special cases, we consider the conditions on $ \varphi $ which are equivalent to $ \bar \varphi $ being perfect or uniquely perfect or linear. The latter is introduced in the paper together with a ramification.

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

  • [1] M. Harrison, Introduction to formal language theory, Addison-Wesley, Reading, Mass., 1978. MR 526397 (80h:68060)
  • [2] G. T. Herman and G. Rozenberg, Developmental systems and languages, North-Holland, Amsterdam, 1975. MR 0495247 (58:13968)
  • [3] M. Petrich and C. Reis, Perfect congruences on a free monoid, Proc. Amer. Math. Soc. 99 (1987), 205-212. MR 870772 (87m:20167)

Similar Articles

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

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

Additional Information

Keywords: Free monoid, endomorphism, DOL-scheme, syntactic congruence, perfect congruence, linear congruence, code, hypercode
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society