M, ρ, and M/ρ Monoidleri için Sonlu Tam Yeniden Yazma Sistemleri

Year 2023, , 720 - 725, 10.03.2023

Aykut Emniyet , Basri Çalışkan

https://doi.org/10.47495/okufbed.1093331

Abstract

𝑀 bir monoid ve 𝜌, 𝑀 üzerinde kongrüans olacak biçimde bir denklik bağıntısı olsun. Böylece, 𝜌, 𝑀×𝑀 monoidlerinin direkt çarpımının bir alt monoidi ve 𝑀/𝜌={𝑥𝜌:𝑥∈𝑀} kümesi (𝑥𝜌)(𝑦𝜌)=(𝑥𝑦)𝜌 işlemi ile bir monoid olur. Öncelikle, bir giriş lemması ifade ve ispat edilerek konu ile ilgili bir örnek verilmektedir. Daha sonra, eğer 𝜌 bir sonlu tam yeniden yazma sistemi ile takdim edilebilir ise, 𝑀’nin de bir sonlu tam yeniden yazma sistemi ile takdim edilebilir olduğu gösterilmektedir. Ana sonucun son kısmında, eğer 𝜌 bir sonlu tam yeniden yazma sistemi ile takdim edilebilir ise, 𝑀/𝜌 monoidinin de bir sonlu tam yeniden yazma sistemi ile takdim edilebilir olduğu gösterilmektedir.

Keywords

Yarıgruplar, Monoidler, Takdimler, Kongruanslar, Yeniden Yazma Sistemleri

Finite Complete Rewriting Systems for the Monoids M, ρ, and M/ρ

Abstract

Let 𝑀 be a monoid and 𝜌 be an equivalence relation on 𝑀 such that 𝜌 is a congruence. So, 𝜌 is a submonoid of the direct product of monoids 𝑀×𝑀, and 𝑀/𝜌={𝑥𝜌:𝑥∈𝑀} is a monoid with the operation (𝑥𝜌)(𝑦𝜌)=(𝑥𝑦)𝜌. First, an introductory lemma is proposed, proved and a relevant example is given. Then, it is shown that if 𝜌 can be presented by a finite complete rewriting system, then so can 𝑀. As the final part of the main result, it is proved that if 𝜌 can be presented by a finite complete rewriting system, then so can 𝑀/𝜌.

Keywords

semigroups, monoids, presentations, congruences, rewriting systems

References

• Ayık G., Ayık H., Ünlü Y. Presentations for S and S/ρ from a given presentation ρ, Semigroup Forum, 2005; 70: 146-149.
• Book R.V., Otto F. String-Rewriting Systems, Springer-Verlag, New York, 1993.
• Cetinalp, E. K., Karpuz, E. G. Crossed product of infinite groups and complete rewriting systems, Turkish Journal of Mathematics, 2021; 45(1): 410-422.
• Dehn M. Tiber unendliche diskontinuierliche Gruppen, Mathematische Annalen, 1911; 71: 116-144.
• Gray R., Malheiro A., Finite complete rewriting systems for regular semigroups, Theoretical Computer Science, 2011; 412: 654-661.
• Howie J. M. Fundamentals of Semigroup Theory, Clarendon Press, Oxford, 1995.
• Kuyucu F. Relations between Ranks of Certain Semigroups, Selçuk J. Appl. Math., 2011; 12(1): 123-126.
• Özer, B., Yüksek, A. Finite Complete Rewriting Systems For Matrix Semigroup Presentations, International Journal of Algebra, 2016; 10: 497-511.
• Pride S. J. Subgroups of Finite Index in Groups with Finite Complete Rewriting Systems, Proceedings of the Edinburgh Mathematical Society, 2000; 43(1): 177-183.
• Sims C.C. Computation with Finitely Presentations Groups, Cambridge University Press, Cambridge, 1994.
• Squier C., Otto F., Kobayashi Y. A finiteness condition for rewriting systems, Theoretical Computer Science, 1994; 131: 271-294.
• Wang J. Finite Derivation Type for Semigroups and Congruences, Semigroup Forum, 2007; 75: 388-392.
• Wang J. Finite complete rewriting systems and finite derivation type for small extensions of monoids, Journal of Algebra, 1998; 204: 493-503.
• Wong K.B., Wong P.C. On finite complete rewriting systems and large subsemigroups, Journal of Algebra, 2010; 345: 242-256.