Source author record

João Araújo

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.GR math.CO Logic in Computer Science math.LO math.RA Symbolic Computation

Catalog footprint

Research overview

18works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Boosting Isomorphic Model Filtering with Invariants

The enumeration of finite models is very important to the working discrete mathematician (algebra, graph theory, etc) and hence the search for effective methods to do this task is a critical goal in discrete computational mathematics. However, it is hindered by the possible existence of many isomorphic models, which usually only add noise. Typically, they are filtered out {\em a posteriori}, a step that might take a long time just to discard redundant models. This paper proposes a novel approach to split the generated models into mutually non-isomorphic blocks. To do that we use well-designed hand-crafted invariants as well as randomly generated invariants. The blocks are then tackled separately and possibly in parallel. This approach is integrated into Mace4 (the most popular tool among mathematicians) where it shows tremendous speed-ups for a large variety of algebraic structures.

preprint2022arXiv

CREAM: a Package to Compute [Auto, Endo, Iso, Mono, Epi]-morphisms, Congruences, Divisors and More for Algebras of Type $(2^n,1^n)$

The CREAM GAP package computes automorphisms, congruences, endomorphisms and subalgebras of algebras with an arbitrary number of binary and unary operations; it also decides if between two such algebras there exists a monomorphism, an epimorphism, an isomorphism or if one is a divisor of the other. Thus it finds those objects for almost all algebras used in practice (groups, quasigroups in their various signatures, semigroups possibly with many unary operations, fields, semi-rings, quandles, logic algebras, etc). As a one-size-fits-all package, it only relies on universal algebra theorems, without taking advantage of specific theorems about, eg, groups or semigroups to reduce the search space. Canon and Holt produced very fast code to compute automorphisms of groups that outperform CREAM on orders larger than 128. Similarly, Mitchell et al. take advantage of deep theorems to compute automorphisms and congruences of completely 0-simple semigroups in a very efficient manner. However these domains (groups of order above 128 and completely 0-simple semigroups) are among the very few examples of GAP code faster than our general purpose package CREAM. For the overwhelming majority of other classes of algebras, either ours is the first code computing the above mentioned objects, or the existing algorithms are outperformed by CREAM, in some cases by several orders of magnitude. To get this performance, CREAM uses a mixture of universal algebra algorithms together with GAP coupled with artificial intelligence theorem proving tools (AITP) and very delicate C implementations. As an example of the latter, we re-implement Freese's very clever algorithm for computing congruences in universal algebras, in a way that outperforms all other known implementations.

preprint2022arXiv

Varieties of Lazy Magmas Characterized by Forbidden Substructure Theorems

A magma (or groupoid) is a set with a binary operation $(A,f)$ . Roughly speaking, a magma is said to be lazy if compositions such as $f(x,f(f(y,z),u))$ depend on at most two variables. Recently, Kaprinai, Machida and Waldhauser described the lattice of all the varieties of lazy groupoids. A forbidden structure theorem is one that charcaterizes a smaller class $A$ inside a larger class $B$ as all the elements in $B$ that avoid some substructures. For example, a lattice is distributive (smaller class $A$ ) if and only if it is a lattice (larger class $B$ ) and avoids the pentagon and the diamond. In this paper we provide a characterization of all pairs of lazy groupoid varieties $A\le B$ by forbidden substructure theorems. Some of the results are straightforward, but some other are very involved. All of these results and proofs were found using a computational tool that proves theorems of this type (for many different classes of relational algebras) and that we make available to every mathematician.

preprint2017arXiv

Decidability and Independence of Conjugacy Problems in Finitely Presented Monoids

There have been several attempts to extend the notion of conjugacy from groups to monoids. The aim of this paper is study the decidability and independence of conjugacy problems for three of these notions (which we will denote by $\sim_p$ , $\sim_o$ , and $\sim_c$ ) in certain classes of finitely presented monoids. We will show that in the class of polycyclic monoids, $p$ -conjugacy is "almost" transitive, $\sim_c$ is strictly included in $\sim_p$ , and the $p$ - and $c$ -conjugacy problems are decidable with linear compexity. For other classes of monoids, the situation is more complicated. We show that there exists a monoid $M$ defined by a finite complete presentation such that the $c$ -conjugacy problem for $M$ is undecidable, and that for finitely presented monoids, the $c$ -conjugacy problem and the word problem are independent, as are the $c$ -conjugacy and $p$ -conjugacy problems.

preprint2016arXiv

Congruences on Direct Products of Transformation and Matrix Monoids

