Characterizations of linear congruences on a free monoid
Alessandra Cherubini and Mario Petrich
Proc. Amer. Math. Soc. 119 (1993), 719-726
Full-text PDF Free Access
Similar Articles |
Abstract: Linear congruences on a free monoid coincide with the congruences on induced by nontrivial homomorphisms into the additive group of integers. For a finite , we characterize abstractly several classes of linear congruences on , in particular, -linear congruences, called -linear and determined by Reis, -linear congruences, introduced by Petrich and Thierrin, and general linear congruences, introduced by the authors. These characterizations include descriptions involving maximality as prefix congruences.
Petrich and Gabriel
Thierrin, Congruences associated with
DOL-schemes, Proc. Amer. Math. Soc.
102 (1988), no. 4,
934843 (89d:68047), http://dx.doi.org/10.1090/S0002-9939-1988-0934843-7
M. Reis, Infix congruences on a free
monoid, Trans. Amer. Math. Soc.
311 (1989), no. 2,
978373 (90a:20119), http://dx.doi.org/10.1090/S0002-9947-1989-0978373-0
Salomaa, Formal languages, Academic Press [Harcourt Brace
Jovanovich, Publishers], New York-London, 1973. ACM Monograph Series. MR 0438755
Sasaki and Takayuki
Tamura, Positive rational semigroups and commutative power joined
cancellative semigroups without idempotent, Czechoslovak Math. J.
21(96) (1971), 567–576. MR 0292981
- M. Petrich and G. Thierrin, Congruences associated with -schemes, Proc. Amer. Math. Soc. 102 (1988), 787-793. MR 934843 (89d:68047)
- C. M. Reis, Prefix congruences on a free monoid, Trans. Amer. Math. Soc. 311 (1989), 727-737. MR 978373 (90a:20119)
- A. Salomaa, Formal languages, Academic Press, New York, San Francisco, and London, 1973. MR 0438755 (55:11661)
- M. Sasaki and T. Tamura, Positive rational semigroups and power joined cancellative semi-groups without idempotent, Czechoslovak Math. J. 21 (1971), 567-576. MR 0292981 (45:2062)
Retrieve articles in Proceedings of the American Mathematical Society
Retrieve articles in all journals
© Copyright 1993
American Mathematical Society