ترغب بنشر مسار تعليمي؟ اضغط هنا

Word Problem Languages for Free Inverse Monoids

104   0   0.0 ( 0 )
 نشر من قبل Tara Brough
 تاريخ النشر 2018
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English
 تأليف Tara Brough




اسأل ChatGPT حول البحث

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 both $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.



قيم البحث

اقرأ أيضاً

104 - Tara Brough 2020
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).
218 - Tara Brough 2013
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.
116 - Tara Brough 2011
We consider the class of groups whose word problem is poly-context-free; that is, an intersection of finitely many context-free languages. We show that any group which is virtually a finitely generated subgroup of a direct product of free groups has poly-context-free word problem, and conjecture that the converse also holds. We prove our conjecture for several classes of soluble groups, including metabelian groups and torsion-free soluble groups, and present progress towards resolving the conjecture for soluble groups in general. Some of the techniques introduced for proving languages not to be poly-context-free may be of independent interest.
199 - Karl Auinger , Yuzhu Chen , Xun Hu 2014
We prove a sufficient condition under which a semigroup admits no finite identity basis. As an application, it is shown that the identities of the Kauffman monoid $mathcal{K}_n$ are nonfinitely based for each $nge 3$. This result holds also for the c ase when $mathcal{K}_n$ is considered as an involution semigroup under either of its natural involutions.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا