اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRecognizing pro-R closures of regular languages
61
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given a regular language L, we effectively construct a unary semigroup that recognizes the topological closure of L in the free unary semigroup relative to the variety of unary semigroups generated by the pseudovariety R of all finite R-trivial semigroups. In particular, we obtain a new effective solution of the separation problem of regular languages by R-languages.
قيم البحث
اقرأ أيضاً
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 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.
In this article we undertake a study of extension complexity from the perspective of formal languages. We define a natural way to associate a family of polytopes with binary languages. This allows us to define the notion of extension complexity of fo
rmal languages. We prove several closure properties of languages admitting compact extended formulations. Furthermore, we give a sufficient machine characterization of compact languages. We demonstrate the utility of this machine characterization by obtaining upper bounds for polytopes for problems in nondeterministic logspace; lower bounds in streaming models; and upper bounds on extension complexities of several polytopes.
Let $m$ be a positive integer and let $Omega$ be a finite set. The $m$-closure of $Gle$Sym$(Omega)$ is the largest permutation group on $Omega$ having the same orbits as $G$ in its induced action on the Cartesian product $Omega^m$. The exact formula
for the $m$-closure of the wreath product in product action is given. As a corollary, a sufficient condition is obtained for this $m$-closure to be included in the wreath product of the $m$-closures of the factors.
Let $hat{F}$ be a free pro-$p$ non-abelian group, and let $Delta$ be a commutative Noetherian complete local ring with a maximal ideal $I$ such that $textrm{char}(Delta/I)=p>0$. In [Zu], Zubkov showed that when $p eq2$, the pro-$p$ congruence subgrou
p $$GL_{2}^{1}(Delta)=ker(GL_{2}(Delta)overset{DeltatoDelta/I}{longrightarrow}GL_{2}(Delta/I))$$ admits a pro-$p$ identity, i.e., there exists an element $1 eq winhat{F}$ that vanishes under any continuous homomorphism $hat{F}to GL_{2}^{1}(Delta)$. In this paper we investigate the case $p=2$. The main result is that when $textrm{char}(Delta)=2$, the pro-$2$ group $GL_{2}^{1}(Delta)$ admits a pro-$2$ identity. This result was obtained by the use of trace identities that originate in PI-theory.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
