BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Pierre Gillibert

Pierre Gillibert appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.LOmath.RAmath.CTmath.GMDiscrete MathematicsLogic in Computer Sciencemath.COComputational ComplexityFormal Languages and Automata TheoryMachine Learning

Catalog footprint

What is connected

13works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

13 published item(s)

preprint2021arXiv

Pseudo-loop conditions

We initiate the systematic study of loop conditions of arbitrary finite width. Each loop condition is a finite set of identities of a particular shape, and satisfaction of these identities in an algebra is characterized by it forcing a constant tuple into certain invariant relations on powers of the algebra. By showing the equivalence of various loop conditions, we are able to provide a new and short proof of the recent celebrated result stating the existence of a weakest non-trivial idempotent strong Mal'cev condition. We then consider pseudo-loop conditions, a modification suitable for oligomorphic algebras, and show the equivalence of various pseudo-loop conditions within this context. This allows us to provide a new and short proof of the fact that the satisfaction of non-trivial identities of height 1 in a closed oligomorphic core implies the satisfaction of a fixed single identity.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

When symmetries are not enough: a hierarchy of hard Constraint Satisfaction Problems

We produce a class of $ω$-categorical structures with finite signature by applying a model-theoretic construction -- a refinement of the Hrushosvki-encoding -- to $ω$-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate $ω$-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity, and $ω$-categorical templates that show that membership in any given complexity class cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of $ω$-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Finite Abelian algebras are dualizable

A finite algebra $\bA=\alg{A;\cF}$ is \emph{dualizable} if there exists a discrete topological relational structure $\BA=\alg{A;\cG;\cT}$, compatible with $\cF$, such that the canonical evaluation map $e\_{\bB}\colon \bB\to \Hom( \Hom(\bB,\bA),\BA)$ is an isomorphism for every $\bB$ in the quasivariety generated by $\bA$. Here, $e\_{\bB}$ is defined by $e\_{\bB}(x)(f)=f(x)$ for all $x\in B$ and all $f\in \Hom(\bB,\bA)$. We prove that, given a finite congruence-modular Abelian algebra $\bA$, the set of all relations compatible with $\bA$, up to a certain arity, \emph{entails} the whole set of all relations compatible with $\bA$. By using a classical compactness result, we infer that $\bA$ is dualizable. Moreover we can choose a dualizing alter-ego with only relations of arity $\le 1+α^3$, where $α$ is the largest exponent of a prime in the prime decomposition of $\card{A}$. This improves Kearnes and Szendrei result that modules are dualizable, and Bentz and Mayr's result that finite modules with constants are dualizable. This also solves a problem stated by Bentz and Mayr in 2013.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Finite Abelian algebras are fully dualizable

We show that every finite Abelian algebra A from congruence-permutable varieties admits a full duality. In the process, we prove that A also allows a strong duality, and that the duality may be induced by a dualizing structure of finite type. We give an explicit bound on the arities of the partial and total operations appearing in the dualizing structure. In addition, we show that the enriched partial hom-clone of A is finitely generated as a clone.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The finiteness problem for automaton semigroups is undecidable

The finiteness problem for automaton groups and semigroups has been widely studied, several partial positive results are known. However we prove that, in the most general case, the problem is undecidable. We study the case of automaton semigroups. Given a NW-deterministic Wang tile set, we construct an Mealy automaton, such that the plane admit a valid Wang tiling if and only if the Mealy automaton generates a finite semigroup. The construction is similar to a construction by Kari for proving that the nilpotency problem for cellular automata is unsolvable. Moreover Kari proves that the tiling of the plane is undecidable for NW-deterministic Wang tile set. It follows that the finiteness problem for automaton semigroup is undecidable.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The possible values of critical points between strongly congruence-proper varieties of algebras

We denote by Conc(A) the semilattice of all finitely generated congruences of an (universal) algebra A, and we define Conc(V) as the class of all isomorphic copies of all Conc(A), for A in V, for any variety V of algebras. Let V and W be locally finite varieties of algebras such that for each finite algebra A in V there are, up to isomorphism, only finitely many B in W such that A and B have isomorphic congruence lattices, and every such B is finite. If Conc(V) is not contained in Conc(W), then there exists a semilattice of cardinality aleph 2 in Conc(V)-Conc(W). Our result extends to quasivarieties of first-order structures, with finitely many relation symbols, and relative congruence lattices. In particular, if W is a finitely generated variety of algebras, then this occurs in case W omits the tame congruence theory types 1 and 5; which, in turn, occurs in case W satisfies a nontrivial congruence identity. The bound aleph 2 is sharp.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The possible values of critical points between varieties of lattices

