Encontrados 10 documentos, a visualizar página 1 de 1
Canonical forms for free k-semigroups
Costa, José Carlos Cruz daThe implicit signature kappa consists of the multiplication and the (omega-1)-power. We describe a procedure to transform each kappa-term over a finite alphabet A into a certain canonical form and show that different canonical forms have different interpretations over some finite semigroup. The procedure of construction of the canonical forms, which is inspired in McCammond's normal form algorithm for omega-te...
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...
Tameness of joins involving the pseudovariety of local semilattices
Costa, José Carlos Cruz da; Nogueira, ConceiçãoIn this paper we prove that, if V is a kappa-tame pseudovariety which satisfies the pseudoidentity xy^{\omega+1}z=xyz, then the pseudovariety join LSl v V is also kappa-tame. Here, LSl denotes the pseudovariety of local semilattices and kappa denotes the implicit signature consisting of the multiplication and the (omega-1)-power. As a consequence, we deduce that LSl v V is decidable. In particular the joins LS...
Semidirect product with an order-computable pseudovariety and tameness
Almeida, Jorge; Costa, José Carlos Cruz da; Teixeira, M. LurdesDedicated to the memory of Walter Douglas Munn. ; The semidirect product of pseudovarieties of semigroups with an ordercomputable pseudovariety is investigated. The essential tool is the natural representation of the corresponding relatively free profinite semigroups and how it transforms implicit signatures. Several results concerning the behavior of the operation with respect to various kinds of tameness pro...
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...
Biinfinite words with maximal recurrent unbordered factors
Costa, José Carlos Cruz daA finite non-empty word z is said to be a border of a finite non-empty word w if w=uz=zv for some non-empty words u and v. A finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. In this paper, we give two characterizations of the biinfinite words of the form ...uuuvuuu..., where u and v are finite words, in terms of its unbordered factors. The main res...
Free profinite locally idempotent and locally commutative semigroups
Costa, José Carlos Cruz daThis paper is concerned with the structure of semigroups of implicit operations on the pseudovariety LSl of finite locally idempotent and locally commutative semigroups. We depart from a general result of Almeida and Weil to give two descriptions of these semigroups: the first in terms of infinite words, and the second in terms of infinite and bi-infinite words. We then derive some applications.
| Financiadores do RCAAP | |||||||
|
|
|
|
|
|
||