| Esperanza | López Centella | Weak wreath products and weak quantum duplicates | \title{Weak wreath products and weak quantum duplicates}
\author{Esperanza L\'opez Centella}
Wreath products are the key for the (strict) factorization problem. As it is well-known, given an associative and unital algebra $(H,\mu_H,\eta_H)$, this is isomorphic to a wreath product of algebras $A$ and $B$ if and only if there exist injective algebra morphisms $A\stackrel{i_A}{\to} H \stackrel{i_B}{\leftarrow}$ such that $\mu_H(i_A\otimes i_B)$ is a linear isomorphism. In this talk we recall the factorization problem answered by a \textit{weak wreath product} of algebras. Motivated by arguments from Mathematical Physics, we introduce the notion of \textit{weak quantum duplicate} of an algebra, a construction based on a weak wreath product of the algebra under consideration and a two-dimensional factor. We provide a characterization of weak quantum duplicates of a finite-dimensional algebra, extending that one of quantum duplicates given in \cite{Cibils}. As an application, we explicitly describe a great part of the set of weak factorization structures (equivalently, weak distributive laws \cite{Street}) existing between two two-dimensional associative unital algebras over a field, classifying (up-to isomorphism) the weak wreath products arising from them and covering the description in \cite{CortEtAll}.
\bibitem{Cibils}
C. Cibils, \textit{Non-conmutative duplicates of finite sets}, J. Algebra Appl. \textbf{5} (2006), no. 3, 361-377.
\bibitem{CortEtAll}
\'O. Cortadellas, G. Navarro, J. López-Pe\~na, \textit{Factorizations structures with a two-dimensional factor}, J. London Math. Soc \textbf{2} (2010), no. 81, 1-23.
\bibitem{Street}
R. Street, {\em Weak distributive laws}, Theory and Appl. of Categories 22 (2009), no. 22, 313--320. |
| Michiro | Kondo | Reticulations on residuated lattices | A notion of reticulation which provides topological properties on algebras has introduced on commutative rings in 1980 by Simmons. For a given commutative ring $A$, a pair $(L,\lm)$ of a bounded distributive lattice and a mapping $\lm : A \to L$ satisfying some conditions is called a reticulation of $A$, and the map $\lambda$ gives a homeomorphism between the topological space $Spec(A)$ consisting of prime filters of $A$ and the topological space $Spec(L)$ consisting of prime filters on $L$. The concept of reticulation are generalized to non-commutative rings, MV-algebras, BL-algebras, quantale and so on. Since these algebras are axiomatic extensions of residuated lattices which are algebraic semantics of so-called fuzzy logic, it is natural to consider properties of reticulations on residuated lattices. In 2008, Mure\c{s}an has published a paper about reticulations on residuated lattices and she has provided an axiomatic definition of reticulations on residuated lattices, in which five conditions are needed. In this talk, we show that only two independent conditions of reticulation are enough to axiomatize reticulations on residuated lattices and also prove that reticulations on residuated lattices can be considered as homomorphisms between residuated lattices and bounded distributive lattices. |
| Zoltán | Ésik | Equational properties of stratified least fixed points | A novel fixed point theorem has recently been proved involving non-monotonic functions between stratified complete lattices. The stratified least fixed point operator extends the classical least fixed point operator over monotonic functions of complete lattices. The theorem finds applications in logic programming and knowledge representation and reasoning. The main results show that the new fixed point operator satisfies {\bf the standard} identities of fixed point operators as described by the axioms of iteration theories.
|
| Kamil | Kozłowski | On Armendariz and semi-Armendariz rings | A ring $R$ is called Armendariz if whenever polynomials $f = \sum a_i x^i$ and $g = \sum b_j x^j$ in $R[x]$ satisfy $fg = 0$, then $a_ib_j = 0$ for all $i, j$. The name of these rings honors E.P. Armendariz, who noted in \cite{Armendariz} that all reduced rings satisfy this condition. Armendariz rings were introduced by M.B. Rege and S. Chhawchharia in \cite{Rege}.
In \cite{AndersonCamillo}, D.D. Anderson and V. Camillo proved that for any $n \geq 2$, a~ring~$R$ is Armendariz if and only if for any polynomials $f_1, f_2, \ldots, f_n \in R[x]$,
$$(\ast) \ \ \text{$f_1 f_2 \cdots f_n = 0$ \ implies \ $a_1 a_2 \cdots a_n = 0,$}$$
where $a_i$ is a coefficient of $f_i$. In \cite{Jeon}, Y.C. Jeon, Y. Lee and S.J. Ryu generalized the notion of an Armendariz ring by defining a ring $R$ to be $n$-semi-Armendariz if condition $(\ast)$ holds in the case where $f_1 = f_2 = \ldots = f_n$, i.e. if whenever the $n$-th power of a polynomial $f \in R[x]$ is zero, then the products of any $n$ coefficients of $f$ are all zero. A ring $R$ is called semi-Armendariz if $R$ is $n$-semi-Armendariz for any positive integer $n$. Armendariz rings, semi-Armendariz rings and numerous other types of Armendariz-like rings are extensively studied by many authors (see \cite{KM}, \cite{MMZarmendariz} and the literature quoted therein).
In this talk, we will discuss properties of Armendariz and semi-Armendariz rings, and identify some Armendariz and $n$-semi-Armendariz subrings of matrix rings.
\bibitem{AndersonCamillo}
D.D. Anderson, V. Camillo, {\it Armendariz rings and
Gaussian rings,} Comm.\ Algebra 26 (1998), 2265--2272.
\bibitem{Armendariz}
E.P. Armendariz, {\it A note on extensions of Baer and
P.P.-rings,} J. Austral.\ Math.\ Soc.\ 18 (1974), 470--473.
\bibitem{Jeon}
Y.C. Jeon, Y. Lee, S.J. Ryu, {\it A structure on coefficients of nilpotent polynomials,} J. Korean Math. Soc. 47 (2010), 719--733.
\bibitem{KM}
K. Koz{\l}owski, R. Mazurek, {\it On semi-Armendariz matrix rings}, J. Korean Math. Soc. 52 (2015), 781--795.
\bibitem{MMZarmendariz}
G. Marks, R. Mazurek, M. Ziembowski, {\it A unified
approach to various generalizations of Armendariz rings,} Bull. Aust. Math. Soc. 81 (2010), 361--397.
\bibitem{Rege}
M.B. Rege, S. Chhawchharia, {\it Armendariz rings,} Proc. Japan Acad. Ser. A Math. Sci. 73 (1997), 14--17. |
| Pasha | Zusmanovich | Robinson--Amitsur ultrafilters | An old ring-theoretic result due to A. Robinson and S. Amitsur says that if a prime ring is embedded into a direct product of rings, then it is embedded into their ultraproduct. A suitable reformulation of this result in the language of universal algebra implies a criterion of absence of nontrivial identities of an algebraic system within a given variety, an alternative proof of a toy version of Regev's $A \otimes B$-theorem, some properties of Tarski's monsters, and some other interesting, and disjoint at the first glance, things. We will also discuss generalization of this embedding to ultraproducts over $\kappa$-complete ultrafilters and its (un)applicability to classical algebraic structures. (Based on arXiv:1508.07496 and arXiv:0911.5414). |
| Nebojša | Mudrinski | Bounds on the length of terms in various types of algebras | As usual, for a given algebra of a given type, we define the length of a term as the number of fundamental operational symbols and variables that occur in the term. In general, it is not easy to determine the minimal length of $n$-ary terms such that among all $n$-ary terms of that length one can find $n$-ary terms that represent all different $n$-ary term functions of the algebra. We present a general bound, but also bounds on the length of terms for functionally complete algebras, certain $3$-supernilpotent finite expanded groups and some other examples showing that such a bound can vary from linear to exponential in the number of arguments.
This is joint research with E. Aichinger. |
| Claudia | Mureșan | Going Up and Lying Over in Congruence--modular Algebras | Coauthor: George Georgescu
Properties {\em Going Up (GU)} and {\em Lying Over (LO)} have been extensively studied in commutative rings \cite{kap}; more recently, their investigation in MV--algebras \cite{bel} and BL--algebras \cite{rada} has been initiated. For the purpose of extending this previous work to a more general context, we define and study properties GU and LO in an arbitrary congruence--modular equational class ${\cal C}$. Let $f:A\rightarrow B$ be a morphism in ${\cal C}$ and $f^*$ be the inverse image of $f\times f:A\times A\rightarrow B\times B$. For any member $M$ of ${\cal C}$ and any congruence $\theta $ of $M$, we denote by ${\rm Spec}(M)$ the set of the prime congruences of $M$, and by $[\theta )$ the set of the congruences of $M$ which include $\theta $. We say that $f$ is {\em admissible} iff $f^*({\rm Spec}(B))\subseteq {\rm Spec}(A)$. Surjective morphisms are admissible, but the converse is not true. Now assume that $f$ is admissible. We say that $f$ fulfills {\em GU} iff, for all $\phi \in {\rm Spec}(B)$, $[f^*(\phi ))\cap {\rm Spec}(A)\subseteq f^*([\phi )\cap {\rm Spec}(B))$. We say that $f$ fulfills {\em LO} iff $[{\rm Ker}(f))\cap {\rm Spec}(A)\subseteq f^*({\rm Spec}(B))$. GU implies LO, and the converse holds for surjective morphisms. In the classes of Boolean algebras and residuated lattices, all morphisms are admissible and fulfill GU and LO. In the class of bounded lattices, not all morphisms are admissible, nor do all admissible morphisms fulfill GU or LO. Admissibility, GU and LO are preserved by quotients. If ${\cal C}$ is semi--degenerate and the congruences of finite direct products of algebras in ${\cal C}$ are products of congruences of the terms of these products of algebras, then, in ${\cal C}$, admissibility, GU and LO are preserved by finite direct products.
\bibitem{agl} P. Agliano, Prime Spectra in Modular Varieties, {\em Algebra Universalis} 30 (1993), 581--597.
\bibitem{bel} L. P. Belluce, The Going Up and Going Down Theorems in MV--algebras and Abelian l--groups, {\em J. Math. An. Appl.} 241 (2000), 92--106.
\bibitem{fremck} R. Freese, R. McKenzie, {\em Commutator Theory for Congruence--modular Varieties}, London Mathematical Society Lecture Note Series 125, Cambridge University Press, 1987.
\bibitem{kap} J. Kaplansky, {\em Commutative Rings}, First Edition: University of Chicago Press, 1974; Second Edition: Polygonal Publishing House, 2006.
\bibitem{rada} S. Rasouli, B. Davvaz, An Investigation on Boolean Prime Filters in BL--algebras, {\em Soft Computing} 19, Issue 10 (October 2015), 2743--2750. |
| Danica | Jakubíková-Studenovská | Construction of a complement to a quasiorder | Coauthor: Lucia Janičková
Monounary algebras $(A, f)$ whose lattices of quasiorders are complemented have been characterized as follows: (C) $f(x)$ is a cyclic element for all $x \in A$, and all cycles have the same square-free number $n$ of elements. Sufficiency of the condition (C) was proved by means of transfinite induction. We will describe a construction of a complement to a given quasiorder of $(A, f)$ satisfying (C). |
| Jan | Kühr | Special elements in lattices with antitone involutions | coauthor: Petr Emanovský
We describe two boolean skeletons of lattices with antitone involutions and under certain conditions we characterize subdirectly irreducible pseudocomplemented lattices with antitone involutions. |
| Reinhard | Pöschel | Permutation patterns and permutation groups | Consider a permutation $\pi\in S_{n}$ as a string $\pi_{1}\dots\pi_{n}$ where $\pi_{i} = \pi(i)$ for all $i \in \{1,\dots,n\}$ and hence $\{\pi_{1},\dots,\pi_{n}\}=\{1,\dots,n\}$.
A permutation $\sigma \in S_{m}$ with $m\leq n$ that is obtained from a substring of $\pi$ of length $m$ by compressing it to numbers $1,\dots,m$ while keeping unchanged the relative order of the elements is called a ($m$-)\textit{pattern} of $\pi$.
In this talk we report on some problems, results and applications in connection with permutation patterns. In particular we consider permutation groups which can be characterized by permutation patterns (e.g., by avoiding prescribed patterns).
(coauthor: Erkko Lehtonen) |
| Přemysl | Jedlička | Distributive quasigroups of order 243 | Finite non-medial distributive quasigroups exist only in orders that are powers of 3. The smallest examples, of order 81, were enumerated by T. Kepka and P. Němec in the 80's. We continue their work by enumerating non-medial distributive quasigroups of order 243. |
| Ganna | Kudryavtseva | Free skew Boolean algebras | I will present the structure results about the structure of free skew Boolean algebras and free skew Boolean intersection algebras, including the theories of normal forms and calculation of various combinatorial characteristics of these algebras. The results on free skew Boolean algebras are based on a joint work with Jonathan Leech.
|
| Erhard | Aichinger | On the relational degree of a clone | In 2011, Davey, Jackson, Pitkethly and Szab\'o defined the \emph{relational degree} of an algebra as the smallest $d \in \mathbb{N}_0$ such that the clone of term functions is determined by its at most $d$-ary invariant relations (when such a $d$ exists). We will state a preservation property that yields the following consequence:
"Let $\mathbf{A}$ be a finite algebra of finite type with edge term that generates a residually small variety. Then there is a $k \in \mathbb{N}$ such that every algebra in this variety is of relational degree at most $k$."
We will also investigate countably infinite algebras and obtain that a clone with quasigroup operations on a countable set is either locally closed, or its local closure is uncountable. |
| Esma | Kangal | The Word Problem for Aut(Fn) | In combinatorial group theory, Max Dehn introduced the decision problems such as the word problem, the conjugacy problem and the isomorphism problem in $1911$. There are many studies on the word problem in the literature. Novikov and Boone showed that there exists a finitely presented group whose word problem is unsolvable. Therefore to show a finitely presented group has solvable word problem is important. In here, we study on the word problem of the automorphism group $Aut(F_n)$ of a free group with rank n. In particular, we use the method of rewriting system on the presentation of $Aut(F_n)$ to solve this problem. |
| Libor | Polák | Several hierarchies of classes of piecewise testable languages | In DLT 2008 we studied the following classes of languages: Let $k$ be a natural number, a {\it monomial} over an alphabet $A$ is the language $A^*a_1A^*a_2\dots a_lA^*,\ l\leq k$. Let $B_k$ be the set of all Boolean combinations of monomials, let $P_k$ be the set of all finite intersections of finite unions of monomials and $D_k$ that of all finite unions of monomials.
The levels of classes of regular languages starting from the most restrictive case are: Boolean varieties, positive varieties, disjunctive varieties (well-known), and weak ones.
Basically there are three worlds: classes of languages, classes of (enriched) semiautomata (no initial and no final stated) and those of appropriate algebraic structures.
Given a regular language and one of four levels above, we naturally define the canonical automaton and the syntactic structure. It is also desirable to consider general semiautomata a appropriate algebraic structure for each level.
We are going to concentrate on examples. We will cosider also new hierarchies of p.t. languages. |
| Jan | Paseka | Partial tense MV-algebras | In this lecture we characterize the restriction of arbitrary meets of MV-morphism to a suitable domain into a unit interval as so-called partial semi-states. Using this, we show that any partial fm-function $G$ between semisimple MV-algebras is representable via the canonical total fm-function $G^*:[0,1]^T \to [0,1]^S$. In particular, any partial tense semisimple MV-algebra is representable in this way. |
| Joanna | Kaleta | Sharp and principal elements in effect algebras | In this talk we characterize the effect algebras whose sharp and principal elements coincide. I present partially solution to the problems: when the set of sharp (principal) elements is closed under orthosum. |
| Péter P. | Pálfy | Small congurence lattices | Mostly based on the 2012 PhD dissertation of William J. DeMeo, we will discuss which small lattices can be represented as congruence lattices of finite algebras or intervals in subgroup lattices of finite groups.
|
| Ulrich | Knauer | Planar (right) groups | Planar (right) groups
Ulrich Knauer, Berlin
Joint work with Kolja Knauer, Marseille
In 1896 Maschke characterized planar groups [4]. A group $G$, or more generally an algebraic structure is called planar, if its Cayley graph can be embedded in the plane. i. e. on a surface of genus 0. The (right) Cayley graph $Cay(G,C)$ is constructed in the traditional way: the (group) elements are the points of the graph, for the arcs select a (minimum) generating system of $C\sse G$ and connect two points $g,g'\in G$ if there exists $c\in C$ such that $gc=g'$. The automorphism group of this (directed color) graph is isomorphic to $A$.
It turns out that there are only finitely many planar groups, plus four infinte series: $\{\Z_n\}$, $\{\Z_n\times \Z_2\}$, and $\{\D_n\}$, $\{\D_n\times \Z_2\}$. For more information on this and related topics see for example [3].
There are some results for planar Clifford semigroups [8] – no characterization so far - or for direct products of cyclic semigroups [6,7]. Since there are so many semigroups, a general characterization seems hopeless.
A promising approach is to look at semigroups which are unions of groups (completely regular semigroups), like Clifford semigroups, or right/left groups.
A right group is of the form $G\times R_n$ where $G$ is a group and $R_n$ is the $n$-element right zero semigroup.
We characterize planar right groups with respect to right Cayley graphs [2].
It is obvious that in this case a left group $G\times L_n$ is planar iff $G$ is planar.
It might also be interesting, to investigate semigroups, whose Cayley graph is embeddable on orientable/non-orientable surfaces of higher genus, like torus, projective plane, Kleinian bottle etc. [1]. For groups some more results are known, see for example [5].
[1] Kolja Knauer and Ulrich Knauer, Toroidal embeddings of right groups, Thai J. Math. 8 (2010), no. 3, 83--490.
[2] – , – , Planar right groups, Semigroup Forum 92(1) (2016), 142—157.
[3] Ulrich Knauer, Algebraic Graph Theory. Morphisms, Monoids and Matrices, de Gruyter Studies in Mathematics, vol. 41, Walter de Gruyter & Co., Berlin and Boston, 2011
[4] Heinrich Maschke, The Representation of Finite Groups, Especially of the Rotation Groups of the Regular Bodies of Three-and Four-Dimensional Space, by Cayley's Color Diagrams, Amer. J. Math. 18 (1896), no. 2, 156—194.
[5] Viera K. Proulx, Classification of toroidal groups, J. Graph Theory 2 (1978), 269—273.
[6] DenisV. Solomatin, Direct products of cyclic semigroups admitting a planar Cayley graph. Sibirskie Elektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] 3 (2006), 238--252 (in Russian).
[7] –, Semigroups with outerplanar Cayley graphs, Sibirskie Elektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] 8 (2011), 191--212 (in Russian).
[8] Xia Zhang, Clifford semigroups with genus zero, in: Semigroups, Acts and Categories with Applications to Graphs, Proceedings, Tartu 2007, Mathematics Studies, vol. 3, Estonian Mathematical Society, Tartu, 2008, pp. 151--160. |
| Jaroslav | Šeděnka | Recovering short generators of principal ideals in some cyclotomic fields of two-prime order | Several proposed cryptographic protocols based on ideal lattices, such as Soliloquy encryption scheme or Smart and Vercauteren homomorphic encryption, use principal ideals with short generators in cyclotomic fields. It was later suggested ([1], [2]) to use the logarithm embedding to recover such generator, and a rigorous proof for such attack was later provided by [3] for the case when the cyclotomic ring is a prime power.
In this talk, we will discuss how to modify the aforementioned methods from prime-power cyclotomic fields to cyclotomic fields with the order of two distinct primes. |
| László | Márki | Morita equivalence for semigroups without identity | Since 2011-12 there is a satisfactory theory of Morita equivalence for semigroups with local units. In the present talk it will be discussed how one can proceed in more general cases.
This is joint work with Valdis Laan. |
| Branimir | Šešelja | Omega-complete lattices | Starting with omega sets introduced by Fourman and Scott in late seventies as a model of intuitionistic logic, we develop an order-theoretic and algebraic approach to omega structures. Omega is a complete lattice, and an $\Omega$-poset is a triple $(M,R,E)$ where $M\neq\emptyset$, $R:M^2\rightarrow\Omega$ is a transitive ($R(x,y)\wedge R(y,z)\leq R(x,y)$) and strict ($R(x,y)\leq R(x,x)\wedge R(y,y)$) $\Omega$-valued mapping, while the map $E:M^2\rightarrow\Omega$, defined by $E(x,y)=R(x,y)\wedge R(y,x)$, acts as an $\Omega$-valued equality on $M$. Particular $\Omega$-posets are $\Omega$-complete lattices, having pseudo-suprema and pseudo-infima for subsets.
For all these mappings an important tool is a cut, a subset of the domain ($M$ or $M^2$) which is the principal filter generated by an element of the lattice $\Omega$. We prove that an $\Omega$-poset is an $\Omega$-lattice if and only if all quotient structures of cuts over the corresponding cut equalities are complete lattices under the order induced by $R$, and the set inclusion among them is compatible with the order in $\Omega$. We also prove that $\Omega$ posets and complete lattices can be constructed from closure systems of transitive and strict relations. |
| Eylem | Guzel Karpuz | Gröbner-Shirshov Basis Theory and Word Problem for Some Group Constructions | The Gröbner-Shirshov basis theory was developed by A. I. Shirshov for Lie algebra and B. Buchberger for commutative algebras. It was also generalized by G. M. Bergman and L. A. Bokut to the case of associative algebras. This theory is a powerful tool to solve many problems; normal form, word problem, embedding theorems, ets. In this talk, we give Gröbner-Shirshov bases of some group constructions, namely, knit product of cyclic groups, central extension of groups and crossed product of cyclic groups. It gives a new algorithm for getting normal form, and thus a new algorithm for solving the word problem in these group constrcuctions.
This work is supported by Tübitak Project No 113F294. |
| Nurten | Urlu | Gröbner-Shirshov bases of rook monoid and some complex reflection groups | The Gröbner-Shirshov basis theory was developed by A. I. Shirshov for Lie algebras and B. Buchberger for commutative algebras. This theory is very useful in the study of presentations of associative algebras, Lie algebras, semigroups and groups by generators and defining relations. The aim of this talk is to give Gröbner-Shirshov bases of rook monoid and some congruence class of primitive complex reflection groups. Hence we obtain normal forms of elements of these group structures.
This work is supported by Tubitak Project No 113F294.
|
| Erkko | Lehtonen | Reconstructing functions and unique identification minors | The identification minors of a function of several arguments are formed by setting any two of its arguments equal. We present some results -- both positive and negative -- and open problems concerning the following reconstruction problem: Is every function of several arguments uniquely determined, up to permutation of arguments, by the collection of its identification minors? A related open problem is to determine which functions have a unique identification minor.
This talk is partly based on joint work with Miguel Couceiro and Karsten Schölzel. |
| Esra | Kırmızı Çetinalp | Growth Series and Rewriting System for Two-Sided Crossed Product of Cyclic Groups | There is a long history of studying combinatorial structures in the context of infinite groups. One example is growth series, where for a given set of generators, one counts the number of elements of length $n$, and converts this sequence into a formal power series. By calculating such series, it becomes possible to classify related groups. In this work, we consider monoid presentation of two-sided crossed product of cyclic groups. By using monoid version of this presentation, we obtain complete rewriting systems, Gröbner-Shirshov bases and then give normal forms of elements of this product. After that, by using these obtained normal forms we compute growth series.
This work is supported by Tübitak Project No 113F294. |
| Szabolcs | Iván | Algebraic characterization of temporal logics on forests | We associate a temporal logic $\mathrm{FL}(\mathcal{L})$ to a class $\mathcal{L}$ of (regular) forest languages where a forest is an ordered finite sum of finite unranked trees. Under a natural assumption of the set $\mathcal{L}$ of modalities we derive an algebraic characterization of the forest languages definable in $\mathrm{FL}(\mathcal{L})$, in terms of the iterated “Moore product” of forest automata. Using this characterization we derive a polynomial-time algorithm to decide definability of the fragment $\mathrm{EF}^*$ of \mathrm{CTL}, evaluated on forests. |
| Ivan | Chajda | Representing quantum structures as near semirings | We introduce the concept of a near semiring with involution. Generalizing the theory of semirings we aim at represent quantum structures, such as basic algebras and orthomodular lattices, by means of near semirings with involution. In particular, after discussing several properties of near semirings, we introduce the so-called Lukasiewicz near semirings and we show that every basic algebra is term equivalent to a such near semiring. If this Lukasiewicz near semiring becomes a semiring, we obtain as a corollary a representation of MV-algebras. Analogously, we introduce orthomodular near semirings as an particular case of Lukasiewicz near semirings and we show that they represent orthomodular lattices. We show that these representations are one-to-one correspondences. Moreover, we will get important congruence properties of Lukasiewicz near semirings. |
| Jorge | Almeida | The omega-inequality problem for concatenation hierarchies of star-free languages | We investigate when an inequality of $\omega$-terms is valid in a given level of a concatenation hierarchy of star-free languages. The main result shows that this
problem is decidable for all levels of the Straubing-Th\'erien hierarchy. Combined with the $\omega$-reducibility of such levels for the inequality $x\le y$ in the sense of Almeida and Steinberg, this would yield decidability of the membership problem of all levels of the hierarchy, which is considered one of the major open problems in finite semigroup theory, namely in its connections with theoretical computer science.
This is joint work with Ond\v rej Kl\'ima and Michal Kunc. |
| Dmitriy | Zhuk | The proof of CSP Dichotomy Conjecture for 5-element domain | We present the proof of Constraint Satisfaction Problem (CSP) Dichotomy Conjecture for 5-element domain.
Precisely, we prove the remaining part of this conjecture showing that
a CSP instance can be solved in polynomial time if all constraints are preserved by a Weak Near-Unanimity operation.
|
| Mike | Behrisch | Approximating closest homomorphisms into Boolean CSP-templates | We study the following CSP approximation problem (\textsf{NearestOtherSolution}, abbreviated \textsf{NOSol}): given a conjunctive Boolean propositional formula and a satisfying assignment to the variables occurring therein, what is the complexity of determining a distinct satisfying assignment that is as close as possible to the given one w.r.t.\ Hamming distance.
Stated differently: given a Boolean CSP-template (a Boolean relational structure of finite type) and a homomorphism from a finite structure of the same type into the template, what is the complexity of approximating (in terms of Hamming distance) another homomorphism between these structures.
The talk focusses on the clone theoretic background tools employed to give a complete classification of the approximation complexity for such problems; it is based on joint work with Gernot Salzer (TU Wien), Miki Hermann (\'Ecole Polytechnique, Palaiseau) and Stefan Mengel (CRIL, Universit\'e d'Artois, Lens) published as \textit{Give Me Another One!}, Proceedings of the 26th Annual International Symposium on Algorithms and Computation (ISAAC~2015), Nagoya (Japan), LNCS, 9472, Springer, Berlin, Heidelberg, November 2015, pp.~664--676. http://dx.doi.org/10.1007/978-3-662-48971-0_56. |
| Jakub | Opršal | Properties that are not characterizable by linear identities | We will discuss several properties that can be described by a~Mal'cev condition, or by some infinite set of identities, but cannot be described by any set of linear identities. This has also a connection to the lattice of interpretability types of varieties; we will show two linear idempotent Mal'cev conditions whose meet in the interpretability lattice cannot be characterized by linear identities. |
| Andreja | Tepavčević | Characterization of posets connected to preference structures | Weakly orthocomplemented posets are introduced and investigated in connection to poset-valued preference structures, as a generalization of orthocomplemented posets. Different representations of such posets will be presented. Moreover, necessary and sufficient conditions for a pointwise closure system to be a system of cuts of a poset valued preference structures with a fixed co-domain will be given. Also we give a convenient representation of posets via join-irreducibles in the framework of poset valued intuitionistic structures. |
