Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRecognizing pro-R closures of regular languages
61
0
0.0
(
0
)
Added by
Jorge Almeida
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 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.
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 formal 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 subgroup $$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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
