Informace o publikaci

On the insertion of n-powers

Autoři

MENESES GUIMARÄES DE ALMEIDA Jorge Manuel KLÍMA Ondřej

Rok publikování 2019
Druh Článek v odborném periodiku
Časopis / Zdroj DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www https://dmtcs.episciences.org/5155
Klíčová slova Regular language; polynomial closure; pseudovariety; finite ordered monoid; pseudoidentity; Burnside pseudovariety
Popis 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 <= 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 <= x(n) in which both sides are regular elements with respect to the upper bound.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info