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

Groups with poly-context-free word problem

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




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

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.



قيم البحث

اقرأ أيضاً

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).
103 - Tara Brough 2018
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.
223 - 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.
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.
225 - Derek Holt , Sarah Rees 2020
We prove that the compressed word problem in a group that is hyperbolic relative to a collection of free abelian subgroups is solvable in polynomial time.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

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