93. Arbeitstagung Allgemeine Algebra

Date: | 10 - 12 February 2017 |

Location: | Bern University of Applied Sciences, Business School, Brückenstrasse 73, 3005 Bern Website |

The AAA-series (Arbeitstagung Allgemeine Algebra) is a series of workshops in the field of general algebra that has taken place twice a year for more than 40 years, usually at universities in Germany and Austria, but also in other European countries, including Switzerland. The meetings are organized by local colleagues. The traditional AAA was founded in 1970 by Rudolf Wille, Darmstadt.

Since then, twice a year researchers meet to exchange their views and results in algebra and related topics. The general coordination stayed with Rudolf Wille until 1995, when after 50 conferences he passed it on to Reinhard Pöschel and Bernhard Ganter, Dresden. From 2013 the series is coordinated by Erhard Aichinger, Linz, Austria.

Adler Behrisch Chajda Ciobanu Clark Clark_2 Gumm Janičková Kazda Kötters Kompatscher Kramer Krishna Kwuida Länger Lele Molaei Opršal Temgoua Valota Volkov Zumbrägel

We are happy to announce the plenary lectures of:

Heriot Watt University Edinburgh, UK

Solving equations in free groups and semigroups has important connections to algebra, geometry and unification theory, and was shown to be decidable by Makanin in the 1980's. Since Makanin's algorithm is extremely complex, there have been efforts to simplify and modify it for the last 30 years.

In this talk I will describe work with Murray Elder and Volker Diekert on finding all solutions to an equation in a free group in an efficient way. We prove that the set of all solutions to an equation of length n can be encoded in a finite graph, where solutions can be simply read-off the graph, and the graph can be constructed in NSPACE(n log n).

State University of New York, New Paltz, USA

Theorems of Rosenberg and Rousseau make it easy to determine if a finite groupoid is primal. But finding a term to represent an operation on a primal groupoid is computationally unfeasible by standard methods. This talk will present an efficient evolutionary algorithm to do this. Two theorems explain the success of this algorithm, one based on the assumption that the groupoid is idemprimal and the other based on the assumption that its term to term operation function is continuous. A third theorem gives a condition for term continuity using two efficiently testable properties that appear to hold for almost all finite groupoids. This algorithm has potential application to circuit design and to cryptography.

TU Dresden, Germany

Virtually all of today's public-key cryptosystems are based either on the integer factorisation problem or the discrete logarithm problem. However, Shor's algorithm renders all of them completely broken once a quantum computer is built, so the search for alternatives is a very active ongoing research area.

The quantum attack on the discrete logarithm problem makes substantial use of the cyclic group structure, so that generalising the viewpoint by considering semigroup actions makes sense. A promising candidate for a cryptographically interesting semigroup action is based on matrices over simple semirings. These are semirings that do not allow for smaller homomorphic images so that a Pohlig-Hellman-type attack is avoided. Recent results on the classification of finite simple semirings (in terms of residuated maps in lattices) provide a wealth of effective examples. Further research is required to assess the security of the resulting cryptosystems.

TU Wien, Austria / Charles University Prague, Czech Republic

When the term clone of a finite algebra satisfies non-trivial equations (i.e., equations not satisfiable by projections), then this has numerous interesting consequences for the structure of the algebra, some of which are quite recent discoveries. Even more recently, analogous consequences of non-trivial equations have been shown for oligomorphic algebras, i.e., algebras on a countably infinite domain whose term clone contains a sufficiently large permutation group. In particular, surprising links between equations in algebras and model-theoretic concepts have appeared. We survey these results and their applications to constraint satisfaction problems in theoretical computer science.

Universität Marburg, Germany

A signature F is a Set-Endofunctor. While algebraic signatures correspond to polynomial functors, and thereby are rather plain objects, coalgebraic signatures, in order to model all kinds of state based systems, must exhaust the full spectrum of Set-Endofunctors.

Preservation properties of such signature functors have a vital influence on their co-algebraic theories. Among those properties studied are: weak preservation of pullbacks, of kernel pairs or of preimages. We add to this weak preservation of constant maps, i.e. that Fc is a constant map whenever c was. Inspired by an observation in a paper by Dent, Kearnes and Szendrei, we prove that every connected monadic functor weakly preserves the pullback of constant maps.

We briefly investigate such conditions for functors arising as free-algebra functors F_{V}(X) where V is a variety of universal algebras. If V is a Malcev variety then F_{V}(X) weakly preserves pullbacks. Conversely, if V is n-permutable and F_{V} weakly preserves pullbacks, then V must be Malcev.

University of Bern, Switzerland

Algebraic structures of a kind similar to these we will discuss in this talk surfaced first in [1]. The basic idea is to formulate laws governing the behaviour of abstract pieces of information. This results in two-sorted algebras (Φ, E) where Φ is a commutative idempotent semigroup (modeling the "pieces of information") and E a collection of maps ε_{q} : Φ→Φ, associated to a set Q of questions in such a way that for φ ∈ Φ and q ∈ Q, ε_{q} (φ) is the information contained in φ which is relevant to the question q.

The purpose of the talk is NOT to justify the usefulness of these algebras for Theoretical Computer Science by exhibiting many examples and applications there (they exist, see e.g. [2]), but rather to examine them from the point of view of (Universal) Algebra, especially with to goal of finding uniform representations of such algebras by rather simple set theoretical constructs over a basic universe. In order to make these lofty statements somewhat precise, we remark that Cignoli's Q-distributive lattices [3] (and Halmos' Monadic algebras) are special cases of commutative information algebras.

[1] Shenoy, P., and Shafer, G. Axioms for Probability and Belief-Function Propagation, in Machine Intelligence and Pattern Recognition, Vol. 9 (1990), 169 - 198

[2] Kohlas, J., Information Algebras: Generic Structures for Inference Series: Discrete Mathematics and Theoretical Computer Science, Springer 2003

[3] Cignoli, R., Quantifiers on distributive lattices, Discrete Mathematics 96, 183 - 197

University of Yaounde I, Cameroon

We first have a look at some subclasses of residuated lattices that are not MTL-algebras; then we give some examples of fuzzy algebraic structures, with focus on fuzzy filters of lattices and fuzzy ideals of rings. The lattice of fuzzy ideals of a ring supports a structure of residuated lattice.