


Universal Algebra and Complexity / Algèbre universelle et complexité Org: Jennifer Hyndman (UNBC), Benoit Larose (Concordia) and/et Denis Therien (McGill)
 DAVID MIX BARRINGTON, University of Massachusetts Amherst, Amherst, MA 01003, USA
Complexity for Groupoids Given by Table

Suppose we are given a complete multiplication table for a groupoid
(binary algebra) and are asked to evaluate a given product of
elements, or determine whether an element is generated by a given set
of elements. In general, these problems are complete for the
complexity classes LOGCFL (also known as SAC^{1}) and P
respectively, and by restricting the class of groupoids possible we
get a variety of other interesting problems. In this talk we survey
some results and open problems in this area. In particular, we show
how results on the iterated product problem for groups
(BarringtonKadauLangeMcKenzie 2001) led to the solution of a
longstanding open problem about integer division
(HesseAllenderBarrington 2002).
 MARTIN BEAUDRY, Université de Sherbrooke, Sherbrooke, QC J1K 2R1
Finite aperiodic loops as languagerecognizing devices

Since it was proved that finite loops recognize exactly the open
regular languages, the aperiodic, or groupfree, loops have emerged as
a promising special case. In particular, the languages they recognize
happen to be starfree. This opens the problem of developing a
workable characterization of the open starfree languages.
This is joint work with François Lemieux and Denis Thérien.
 MANUEL BODIRSKY, HumboldtUniversität zu Berlin
Constraint Satisfaction Problems with Infinite Domains

The complexity of constraint satisfaction problems is intensively
studied for finite templates. In this talk I will discuss constraint
satisfaction problems with a template over an infinite domain. I
focus on templates that are omegacategorical, a wellknown concept in
model theory. For this class, several techniques known for constraint
satisfaction with finite templates still applyin particular, I will
discuss generalizations of wellknown Galoisconnections, and the
notion of a core of a relational structure.
 ANDREI BULATOV, Simon Fraser University, Burnaby, Canada
Complexity of constraint counting problems

We consider the problem #CSP(B):
given a relational structure A, compute the number of homomorphisms
from A to the relational structure B. We give some examples and
show the connection between the complexity of #CSP(B) and the
polymorphisms of B.
We identify two necessary conditions
for the tractability of #CSP(B):
(1) B has a Mal'tsev polymorphism,
(2) every pair of equivalence relations definable in B
(congruences of the corresponding algebra Alg(B)) satisfies
certain combinatorial conditions.
Finally we show that these conditions are also sufficient for the
tractability of #CSP(B) when satisfied by every finite algebra
from the variety generated by Alg(B).
 VICTOR DALMAU, Universitat Pompeu Fabra
Constraint Satisfaction Problems and the Expressiveness of
Finite Algebras

Constraint satisfaction problems arise in a wide variety of domains,
such as combinatorics, logic, and artificial intelligence. In recent
years, much effort has been directed towards classifying the
complexity of all families of constraint satisfaction problems. It
has been shown that it is possible to associate to every subclass of
the CSP an algebra A such that the complexity the
corresponding CSP is completely determined by the properties
of A.
Let A be any algebra over a finite universe. We define the
expressiveness of A as the mapping
ex_{A} : N ® N that
given a natural number n returns the number subuniverses of
A^{n}. Some algebras A that lead to tractable
cases of the CSP such as Mal'tsev algebras, or algebras containing a
nearunanimity operations among their term operations, satisfy the
following property: logex_{A} (n) £ p(n), for some
polynomial p. We call any such algebra polynomially
expressible. We conjecture that all polynomially expressible
algebras give rise to families of constraint satisfaction problems
solvable in polynomial time. In this talk we shall present some
initial results in this direction.
 RICARD GAVALDA, Universitat Politecnica de Catalunya, Barcelona, Spain
Learnability of functions defined by programs over
semigroups

Computational Learning Theory studies the existence of algorithms that
provably and efficiently learn classes of functions, under a rigorously
defined model of "learning". Learning via queries is one such
model, and among the best studied ones: it assumes that an external
agent knows one target function from the class, and the learning
algorithm must identify that function exactly by asking the agent
queries from a predefined set.
In this talk, we survey recent works studying the learnability of
classes of functions defined by several variants of programs over
monoids or semigroups. In many contexts, it is possible to design
learning algorithms that learn whole (and natural) varieties of
semigroups, which in turn can compute classes of functions that had
been independently studied in Computational Learning Theory. Often,
one can show that the limit of learnability (e.g., using a fixed
set of query types) coincides exactly with such a variety of
semigroups, suggesting a strong connection between the algebraic
complexity of semigroups and their learning complexity.
 PAVOL HELL, Simon Fraser University, Burnaby, BC V5A 1S6
