Reducibility of pointlike problems

被引:5
作者
Almeida, J. [1 ,2 ]
Costa, J. C. [3 ,4 ]
Zeitoun, M. [5 ]
机构
[1] Univ Porto, Ctr Matemat, Rua Campo Alegre 687, P-4169007 Oporto, Portugal
[2] Univ Porto, Fac Ciencias, Dept Matemat, Rua Campo Alegre 687, P-4169007 Oporto, Portugal
[3] Univ Minho, Ctr Matemat, Campus Gualtar, P-4700320 Braga, Portugal
[4] Univ Minho, Dept Matemat & Aplicacoes, Campus Gualtar, P-4700320 Braga, Portugal
[5] Univ Bordeaux, LaBRI, UMR 5800, F-33400 Talence, France
关键词
Pseudovariety; Profinite semigroup; Pointlike set; Regular language; Aperiodic semigroup; TAMENESS;
D O I
10.1007/s00233-015-9769-2
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 pi of primes; the pseudovariety of all finite semigroups in which every regular J-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 omega-reducibility of the pointlike and idempotent pointlike problems, respectively for the pseudovarieties of all finite aperiodic semigroups (A) and of all finite semigroups in which all regular elements are idempotents (DA).
引用
收藏
页码:325 / 335
页数:11
相关论文
共 22 条
  • [1] Reducibility of pointlike problems
    J. Almeida
    J. C. Costa
    M. Zeitoun
    Semigroup Forum, 2017, 94 : 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 THE PSEUDOVARIETY LS1
    Costa, Jose Carlos
    Nogueira, Conceicao
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2009, 19 (02) : 247 - 282
  • [5] Some reducibility properties for pseudovarieties of the form DRH
    Borlido, Celia
    COMMUNICATIONS IN ALGEBRA, 2018, 46 (04) : 1813 - 1830
  • [6] Complete κ-reducibility of pseudovarieties of the form DRH
    Almeida, Jorge
    Borlido, Celia
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2017, 27 (02) : 189 - 235
  • [7] 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
  • [8] Reducibility vs. definability for pseudovarieties of semigroups
    Almeida, J.
    Klima, O.
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2016, 26 (07) : 1483 - 1495
  • [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