On the insertion of n-powers

J 2019

On the insertion of n-powers

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

Základní údaje

Originální název

On the insertion of n-powers

Autoři

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

Vydání

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, NANCY, DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE, 2019, 1462-7264

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Francie

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.442

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14310/19:00108233

Organizační jednotka

Přírodovědecká fakulta

Klíčová slova anglicky

Regular language; polynomial closure; pseudovariety; finite ordered monoid; pseudoidentity; Burnside pseudovariety

Štítky

rivok

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 19. 8. 2025 10:00, Mgr. Marie Novosadová Šípková, DiS.

Anotace

V originále

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.

Návaznosti

GA15-02862S, projekt VaV

Název: Aplikace algebry a kombinatoriky v teorii formálních jazyků

Investor: Grantová agentura ČR, Aplikace algebry a kombinatoriky v teorii formálních jazyků

Citovat

MENESES GUIMARÄES DE ALMEIDA, Jorge Manuel a Ondřej KLÍMA. On the insertion of n-powers. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE. NANCY: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE, 2019, roč. 21, č. 3, s. 1-18. ISSN 1462-7264. Dostupné z: https://doi.org/10.23638/DMTCS-21-3-5.

@article{1642039,
   author = {Meneses Guimaräes de Almeida, Jorge Manuel and Klíma, Ondřej},
   article_location = {NANCY},
   article_number = {3},
   doi = {https://doi.org/10.23638/DMTCS-21-3-5},
   keywords = {Regular language; polynomial closure; pseudovariety; finite ordered monoid; pseudoidentity; Burnside pseudovariety},
   language = {eng},
   issn = {1462-7264},
   journal = {DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE},
   title = {On the insertion of n-powers},
   url = {https://dmtcs.episciences.org/5155},
   volume = {21},
   year = {2019}
}

TY  - JOUR
ID  - 1642039
AU  - Meneses Guimaräes de Almeida, Jorge Manuel - Klíma, Ondřej
PY  - 2019
TI  - On the insertion of n-powers
JF  - DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
VL  - 21
IS  - 3
SP  - 1-18
EP  - 1-18
PB  - DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE
SN  - 14627264
KW  - Regular language
KW  - polynomial closure
KW  - pseudovariety
KW  - finite ordered monoid
KW  - pseudoidentity
KW  - Burnside pseudovariety
UR  - https://dmtcs.episciences.org/5155
L2  - https://dmtcs.episciences.org/5155
N2  - 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.
ER  -

MENESES GUIMARÄES DE ALMEIDA, Jorge Manuel a Ondřej KLÍMA. On the insertion of n-powers. \textit{DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE}. NANCY: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE, 2019, roč.~21, č.~3, s.~1-18. ISSN~1462-7264. Dostupné z: https://doi.org/10.23638/DMTCS-21-3-5.

Přehled o publikaci