We denote by Conc(L) the semilattice of all finitely generated congruences of a lattice L. For varieties (i.e., equational classes) V and W of lattices such that V is contained neither in W nor its dual, and such that every simple member of W contains a prime interval, we prove that there exists a bounded lattice A in V with at most aleph 2 elements such that Conc(A) is not isomorphic to Conc(B) for any B in W. The bound aleph 2 is optimal. As a corollary of our results, there are continuum many congruence classes of locally finite varieties of (bounded) modular lattices.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

From objects to diagrams for ranges of functors

Let A, B, S be categories, let F:A-->S and G:B-->S be functors. We assume that for "many" objects a in A, there exists an object b in B such that F(a) is isomorphic to G(b). We establish a general framework under which it is possible to transfer this statement to diagrams of A. These diagrams are all indexed by posets in which every principal ideal is a join-semilattice and the set of all upper bounds of any finite subset is a finitely generated upper subset. Various consequences follow, in particular: (1) The Grätzer-Schmidt Theorem, which states that every algebraic lattice is isomorphic to the congruence lattice of some algebra, can be extended to finite poset-indexed diagrams of algebraic lattices and compactness-preserving complete join-homomorphisms (and no finiteness restriction if there are large enough cardinals). (2) In a host of situations, the relative critical point between two locally finite quasivarieties is either less than aleph omega or equal to infinity. (3) A lattice of cardinality aleph 1 may not have any congruence-permutable, congruence-preserving extension.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An infinite combinatorial statement with a poset parameter

We introduce an extension, indexed by a partially ordered set P and cardinal numbers k,l, denoted by (k,l)-->P, of the classical relation (k,n,l)--> r in infinite combinatorics. By definition, (k,n,l)--> r holds, if every map from the n-element subsets of k to the subsets of k with less than l elements has a r-element free set. For example, Kuratowski's Free Set Theorem states that (k,n,l)-->n+1 holds iff k is larger than or equal to the n-th cardinal successor l^{+n} of the infinite cardinal k. By using the (k,l)-->P framework, we present a self-contained proof of the first author's result that (l^{+n},n,l)-->n+2, for each infinite cardinal l and each positive integer n, which solves a problem stated in the 1985 monograph of Erdös, Hajnal, Mate, and Rado. Furthermore, by using an order-dimension estimate established in 1971 by Hajnal and Spencer, we prove the relation (l^{+(n-1)},r,l)-->2^m, where m is the largest integer below (1/2)(1-2^{-r})^{-n/r}, for every infinite cardinal l and all positive integers n and r with r larger than 1 but smaller than n. For example, (\aleph_{210},4,\aleph_0)-->32,768. Other order-dimension estimates yield relations such as (\aleph_{109},4,\aleph_0)--> 257 (using an estimate by Füredi and Kahn) and (\aleph_7,4,\aleph_0)-->10 (using an exact estimate by Dushnik).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Categories of partial algebras for critical points between varieties of algebras

A lifting of a semilattice S is an algebra A such that the semilattice of compact (=finitely generated) congruences of A is isomorphic to S. The aim of this work is to give a categorical theory of partial algebras endowed with a partial subalgebra together with a semilattice-valued distance, that we call gamps. This part of the theory is formulated in any variety of (universal) algebras. Let V and W be varieties of algebras (on a finite similarity type). Let P be a finite lattice of order-dimension d>0. Assume that we have a diagram of semilattice with a lifting in V, but with no "partial lifting" in the category of gamps of W, then there is a semilattice S of cardinality aleph (d - 1), such that S has a lifting in V, but S has no lifting in W. We already knew a similar result for diagrams with no lifting in W, however the semilattice S constructed here has cardinality aleph d. Gamps are also used to study congruence-preserving extensions. Denote by M the variety generated by the lattice of length two, with three atoms. We construct a lattice A in M of cardinality aleph 1 with no congruence n-permutable, congruence-preserving extension, for each n > 1.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Critical points between varieties generated by subspace lattices of vector spaces

We denote by Conc(A) the semilattice of compact congruences of an algebra A. Given a variety V of algebras, we denote by Conc(V) the class of all semilattices isomorphic to Conc(A) for some A in V. Given varieties V1 and V2 varieties of algebras, the critical point of V1 under V2, denote by crit(V1;V2) is the smalest cardinality of a semilattice in Conc(V1) but not in Conc(V2). Given a finitely generated variety V of modular lattices, we obtain an integer l, depending of V, such that crit(V;Var(Sub F^n)) is at least aleph_2 for any n > 1 and any field F. In a second part, we prove that crit(Var(Mn);Var(Sub F^3))=aleph_2, for any finite field F and any integer n such that 1+card F< n. Similarly crit(Var(Sub F^3);Var(Sub K^3))=aleph_2, for all finite fields F and K such that card F>card K.

0 citations0 reviewsNo code linkedOpen access