Malcev described the congruences of the monoid $T_n$ of all full transformations on a finite set $X_n=\{1, \dots,n\}$ . Since then, congruences have been characterized in various other monoids of (partial) transformations on $X_n$ , such as the symmetric inverse monoid $In_n$ of all injective partial transformations, or the monoid $PT_n$ of all partial transformations. The first aim of this paper is to describe the congruences of the direct products $Q_m\times P_n$ , where $Q$ and $P$ belong to $\{T, PT,In\}$ . Malcev also provided a similar description of the congruences on the multiplicative monoid $F_n$ of all $n\times n$ matrices with entries in a field $F$ , our second aim is provide a description of the principal congruences of $F_m \times F_n$ . The paper finishes with some comments on the congruences of products of more than two transformation semigroups, and a fairly large number of open problems.

preprint2016arXiv

Primitive groups, road closures, and idempotent generation

We are interested in semigroups of the form $\langle G,a\rangle\setminus G$ , where $G$ is a permutation group of degree $n$ and $a$ a non-permutation on the domain of $G$ . A theorem of the first author, Mitchell and Schneider shows that, if this semigroup is idempotent-generated for all possible choices of $a$ , then $G$ is the symmetric or alternating group of degree $n$ , with three exceptions (having $n=5$ or $n=6$ ). Our purpose here is to prove stronger results where we assume that $\langle G,a\rangle\setminus G$ is idempotent-generated for all maps of fixed rank $k$ . For $k\ge6$ and $n\ge2k+1$ , we reach the same conclusion, that $G$ is symmetric or alternating. These results are proved using a stronger version of the \emph{ $k$ -universal transversal property} previously considered by the authors. In the case $k=2$ , we show that idempotent generation of the semigroup for all choices of $a$ is equivalent to a condition on the permutation group $G$ , stronger than primitivity, which we call the \emph{road closure condition}. We cannot determine all the primitive groups with this property, but we give a conjecture about their classification, and a body of evidence (both theoretical and computational) in support of the conjecture. The paper ends with some problems.

preprint2015arXiv

Orbits of Primitive $k$ -Homogenous Groups on $(n-k)$ -Partitions with Applications to Semigroups

Let $X$ be a finite set such that $|X|=n$ , and let $k< n/2$ . A group is $k$ -homogeneous if it has only one orbit on the sets of size $k$ . The aim of this paper is to prove some general results on permutation groups and then apply them to transformation semigroups. On groups we find the minimum number of permutations needed to generate $k$ -homogeneous groups (for $k\ge 1$ ); in particular we show that $2$ -homogeneous groups are $2$ -generated. We also describe the orbits of $k$ -homogenous groups on partitions with $n-k$ parts, classify the $3$ -homogeneous groups $G$ whose orbits on $(n-3)$ -partitions are invariant under the normalizer of $G$ in $S_n$ , and describe the normalizers of $2$ -homogeneous groups in the symmetric group. Then these results are applied to extract information about transformation semigroups with given group of units, namely to prove results on their automorphisms and on the minimum number of generators. The paper finishes with some problems on permutation groups, transformation semigroups and computational algebra.

preprint2014arXiv

Primitive Groups Synchronize Non-uniform Maps of Extreme Ranks

Let $Ω$ be a set of cardinality $n$ , $G$ a permutation group on $Ω$ , and $f:Ω\toΩ$ a map which is not a permutation. We say that $G$ synchronizes $f$ if the semigroup $\langle G,f\rangle$ contains a constant map. The first author has conjectured that a primitive group synchronizes any map whose kernel is non-uniform. Rystsov proved one instance of this conjecture, namely, degree $n$ primitive groups synchronize maps of rank $n-1$ (thus, maps with kernel type $(2,1,\ldots,1)$ ). We prove some extensions of Rystsov's result, including this: a primitive group synchronizes every map whose kernel type is $(k,1,\ldots,1)$ . Incidentally this result provides a new characterization of imprimitive groups. We also prove that the conjecture above holds for maps of extreme ranks, that is, ranks 3, 4 and $n-2$ . These proofs use a graph-theoretic technique due to the second author: a transformation semigroup fails to contain a constant map if and only if it is contained in the endomorphism semigroup of a non-null (simple undircted) graph. The paper finishes with a number of open problems, whose solutions will certainly require very delicate graph theoretical considerations.

preprint2014arXiv

The Largest Subsemilattices of the Endomorphism Monoid of an Independence Algebra

