Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the insertion of n-powers
294
0
0.0
(
0
)
Added by
Jorge Almeida
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In algebraic terms, the insertion of $n$-powers in words may be modelled at the language level by considering the pseudovariety of ordered monoids defined by the inequality $1le x^n$. We compare this pseudovariety with several other natural pseudovarieties of ordered monoids and of monoids associated with the Burnside pseudovariety of groups defined by the identity $x^n=1$. In particular, we are interested in determining the pseudovariety of monoids that it generates, which can be viewed as the problem of determining the Boolean closure of the class of regular languages closed under $n$-power insertions. We exhibit a simple upper bound and show that it satisfies all pseudoidentities which are provable from $1le x^n$ in which both sides are regular elements with respect to the upper bound.
rate research
Read More
We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: their Cayley graphs are geodetic and side-lengths of non-degenerate triangles are uniformly bounded. This leads to a new algebraic result: the group is plain (isomorphic to the free product of finitely many finite groups and copies of $mathbb Z$) if and only if a certain relation on the set of non-trivial finite-order elements of the group is transitive on a bounded set. We use this to prove that deciding if a group presented by an inverse-closed finite convergent length-reducing rewriting system is not plain is in $mathsf{NP}$. A yes answer would disprove a longstanding conjecture of Madlener and Otto from 1987. We also prove that the isomorphism problem for plain groups presented by inverse-closed finite convergent length-reducing rewriting systems is in $mathsf{PSPACE}$.
We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, as shortlex geodesic words (or any regular set of quasigeodesic normal forms), is an EDT0L language whose specification can be computed in NSPACE$(n^2log n)$ for the torsion-free case and NSPACE$(n^4log n)$ in the torsion case. Furthermore, in the presence of quasi-isometrically embeddable rational constraints, we show that the full set of solutions to systems of equations in a hyperbolic group remains EDT0L. Our work combines the geometric results of Rips, Sela, Dahmani and Guirardel on the decidability of the existential theory of hyperbolic groups with the work of computer scientists including Plandowski, Je.z, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis.
We identify the representations $mathbb{K}[X^k, X^{k-1}Y, dots, Y^k]$ among abstract $mathbb{Z}[mathrm{SL}_2(mathbb{K})]$-modules. One result is on $mathbb{Q}[mathrm{SL}_2(mathbb{Z})]$-modules of short nilpotence length and generalises a classical quadratic theorem by Smith and Timmesfeld. Another one is on extending the linear structure on the module from the prime field to $mathbb{K}$. All proofs are by computation in the group ring using the Steinberg relations.
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.
We prove that, for any natural number n $ge$ 1, we can find a finite alphabet $Sigma$ and a finitary language L over $Sigma$ accepted by a one-counter automaton, such that the $omega$-power L $infty$ := {w 0 w 1. .. $in$ $Sigma$ $omega$ | $forall$i $in$ $omega$ w i $in$ L} is $Pi$ 0 n-complete. We prove a similar result for the class $Sigma$ 0 n .
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
