Encontrados 7 documentos, a visualizar página 1 de 1
Closures of regular languages for profinite topologies
Almeida, Jorge; Costa, José Carlos Cruz da; Zeitoun, MarcThe Pin-Reutenauer algorithm gives a method, that can be viewed as a descriptive procedure, to compute the closure in the free group of a regular language with respect to the Hall topology. A similar descriptive procedure is shown to hold for the pseudovariety A of aperiodic semigroups, where the closure is taken in the free aperiodic omega-semigroup. It is inherited by a subpseudovariety of a given pseudov...
Iterated periodicity over finite aperiodic semigroups
Almeida, Jorge; Costa, José Carlos Cruz da; Zeitoun, MarcThis paper provides a characterization of pseudowords over the pseudovariety of all finite aperiodic semigroups that can be described from the free generators using only the operations of multiplication and omega-power. A necessary and sufficient condition for this property to hold turns out to be given by the conjunction of two rather simple finiteness conditions: the nonexistence of infinite anti-chains of fa...
Pointlike sets with respect to R and J
Almeida, Jorge; Costa, José Carlos Cruz da; Zeitoun, MarcWe present an algorithm to compute the pointlike subsets of a finite semigroup with respect to the pseudovariety R of all finite R-trivial semigroups. The algorithm is inspired by Henckell’s algorithm for computing the pointlike subsets with respect to the pseudovariety of all finite aperiodic semigroups. We also give an algorithm to compute J-pointlike sets, where J denotes the pseudovariety of all finite J-tr...
Complete reducibility of systems of equations with respect to R
Almeida, Jorge; Costa, José Carlos Cruz da; Zeitoun, MarcIt is shown that the pseudovariety R of all finite R-trivial semigroups is completely reducible with respect to the canonical signature. Informally, if the variables in a finite system of equations with rational constraints may be evaluated by pseudowords so that each value belongs to the closure of the corresponding rational constraint and the system is verified in R, then there is some such evaluation which i...
Tameness of pseudovariety joins involving R
Almeida, Jorge; Costa, José Carlos Cruz da; Zeitoun, Marc2000 Mathematics Subject Classification: 20M07 (primary); 20M05, 20M35, 68Q70 (secondary). ; In this paper, we establish several decidability results for pseudovariety joins of the form VvW, where V is a subpseudovariety of J or the pseudovariety R. Here, J (resp. R) denotes the pseudovariety of all J-trivial (resp. R-trivial) semigroups. In particular, we show that the pseudovariety VvW is (completely) ka...
Pseudovariety joins involving J-trivial semigroups
Almeida, Jorge; Azevedo, Assis; Zeitoun, MarcJ. Rhodes asked during the Chico conference in 1986 for the calculation of joins of semigroup pseudovarieties. This paper proves that the join J v H of the pseudovariety J of J-trivial semigroups and of any 2-strongly decidable pseudovariety V of completely regular semigroups is decidable. This problem was proposed by the first author for V=G, the pseudovariety of finite groups.
Three examples of join computations
Azevedo, Assis; Zeitoun, MarcThis article answers three questions of J. Almeida. Using combinatorial, algebraic and topological methods, we compute joins involving the pseudovariety of finite groups, the pseudovariety of semigroups in which each idempotent is a right zero and the pseudovariety generated by monoids M such that each idempotent of M\{1} is a left zero.
| Financiadores do RCAAP | |||||||
|
|
|
|
|
|
||