An algebra $\A$ is said to be an independence algebra if it is a matroid algebra and every map $\al:X\to A$, defined on a basis $X$ of $\A$, can be extended to an endomorphism of $\A$. These algebras are particularly well behaved generalizations of vector spaces, and hence they naturally appear in several branches of mathematics such as model theory, group theory, and semigroup theory. It is well known that matroid algebras have a well defined notion of dimension. Let $\A$ be any independence algebra of finite dimension $n$ , with at least two elements. Denote by $\End(\A)$ the monoid of endomorphisms of $\A$. We prove that a largest subsemilattice of $\End(\A)$ has either $2^{n-1}$ elements (if the clone of $\A$ does not contain any constant operations) or $2^n$ elements (if the clone of $\A$ contains constant operations). As corollaries, we obtain formulas for the size of the largest subsemilattices of: some variants of the monoid of linear operators of a finite-dimensional vector space, the monoid of full transformations on a finite set $X$ , the monoid of partial transformations on $X$ , the monoid of endomorphisms of a free $G$ -set with a finite set of free generators, among others. The paper ends with a relatively large number of problems that might attract attention of experts in linear algebra, ring theory, extremal combinatorics, group theory, semigroup theory, universal algebraic geometry, and universal algebra.

preprint2014arXiv

Two Generalizations of Homogeneity in Groups with Applications to Regular Semigroups

Let $X$ be a finite set such that $|X|=n$ and let $i\leq j \leq n$ . A group $G\leq \sym$ is said to be $(i,j)$ -homogeneous if for every $I,J\subseteq X$ , such that $|I|=i$ and $|J|=j$ , there exists $g\in G$ such that $Ig\subseteq J$ . (Clearly $(i,i)$ -homogeneity is $i$ -homogeneity in the usual sense.) A group $G\leq \sym$ is said to have the $k$ -universal transversal property if given any set $I\subseteq X$ (with $|I|=k$ ) and any partition $P$ of $X$ into $k$ blocks, there exists $g\in G$ such that $Ig$ is a section for $P$ . (That is, the orbit of each $k$ -subset of $X$ contains a section for each $k$ -partition of $X$ .) In this paper we classify the groups with the $k$ -universal transversal property (with the exception of two classes of 2-homogeneous groups) and the $(k-1,k)$ -homogeneous groups (for $2<k\leq \lfloor \frac{n+1}{2}\rfloor$ ). As a corollary of the classification we prove that a $(k-1,k)$ -homogeneous group is also $(k-2,k-1)$ -homogeneous, with two exceptions; and similarly, but with no exceptions, groups having the $k$ -universal transversal property have the $(k-1)$ -universal transversal property. A corollary of all the previous results is a classification of the groups that together with any rank $k$ transformation on $X$ generate a regular semigroup (for $1\leq k\leq \lfloor \frac{n+1}{2}\rfloor$ ). The paper ends with a number of challenges for experts in number theory, group and/or semigroup theory, linear algebra and matrix theory.

preprint2013arXiv

Permutation groups and transformation semigroups: results and problems

J.M. Howie, the influential St Andrews semigroupist, claimed that we value an area of pure mathematics to the extent that (a) it gives rise to arguments that are deep and elegant, and (b) it has interesting interconnections with other parts of pure mathematics. This paper surveys some recent results on the transformation semigroup generated by a permutation group $G$ and a single non-permutation $a$ . Our particular concern is the influence that properties of $G$ (related to homogeneity, transitivity and primitivity) have on the structure of the semigroup. In the first part of the paper, we consider properties of $S=<G,a>$ such as regularity and idempotent generation. The second is a brief report on the synchronization project, which aims to decide in what circumstances $S$ contains an element of rank 1. The paper closes with a list of open problems on permutation groups and linear groups, and some comments about the impact on semigroups are provided. These two research directions outlined above lead to very interesting and challenging problems on primitive permutation groups whose solutions require combining results from several different areas of mathematics, certainly fulfilling both of Howie's elegance and value tests in a new and fascinating way.

preprint2013arXiv

The Classification of Partition Homogeneous Groups with Applications to Semigroup Theory

