اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدWord problem languages for completely regular semigroups
105
0
0.0
(
0
)
تأليف
Tara Brough
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Motivated by the question of which completely regular semigroups have context-free word problem, we show that for certain classes of languages $mathfrak{C}$(including context-free), every completely regular semigroup that is a union of finitely many finitely generated groups with word problem in $mathfrak{C}$ also has word problem in $mathfrak{C}$. We give an example to show that not all completely regular semigroups with context-free word problem can be so constructed.
قيم البحث
اقرأ أيضاً
This paper studies the classes of semigoups and monoids with context-free and deterministic context-free word problem. First, some examples are exhibited to clarify the relationship between these classes and their connection with the notions of word-
hyperbolicity and automaticity. Second, a study is made of whether these classes are closed under applying certain semigroup constructions, including direct products and free products, or under regressing from the results of such constructions to the original semigroup(s) or monoid(s).
This paper considers the word problem for free inverse monoids of finite rank from a language theory perspective. It is shown that no free inverse monoid has context-free word problem; that the word problem of the free inverse monoid of rank $1$ is b
oth $2$-context-free (an intersection of two context-free languages) and ET0L; that the co-word problem of the free inverse monoid of rank $1$ is context-free; and that the word problem of a free inverse monoid of rank greater than $1$ is not poly-context-free.
This note proves a generalisation to inverse semigroups of Anisimovs theorem that a group has regular word problem if and only if it is finite, answering a question of Stuart Margolis. The notion of word problem used is the two-tape word problem -- t
he set of all pairs of words over a generating set for the semigroup which both represent the same element.
This paper is a contribution to the theory of finite semigroups and their classification in pseudovarieties, which is motivated by its connections with computer science. The question addressed is what role can play the consideration of an order compa
tible with the semigroup operation. In the case of unions of groups, so-called completely regular semigroups, the problem of which new pseudovarieties appear in the ordered context is solved. As applications, it is shown that the lattice of pseudovarieties of ordered completely regular semigroups is modular and that taking the intersection with the pseudovariety of bands defines a complete endomorphism of the lattice of all pseudovarieties of ordered semigroups.
This paper enriches the list of properties of the congruence sequences starting from the universal relation and successively performing the operations of lower $t$ and lower $k$. Three classes of completely regular semigroups, namely semigroups for w
hich $ker{sigma}$ is a cryptogroup, semigroups for which $ker{ u}$ is a cryptogroup and semigroups for which $kappa$ is over rectangular bands, are studied. $((omega_t)_k)_t$, $((mathcal{D}_t)_k)_t$ and $((omega_k)_t)_k$ are found to be the least congruences on $S$ such that the quotient semigroups are semigroups for which $ker{sigma}$ is a cryptogroup, $ker{ u}$ is a cryptogroup and $kappa$ is over rectangular bands, respectively. The results obtained present a response to three problems in Petrich and Reillys textbook textquotelefttextquoteleft Completely Regular Semigroupstextquoterighttextquoteright.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