List Partition Problems

List partition problems are certain restrictions of binary list
constraint satisfaction problems. A. Bulatov has recently proved the
dichotomy of all list constraint satisfaction problems. The speaker
and Tomás Feder used Bulatov's result to prove the following
`quasidichotomy' for list partition problems:
Each list partition problem is NPcomplete or solvable in
quasipolynomial time (of order n^{O(logn)}).
There are examples of list partition problems for which the best known
algorithms have performance n^{O(logn/loglogn)}. (These
algorithms are also joint with D. Krá\'l and J. Sgall.)
Variants in which the number of occurences of a variable, and/or the
sizes of the lists, are bounded by small constants, will also be
discussed.
 MIKI HERMANN, LIX, Ecole Polytechnique, France
An Algebraic Approach to the Complexity of Generalized
Conjunctive Queries

Constraint satisfaction is recognized as a fundamental problem in
artificial intelligence, in automated deduction, in computeraided
verification, in operations research, etc. At the same time
conjunctive query containment is considered as a fundamental problem
in database query evaluation and optimization. Recent research points
out that query containment is a central problem in several database
and knowledge base applications, including data warehousing, data
integration, query optimization, and (materialized) view maintenance.
Kolaitis and Vardi pointed out that constraint satisfaction and
conjunctive query containment are essentially the same problem.
Constraints are usually specified by means of relations. The standard
constraint satisfaction problem can therefore be parameterized by
restricting the set of allowed relations. In particular, given a
finite set S of Boolean relations, we consider conjunctive
propositional formulas consisting of clauses built over relations
from S, also called Sformulas. Deciding the satisfiability of
such an Sformula is known as the generalized satisfiability
problem, denoted by SAT(S), and was first investigated by
Schaefer. It turns out that the complexity of SAT(S) can
be characterized by closure properties of S. This correspondence is
obtained through a generalization of Galois theory. In order to get
complexity results via this algebraic approach, conjunctive queries
COQ(S) over a set of relations S turn out to be useful.
Roughly speaking, a conjunctive query from COQ(S) is an
Sformula with distinguished variables, where all nondistinguished
variables are existentially quantified. These queries play an
important role in database theory, since they represent a broad class
of queries and their expressive power is equivalent to
selectjoinproject queries in relational algebra. Thus they are also
of interest in their own right and we study the complexity of some
related computational problems. The algebraic approach is
particularly well adapted to this study, yielding short and elegant
proofs.
We focus here on the counting problem for conjunctive queries. The
problem is to count the number of entries in the database that match
the query, i.e., the number of satisfying assignments. We
obtain a complete complexity classification that indicates a
difference with respect to satisfiability problems of Boolean
constraints.
Measures such as conditional probability (confidence) and correlation
have been used to infer rules of the form "buying diapers causes you
to buy beer". However, such rules indicate only a statistical
relationship between items, but they do not specify the nature and
causality of the relationship. In applications, knowing such causal
relationship is extremely useful for enhancing understanding and
effecting change. While distinguishing causality from correlation is
a truly difficult problem, recent work in statistics and Bayesian
learning provide some promising directions of attack.
In this context, the ideas of Bayesian learning, where techniques are
being developed to infer casual relationships from observational data,
to mining large databases trigger the necessity to study counting
problems in connection with existing database applications. Yet
another recent application of Bayesian learning based on counting is
the task of spam elimination.
Therefore we think that our results will have an impact on concrete
database implementations and applications, since the considered
formulas in our computational problems correspond better to the model
of queries formulated within existing database systems than the so far
mainly studied Sformulas.
While the complexity of conjunctivequery evaluation and constraint
satisfaction is the same, we determined that this is not any more the
case for other computational goals. We have shown that the counting
problem for conjunctive queries has a different structure than that
for conjunctive formulas. The latter displays a dichotomy behavior
between the affine formulas in FP and the
#Pcomplete other cases, whereas the former presents a
trichotomy structure between the affine cases in FP, the
Horn, dual Horn, and bijunctive #Pcomplete cases, and
finally the general #·NPcomplete case. This
shows that, under the more finegrained analysis presented by
counting, the conjunctive queries present three different levels of
(in)tractability.
This is a joint work with Michael Bauland, Philippe Chapdelaine, Nadia
Creignou, and Heribert Vollmer.
 ANDREI KROKHIN, University of Durham, Department of Computer Science, Science
Labs, South Road, Durham DH1 3LE, UK
Supermodular lattices and the complexity of constraint
optimisation

The maximum constraint satisfaction problem (MaxCSP) is an
optimisation version of the CSP. In MaxCSP, one is given
a collection of constraints on overlapping sets of variables, and the
goal is to find an assignment of values to the variables which
maximizes the number of satisfied constraints. This problem is
NPhard in general, but, by restricting the set of allowed constraint
types, one can obtain a tractable (that is, polynomialtime solvable)
problem. This talk is an account of recent progress made in
classifying the complexity of MaxCSP with respect to the set of
allowed constraints. In particular, we will explain the role played
by the condition of supermodularity on finite lattices in attempts to
solve the above mentioned classification problem.
The talk is based on joint work with M. Cooper, D. Cohen, P. Jeavons,
P. Jonsson, M. Klasson, and B. Larose.
 GABOR KUN, Eotvos Lorand University, Pazmany Peter setany 1/c, Budapest,
Hungary, H1117
On the fundamental group and coverings of finite posets

The complexity of the Constraint Satisfaction Problem (CSP) is one of
the most examined questions in complexity theory. The known cases of
NPcomplete CSP's are those relational structures which does not admit
any nontrivial idempotent operation. Feder and Vardi have proved that
every CSP is polynomialtime equivalent to a poset retraction
problem. The typical, known posets admitting no nontrivial idempotent
operation are the crowns.
In our talk we introduce a combinatorial definition of the fundamental
group of posets. This combinatorial definition leads to the same
typecovering theorems than in the case of topological spaces. We
give a characterization of posets from those no crown can be obtained
using retracts and finite covering posets.
Theorem 1
Let P be a finite connected poset. Then the following conditions
are equivalent.
(i) A crown is a retract of a finite covering poset of P.
(ii) The additive group of the integers is the homomorphic
image of a finite index subgroup of the fundamental group of P.
 FRANCOIS LEMIEUX, Université du Québec à Chicoutimi, 555 boul. de
l'Université, Chicoutimi, Québec G7H 2B1
Groupoids that recognize only regular languages

It is known that finite groupoids (finite set closed under a binary
operation) can be seen as a model of computation that generalises
finite semigroups. The sets they recognize is exactly the class of
contextfree languages. Previous studies in groupoid theory have made
extensive use of the multiplication semigroup of a groupoid G that
is the closure under composition of the transformation R_{g}(x)=xg and
L_{g}(x)=gx for all g Î G. In this talk we will consider those
groupoids that can only recognize regular languages.
We prove that any groupoid whose multiplication semigroup belongs to
the pseudovariety DO (where the set of idempotents of each regular
Jclass forms a subsemigroup) can recognize only regular languages.
An important subclass of such groupoids is the set of loops whose
multiplication semigroup is a group.
We show that any loop that recognizes a language L must be divided
by all groups that divide the syntactic monoid of L. Hence, any
loop that contains only trivial groups can only recognize languages in
AC^{0}.
 CYNTHIA LOTEN, Simon Fraser University, 8888 University Drive, Burnaby, BC
V5A 1S6; University College of the Fraser Valley, 33844 King
Road, Abbotsford, BC V2S 7M8
Retractions on Reflexive Graphs

A graph H is called a retract of a graph G if H is a subgraph of
G and there is an edge preserving function from G to H that
fixes each vertex of H. Such a function is called a retraction.
The question is, given a fixed graph H and an arbitrary
supergraph G, when does a retraction from G to H exist? There
are no known conditions that are both necessary and sufficient for the
existence of retraction, and there are graphs H for which the
question is NPc. However, we can take a necessary condition N,
and create a class of graphs H called absolute retracts with respect
to N, AR_{N}, for which N is also a sufficient
condition. The various classes of absolute retracts studied are all
varieties and can be analyzed using nearunanimity functions,
dismantlability, chordal graphs and totally symmetric idempotent
functions.
 JAROSLAV NESETRIL, Department of Applied Mathematics and Institute of
Theoretical Computer Science, Charles University, Prague,
Czech Republic
Density, Complexity, Universality

We exhibit a connection of density (of homomorphism order of finite
structures) and the complexity of the corresponding Constraint
Satisfaction Problems. We survey recent solution of density problem
for various classes of structures including oriented trees and planar
graphs. This is also related to universality of very special classes
of strutures.
The results were obtained jointly with C. Tardif, P. Ossona de Mendez,
T. Luczak and R. Strausz.
 STEVE SEIF, Mathematics Department, Univ. of Louisville, Louisville, KY
40292
Word and constraint satisfaction problems

Progress has been made on the question of whether
constraintsatisfaction problems on finite sets "admit a dichotomy"
using algebraic methods. Essentially the same question exists for
word problems for finite algebras. The connection between the two
dichotomy questions will be discussed.
 HOWARD STRAUBING, Boston College, Chestnut Hill, Massachusetts, USA
Cvarieties of Morphisms into Finite Monoids

Eilenberg and Schutzenberger showed how pseudovarieties of finite
monoids and semigroups form the foundation in universal algebra for
the algebraic theory of finite automata and the languages they accept.
Recent results, principally from the domains of circuit complexity,
finite model theory and temporal logic, suggest that these foundations
are inadequate. We introduce a more general notion, Cvarieties of
morphisms into finite monoids, that includes the older theory as a
special case and accounts for all the new results.
We give the basic definitions and the
generalization of Eilenberg's correspondence theorem, and present a
theorem that shows how Cvarieties arise naturally in firstorder
logic, temporal logic and circuit complexity. (Preliminary versions
of these results were originally announced, without detailed proofs,
in 2002.)
We develop the equational theory for
Cvarieties and semidirect products of Cvarieties, and give
several applications. This is based on joint work with J. E. Pin and
L. Chabard. The equational theory was developed independently by
M. Kunc.
 CSABA SZABÓ, Eötvös Loránd University, Budapest, 1117 Pázmány
Péter sétány I/C
The compexity of solving polynomials over finite algebras

For a finite algebra, A checking an equation (Termeq
A) or solving a polynomial (Polsat A) is a
classical problem. But the notion of polynomial has a different
meaning over a ring or over a ring as a universal algebra. In the
first case it is a sum of monomials in the second case it is sums of
products of sums of .... For the two element ring Z_{2} in the
first case the Polsat problem can be solved in polynomial time; in the
second case it is NPcomplete (J. Lawrence, R. Willard). For the
group A_{4} both problems are solvable in polynomial time. But if we
introduce the commutator as a new operation (why not? the operation
table can be obtained at the preprocessing) both problems turn out to
be hard (G. Horváth, Cs. Szabó). From now we allow to add
finitely many basic operations to the algebra and we look for the
"maximal" complexity of the Termeq and Polsat problems, called
Termeq* and Polosat*. We characterize the Polsat* problem for
congruence modular algebras and the Termeq* problem for groups.
 PASCAL TESSON, Université Laval
On the complexity of solving systems over finite semigroups

For a fixed finite semigroup, we consider the problem EQN^{*}_{S} of
determining whether a system of equations over S has a solution. We
show that when S is a monoid, then EQN^{*}_{S} is solvable in
polynomialtime if S is a commutative union of groups but is
NPcomplete otherwise. We also show that providing a similar
dichotomy result for all finite semigroups would resolve the dichotomy
conjecture for constraint satisfaction problems.
 JIRI TUMA, Charles University in Prague, Faculty of Mathematics and
Physics, Sokolovska 83, 186 00 Prague 8, Czech Republic
Congruence liftings of diagrams

A lifting of a diagram of semilattices and homomorphisms with respect
to the functor Con in a variety V is a simultaneous
representation of all semilattices as semilattices of compact
congruences of algebras in V and all semilattice homomorphisms as
the Con values of homomorphisms between the representing algebras
in V. We present a small diagram D of Boolean subsemilattices of
the semilattices 2^{4} such that no variety V allowing a lifting
satisfies a nontrivial congruence identity. This is a joint work of
F. Wehrung and J. Tuma.
 MATT VALERIOTE, McMaster University, Hamilton Ontario, Canada
Tractable Algebras and Congruence Distributivity

A finite algebra A is said to be tractable if the
collection of all subuniverses of finite powers of A forms
a tractable constraint language. It is conjectured by Bulatov,
Jeavons, and Krokhin that a finite idempotent algebra A is
tractable if and only if the equational class generated by A omits the
unary type from Tame Congruence Theory.
The property of an algebra having bounded relational width was
introduced by Bulatov and Jeavons and is closely related to the
concept of bounded width developed by Feder and Vardi. The
satisfaction of either property by a finite algebra ensures that it is
tractable. It is conjectured that a finite idempotent algebra
A has bounded relational width if and only if the
equational class generated by A omits both the unary and
affine types. Algebras that generate congruence distributive
equational classes are examples of algebras of this kind.
In my talk I will discuss the bounded relational width conjecture and
in particular the results of Larose and Zadori relating to it. I will
also discuss progress made towards determining whether or not finite
algebras in congruence distributive equational classes have bounded
relational width.
 ROSS WILLARD, University of Waterloo, Waterloo, Ontario N2L 3G1
Finitely axiomatizable varieties and pseudovarieties

I report on recent work on an open problem of S. Eilenberg and
M. Schützenberger from 1976, recently revived by G. McNulty,
namely: if the pseudovariety HSP_{fin} (A) generated by
a finite algebra is finitely axiomatizable (i.e., relative to
the axiom "I am finite"), does it follow that the variety
HSP(A) generated by A is also finitely
axiomatizable?