Let $λ=(λ_1,λ_2,...)$ be a \emph{partition} of $n$ , a sequence of positive integers in non-increasing order with sum $n$ . Let $Ω:=\{1,...,n\}$ . An ordered partition $P=(A_1,A_2,...)$ of $Ω$ has \emph{type} $λ$ if $|A_i|=λ_i$ . Following Martin and Sagan, we say that $G$ is \emph{ $λ$ -transitive} if, for any two ordered partitions $P=(A_1,A_2,...)$ and $Q=(B_1,B_2,...)$ of $Ω$ of type $λ$ , there exists $g\in G$ with $A_ig=B_i$ for all $i$ . A group $G$ is said to be \emph{ $λ$ -homogeneous} if, given two ordered partitions $P$ and $Q$ as above, inducing the sets $P'=\{A_1,A_2,...\}$ and $Q'=\{B_1,B_2,...\}$ , there exists $g\in G$ such that $P'g=Q'$ . Clearly a $λ$ -transitive group is $λ$ -homogeneous. The first goal of this paper is to classify the $λ$ -homogeneous groups. The second goal is to apply this classification to a problem in semigroup theory. Let $\trans$ and $\sym$ denote the transformation monoid and the symmetric group on $Ω$ , respectively. Fix a group $H\leq \sym$. Given a non-invertible transformation $a\in \trans\setminus \sym$ and a group $G\leq \sym$, we say that $(a,G)$ is an \emph{ $H$ -pair} if the semigroups generated by $\{a\}\cup H$ and $\{a\}\cup G$ contain the same non-units, that is, $< a,G>\setminus G=< a,H>\setminus H$ . Using the classification of the $λ$ -homogeneous groups we classify all the $\sym$-pairs. This topic involves both group theory and semigroup theory; we have attempted to include enough exposition to make the paper self-contained for researchers in both areas. The paper finishes with a number of open problems on permutation and linear groups.

preprint2012arXiv

Groups Synchronizing a Transformation of Non-Uniform Kernel

This paper concerns the general problem of classifying the finite deterministic automata that admit a synchronizing (or reset) word. (For our purposes it is irrelevant if the automata has initial or final states.) Our departure point is the study of the transition semigroup associated to the automaton, taking advantage of the enormous and very deep progresses made during the last decades on the theory of permutation groups, their geometry and their combinatorial structure. Let $X$ be a finite set. We say that a primitive group $G$ on $X$ is {\em synchronizing} if $G$ together with any non-invertible map on $X$ generates a constant map. It is known (by some recent results proved by P. M. Neumann) that for some primitive groups $G$ and for some singular transformations $t$ of uniform kernel (that is, all blocks have the same number of elements), the semigroup $< G,t>$ does not generate a constant map. Therefore the following concept is very natural: a primitive group $G$ on $X$ is said to be {\em almost synchronizing} if $G$ together with any map of non-uniform kernel generates a constant map. In this paper we use two different methods to provide several infinite families of groups that are not synchronizing, but are almost synchronizing. The paper ends with a number of problems on synchronization likely to attract the attention of experts in computer science, combinatorics and geometry, groups and semigroups, linear algebra and matrix theory.

preprint2012arXiv

The classification of normalizing groups

Let $X$ be a finite set such that $|X|=n$ . Let $\trans$ and $\sym$ denote respectively the transformation monoid and the symmetric group on $n$ points. Given $a\in \trans\setminus \sym$, we say that a group $G\leq \sym$ is $a$ -normalizing if $<a,G> \setminus G=<g^{-1}ag\mid g\in G>.$ If $G$ is $a$ -normalizing for all $a\in \trans\setminus \sym$, then we say that $G$ is normalizing. The goal of this paper is to classify normalizing groups and hence answer a question posed elsewhere. The paper ends with a number of problems for experts in groups, semigroups and matrix theory.

preprint2012arXiv

The Commuting Graph of the Symmetric Inverse Semigroup

The commuting graph of a finite non-commutative semigroup $S$ , denoted $\cg(S)$, is a simple graph whose vertices are the non-central elements of $S$ and two distinct vertices $x,y$ are adjacent if $xy=yx$ . Let $\mi(X)$ be the symmetric inverse semigroup of partial injective transformations on a finite set $X$ . The semigroup $\mi(X)$ has the symmetric group $\sym(X)$ of permutations on $X$ as its group of units. In 1989, Burns and Goldsmith determined the clique number of the commuting graph of $\sym(X)$. In 2008, Iranmanesh and Jafarzadeh found an upper bound of the diameter of $\cg(\sym(X))$, and in 2011, Doluzan and Oblak claimed (but their proof has a GAP) that this upper bound is in fact the exact value. The goal of this paper is to begin the study of the commuting graph of the symmetric inverse semigroup $\mi(X)$. We calculate the clique number of $\cg(\mi(X))$, the diameters of the commuting graphs of the proper ideals of $\mi(X)$, and the diameter of $\cg(\mi(X))$ when $|X|$ is even or a power of an odd prime. We show that when $|X|$ is odd and divisible by at least two primes, then the diameter of $\cg(\mi(X))$ is either 4 or 5. In the process, we obtain several results about semigroups, such as a description of all commutative subsemigroups of $\mi(X)$ of maximum order, and analogous results for commutative inverse and commutative nilpotent subsemigroups of $\mi(X)$. The paper closes with a number of problems for experts in combinatorics and in group or semigroup theory.

