J. Almeida ; O. Klíma - On the insertion of n-powers

dmtcs:4072 - Discrete Mathematics & Theoretical Computer Science, February 5, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-5
On the insertion of n-powersArticle

Authors: J. Almeida ; O. Klíma

    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 $1\le 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 $1\le x^n$ in which both sides are regular elements with respect to the upper bound.


    Volume: Vol. 21 no. 3
    Section: Automata, Logic and Semantics
    Published on: February 5, 2019
    Accepted on: January 16, 2019
    Submitted on: November 16, 2017
    Keywords: Mathematics - Group Theory,Computer Science - Formal Languages and Automata Theory,20M07, 68Q70, 20M3

    Consultation statistics

    This page has been seen 774 times.
    This article's PDF has been downloaded 429 times.