Reducibility of pointlike problems

被引:0
|
作者
J. Almeida
J. C. Costa
M. Zeitoun
机构
[1] Universidade do Porto,Centro de Matemática e Departamento de Matemática, Faculdade de Ciências
[2] Universidade do Minho,Centro de Matemática e Departamento de Matemática e Aplicações
[3] Univ. Bordeaux,undefined
[4] LaBRI,undefined
[5] UMR 5800,undefined
来源
Semigroup Forum | 2017年 / 94卷
关键词
Pseudovariety; Profinite semigroup; Pointlike set ; Regular language; Aperiodic semigroup;
D O I
暂无
中图分类号
学科分类号
摘要
We show that the pointlike and the idempotent pointlike problems are reducible with respect to natural signatures in the following cases: the pseudovariety of all finite semigroups in which the order of every subgroup is a product of elements of a fixed set π\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi $$\end{document} of primes; the pseudovariety of all finite semigroups in which every regular J\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal J$$\end{document}-class is the product of a rectangular band by a group from a fixed pseudovariety of groups that is reducible for the pointlike problem, respectively graph reducible. Allowing only trivial groups, we obtain ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega $$\end{document}-reducibility of the pointlike and idempotent pointlike problems, respectively for the pseudovarieties of all finite aperiodic semigroups (A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf{A}$$\end{document}) and of all finite semigroups in which all regular elements are idempotents (DA\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf{DA}$$\end{document}).
引用
收藏
页码:325 / 335
页数:10
相关论文
共 20 条
  • [1] Reducibility of pointlike problems
    Almeida, J.
    Costa, J. C.
    Zeitoun, M.
    SEMIGROUP FORUM, 2017, 94 (02) : 325 - 335
  • [2] Pointlike reducibility of pseudovarieties of the form V * D
    Costa, Jose Carlos
    Nogueira, Conceicao
    Teixeira, Maria Lurdes
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2016, 26 (02) : 203 - 216
  • [3] On κ-reducibility of pseudovarieties of the form V * D
    Costa, J. C.
    Teixeira, M. L.
    Nogueira, C.
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2017, 27 (01) : 23 - 40
  • [4] Complete κ-reducibility of pseudovarieties of the form DRH
    Almeida, Jorge
    Borlido, Celia
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2017, 27 (02) : 189 - 235
  • [5] The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
    Volarikova, Jana
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2024, 34 (01) : 87 - 135
  • [6] COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1
    Costa, Jose Carlos
    Nogueira, Conceicao
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2009, 19 (02) : 247 - 282
  • [7] Reducibility vs. definability for pseudovarieties of semigroups
    Almeida, J.
    Klima, O.
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2016, 26 (07) : 1483 - 1495
  • [8] Some reducibility properties for pseudovarieties of the form DRH
    Borlido, Celia
    COMMUNICATIONS IN ALGEBRA, 2018, 46 (04) : 1813 - 1830
  • [9] Reducibility of joins involving some locally trivial pseudovarieties
    Costa, JC
    COMMUNICATIONS IN ALGEBRA, 2004, 32 (09) : 3517 - 3535
  • [10] On regular realizability problems
    M. N. Vyalyi
    Problems of Information Transmission, 2011, 47 : 342 - 352