Project/scholarship details
- Project/scholarship ID
65481
- Reference
PTDC/MAT/65481/2006
- FundRef URI
- Funder
FCT - Fundação para a Ciência e a Tecnologia, I.P.
- Funder's country
Portugal
- Funding program
5876-PPCDTI
- Funding amount
52,000.00 €
- Start date
2007-05-01
- End date
2010-08-31
Documents
ω-terms over finite aperiodic semigroups
Almeida, Jorge; Costa, José Carlos; Zeitoun, MarcThis paper provides a characterization of pseudowords over the pseudovariety of all finite aperiodic semigroups that are given by w-terms, that is that can be obtained from the free generators using only multiplication and the w-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 a...
Some structural properties of the free profinite aperiodic semigroup
Almeida, Jorge; Costa, José Carlos; Zeitoun, MarcProfinite semigroups provide powerful tools to understand properties of classes of regular languages. Until very recently however, little was known on the structure of "large" relatively free profinite semi- groups. In this paper, we present new results obtained for the class of all finite aperiodic (that is, group-free) semigroups. Given a finite alphabet X, we focus on the following problems: (1) the word pro...
Complete reducibility of the pseudovariety LSl
Costa, José Carlos; Nogueira, ConceiçãoIn this paper we prove that the pseudovariety LSl of local semilattices is completely κ-reducible, where κ is the implicit signature consisting of the multiplication and the ω-power. Informally speaking, given a finite equation system with rational constraints, the existence of a solution by pseudowords of the system over LSl implies the existence of a solution by κ-words of the system over LSl satisfying the s...
Semidirect product with an order-computable pseudovariety and tameness
Almeida, Jorge; Costa, José Carlos; 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 prope...
Tameness of joins involving the pseudovariety of local semilattices
Costa, José Carlos; 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 LSl...
Closures of regular languages for profinite topologies
Almeida, Jorge; Costa, José Carlos; 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 pseudovarie...
Iterated periodicity over finite aperiodic semigroups
Almeida, Jorge; Costa, José Carlos; 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...
McCammond's normal forms for free aperiodic semigroups revisited
Almeida, Jorge; Costa, José Carlos; Zeitoun, MarcThis paper revisits the solution of the word problem for omega-terms interpreted over finite aperiodic semigroups, obtained by J. McCammond. The original proof of correctness of McCammond's algorithm, based on normal forms for such terms, uses McCammond's solution of the word problem for certain Burnside semigroups. In this paper, we establish a new, simpler, correctness proof of McCammond's algorithm, based on...
Report
Embed
<script type="text/javascript">
<!--
document.write('<div id="rcaap-widget"></div>');
document.write('<script type="text/javascript" src="https://www.rcaap.pt/snippet?resource=documents&project=FCT%2F5876-PPCDTI%2F65481&fields=id,titles,creators,issueDate,link,descriptions"></script>');
-->
</script>