preprint2011arXiv

Idempotent Generated Endomorphisms of an Independence Algebra

The aim of this note is to give a direct proof for the following result proved by Fountain and Lewin: {\em Let $\alg$ be an independence algebra of finite rank and let $a$ be a singular endomorphism of $\alg $. Then $a=e_1... e_n$ where $e^2_i=e_i$ and $rank(a)=rank(e_i)$ .}

preprint2011arXiv

On idempotent generated semigroups

We provide short and direct proofs for some classical theorems proved by Howie, Levi and McFadden concerning idempotent generated semigroups of transformations on a finite set.

preprint2010arXiv

The Largest Subsemilattices of the Semigroup of Transformations on a Finite Set

Let T(X) be the semigroup of full transformations on a finite set X with n elements. We prove that every subsemilattice of T(X) has at most 2^{n-1} elements and that there are precisely n subsemilattices of size exactly 2^{n-1}, each isomorphic to the semilattice of idempotents of the symmetric inverse semigroup on a set with n-1 elements.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

João Araújo

Research overview

Is this your work?

18 publications

Boosting Isomorphic Model Filtering with Invariants

CREAM: a Package to Compute [Auto, Endo, Iso, Mono, Epi]-morphisms, Congruences, Divisors and More for Algebras of Type $(2^n,1^n)$

Varieties of Lazy Magmas Characterized by Forbidden Substructure Theorems

Decidability and Independence of Conjugacy Problems in Finitely Presented Monoids

Congruences on Direct Products of Transformation and Matrix Monoids

Primitive groups, road closures, and idempotent generation

Orbits of Primitive $k$ -Homogenous Groups on $(n-k)$ -Partitions with Applications to Semigroups

Primitive Groups Synchronize Non-uniform Maps of Extreme Ranks

The Largest Subsemilattices of the Endomorphism Monoid of an Independence Algebra

Two Generalizations of Homogeneity in Groups with Applications to Regular Semigroups

Permutation groups and transformation semigroups: results and problems

The Classification of Partition Homogeneous Groups with Applications to Semigroup Theory

Groups Synchronizing a Transformation of Non-Uniform Kernel

The classification of normalizing groups

The Commuting Graph of the Symmetric Inverse Semigroup

Idempotent Generated Endomorphisms of an Independence Algebra

On idempotent generated semigroups

The Largest Subsemilattices of the Semigroup of Transformations on a Finite Set

See the researcher in context

Building this map preview

João Araújo

Research overview

Is this your work?

18 publications

Boosting Isomorphic Model Filtering with Invariants

CREAM: a Package to Compute [Auto, Endo, Iso, Mono, Epi]-morphisms, Congruences, Divisors and More for Algebras of Type (2n,1n)(2^n,1^n)(2n,1n)

Varieties of Lazy Magmas Characterized by Forbidden Substructure Theorems

Decidability and Independence of Conjugacy Problems in Finitely Presented Monoids

Congruences on Direct Products of Transformation and Matrix Monoids

Primitive groups, road closures, and idempotent generation

Orbits of Primitive kkk-Homogenous Groups on (n−k)(n-k)(n−k)-Partitions with Applications to Semigroups

Primitive Groups Synchronize Non-uniform Maps of Extreme Ranks

The Largest Subsemilattices of the Endomorphism Monoid of an Independence Algebra

Two Generalizations of Homogeneity in Groups with Applications to Regular Semigroups

Permutation groups and transformation semigroups: results and problems

The Classification of Partition Homogeneous Groups with Applications to Semigroup Theory

Groups Synchronizing a Transformation of Non-Uniform Kernel

The classification of normalizing groups

The Commuting Graph of the Symmetric Inverse Semigroup

Idempotent Generated Endomorphisms of an Independence Algebra

On idempotent generated semigroups

The Largest Subsemilattices of the Semigroup of Transformations on a Finite Set

See the researcher in context

Building this map preview

CREAM: a Package to Compute [Auto, Endo, Iso, Mono, Epi]-morphisms, Congruences, Divisors and More for Algebras of Type $(2^n,1^n)$

Orbits of Primitive $k$ -Homogenous Groups on $(n-k)$ -Partitions with Applications to Semigroups