2013/2014
SEMESTR LETNI 2013/2014
03. 06, M. Zawadowski (Uniwersytet Warszawski), Kategoryjne uogólnienie Sumy Płonki
Abstrakt. Suma Płonki została wprowadzona w latach 60-tych i od tego czasu doczekała się różnych uogólnień. W wykladzie opowiem o kategoryjnym uogólnieniu tej konstrukcji. Takie sumy można definiowac nie tylko dla modeli regularnych teorii równościowych indeksowanych sup-kratami (sup-semi-lattice), ale też szerzej dla modeli różnych innych klas teorii (na przyklad teorii liniowo-regularnych) indeksowanych pewnymi kategoriami wielomianów.
27. 05, M. Zawadowski (Uniwersytet Warszawski), Teorie równościowe i monady
Abstrakt. Będzie to wykład wprowadzający do drugiego wykładu o kategoryjnym uogólnieniu sumy Płonki. W wykładzie tym dokonam przeglądu ogólnych pojęć kategoryjnych (takich jak funktory sprzężone, (ko)granice) oraz tych związanych z teorią monad. Opowiem też o odpowiedniości pomiędzy monadami a teoriami równościowymi.
20. 05, A. Romanowska, O pewnych rozmaitościach bipółkrat
Abstrakt: Bipółkraty to algebry (B,+,.), w których (B,+) i (B,.) są półkratami. System Birkhofa to bipółkrata spełniająca równość x(x+y) = x + xy, a biłańcuch to bipółkrata, w której oba redukty półkratowe są łańcuchami. W referacie przedstawię obecny stan wiedzy na temat rozmaitości bipółkrat generowanych przez biłańcuchy.
06. 05, M. Stronkowski, Structurally complete discriminator varieties
Abstract: I will provide a characterization of structurally complete quasivarieties among almost structurally complete semisimple quasivarieties. In particular, it gives a characterization of structurally complete discriminator varieties.
29. 04, T. Brengos, Kilka słów o informatyce teoretycznej i teorii kategorii
Abstrakt: W 1989 roku J. Goguen opublikował artykuł pt. "A categorical manifesto", w którym motywuje czytelników do stosowania teorii kategorii w informatyce teoretycznej. Przedstawię pokrótce podstawowe przesłania tego manifestu i spróbuję pokazać, w jaki sposób teoria koalgebr go realizuje.
15. 04, N. Dojer (Uniwersytet Warszawski), Orthogonality and partial rewriting systems
Abstract: Term rewriting system (TRS) is a set of reduction rules, usually corresponding to an equational theory. In order to check, whether an equation holds in the theory, both equation sites are reduced to so called normal forms, which should be the same. TRS is terminating iff each reduction sequence terminates. This property is crucial for deciding equations by rewriting. On the other hand, several techniques were proposed to do without termination in so-called orthogonal systems. During the talk I will present my attempts to translate these results to partial rewriting systems, i.e. TRSs for partial algebras.
08. 04, A. Pilitowska, Entropy and generalized entropy in n-semigroups and in algebras with neutral element
Abstract: An algebra (A,F) is entropic, if every pair of its fundamental operations commutes. It is well known that there is an equivalence between the endomorphism closure property and the entropic law. A weaker version of the entropic law is the so-called generalized entropic property. On the level of varieties, the generalized entropic property may be characterized by the so-called subalgebra closure property: the variety V has the generalized entropic property iff for each algebra (A,F) in V its complex algebra of subalgebras is also a subalgebra of (A,F). In general, these two properties are not equivalent, but in some cases they are. During the talk I will present known and new results concerning relationships between the generalized entropic property and the commutativity of the fundamental operations of the algebra. In particular, I will characterize the algebras with a neutral element that have the generalized entropic property and I will show that there are certain classes of semigroups and n-semigroups for which entropicity and the generalized entropic property are equivalent. (The resent results are joint work with E. Lehtonen.)
01. 04, J. Krempa (Uniwersytet Warszawski), O pierścieniach Dedekinda
Abstrakt: Pierścienie Dedekinda odgrywają ważną rolę w teorii liczb, w geometrii algebraicznej i w innychdziałachmatematyki. Mają one szereg różnorodnych charakteryzacji. Znanych jest wiele ciekawych i użytecznych własności modułów nad pierścieniami Dedekinda. Celem referatu będzie przybliżenie tych faktów. Do zrozumienia referatu wystarczy znajomość elementarnych własności przemiennych pierścieni z jedynką. Potrzebne klasy modułów przypomnę. Wiele dalszych faktów o pierścieniach i modułach nad nimi można znaleźć w cytowanych książkach. S. Balcerzyk i T. Józefiak, "Pierścienie przemienne", J. Browkin, "Teoria ciał", S. Lang, "Algebra".
18, 25. 03, K. Grygiel, Kombinatoryczne spojrzenie na rachunek lambda i logikę kombinatoryczną
Abstrakt: W ostatnich latach coraz większym zainteresowaniem zarówno ze strony logików, jak i kombinatoryków cieszą się badania ilościowe w logikach. Szczególną uwagę poświęcono wyznaczeniu gęstości występowania tautologii wśród wszystkich formuł w badanej logice. Dzięki zastosowaniu zaawansowanych narzędzi kombinatorycznych, przede wszystkim kombinatoryki analitycznej, dość dobrze zbadane zostały logiki klasyczna i intuicjonistyczna. W referacie omówię wyniki uzyskane po przeniesieniu podejścia ilościowego na grunt modeli obliczeń. Poruszę między innymi zagadnienia związane z charakteryzacją losowych termów nietypowanego rachunku lambda oraz logiki kombinatorycznej. Oba te modele stanowią równoważny opis funkcji rekurencyjnych i rozumiane są jako wyidealizowane, wzorcowe języki programowania. Głównym celem referatu będzie przedstawienie rozwiązania niebanalnego problemu z pogranicza teorii obliczeń i kombinatoryki polegającego na oszacowaniu gęstości termów (zarówno w jednym, jak i drugim modelu) z własnością normalizacji pośród wszystkich termów. Zagadnienie to odpowiada pytaniu o prawdopodobieństwo tego, że losowy program, w tym wypadku napisany w języku rachunku lambda lub logiki kombinatorycznej, ma własność stopu. 04.02, 1. A. Romanowska, Quasi-wielościany i dualność, kontynuacja 2. Sprawy organizacyjne
SEMESTR ZIMOWY 2013/2014
21. 01, A. Romanowska, Quasi-wielościany i dualność
Abstrakt: Quasi-wielościanem nazywamy zbiór wypukły, którego domknięcie jest wielościanem. Rozważamy quasi-wielościany jako algebry barycentryczne. Referat poświęcony będzie problemowi istnienia dualności dla klasy wszystkich quasi-wielościanów, rozszerzającej dwie znany dualności: dla (skończonych) półkrat, i dla wielościanów.
14. 01, 2014, A. Mućka, Duality via truth for distributive interlaced bilattices
Abstract: Duality via truth is a duality between classes of algebras and the classes of their associated relational systems (frames). Our intention is to view algebras and frames as being semantic structures for formal languages. Having a semantics of a formal language under consideration, we can define the notion of truth of its formulas. A duality principle underlying the duality via truth stated that a given class of algebras and a class of frames provide equivalent semantics in the sense that a formula is true with respect to one semantics iff it is true with respect to the other semantics. As a consequence, the algebras and the frames express equivalent notion of truth.
17. 12, M. Stronkowski, Structural completeness for varieties of closure algebras
Abstract: I will present the proof that an almost structurally complete variety V of closure algebras is structurally complete iff V satisfies McKinsey axiom iff V does not have a 4-element simple algebra.
10. 12, K. Matczak, Nieskierowane repliki binarnych algebr skierowanych (praca wspólna z J. D. H. Smithem)
Abstrakt: Dimonoidy i ogólnie algebry skierowane otrzymujemy z algebr uniwersalnych przez potraktowanie każdej operacji podstawowej jako wielu różnych operacji skierowanych lub wybranie argumentów operacji fundamentalnej danej algebry. W referacie opiszemy nieskierowane repliki skierowanych algebr binarnych: dimonoidów, digrup i diquasigrup. Repliki są to największe algebry ilorazowe otrzymane przez utożsamienie dwóch skierowanych "mnożeń".
03. 12, T. Kowalski (La Trobe University, Melbourne), Graph colourings and Relation Algebras
Abstract: We will consider the following Ramsey-like problem. For a given number n of colours, is there a complete graph K_m such that the edges of K_m can be coloured with the n colours in such a way that: - there are no monochromatic triangles, - every non-monochromatic triangle appears everywhere it can. The first condition gives an upper bound for the possible size of K_m, via Ramsey theorem. The second condition is really a shorthand for the following two requirements: (i) every vertex of K_m has at least one outgoing edge of each colour, and (ii) given any edge (x,y) of colour c, and any colours a, b, such that {a,b,c} is different form {c}, there exist a vertex z such that (x,z) is coloured by a and (z,y) is coloured by b. To satisfy the second condition the graph K_m cannot be too small: this gives a lower bound for the possible size of K_m. For n=2, the lower bound is 5, and so is the upper bound because R(3,3) = 6. For n = 3, the upper bound is 16, the lower bound can be shown to be 13, and indeed K_13 gives one possible answer. Curiously, no colourings satisfying both conditions exist for K_14 and K_15. For K_16 there exist two non-isomorphic ones. For n=4,5 suitable colourings were found by S. Comer. For n>5 the answer was not known, and listed as an open question in Maddux's "Relation Algebras" (Elsevier,2006). I will show that a required colouring can be obtained from a finite field satisfying certain conditions. Unfortunately, I have no general existence theorem for such fields, but computer searches have shown that they exist for all n betwen 2 and 120, except n = 8, and (possibly) n = 13.
28. 11 (9-10, sala 317), J. Bulin (Charles University in Prague and Johannes Kepler University Linz), Subpower membership problem
Abstract: Let A be a finite, finitely presented algebra. The "Subpower membership problem (SMP)" for A is the following decision problem: Given a_1,...,a_n,b in A^n, decide if b lies in the subalgebra of A^n generated by {a_1,...,a_n}. The naive algorithm runs in EXPTIME and, indeed, M. Kozik constructed an algebra A such that the SMP for A is EXPTIME-complete. On the other hand, for several well known classes of algebras the problem is in P; for instance algebras with a near unanimity term (Baker-Pixley Theorem), finite fields (Gaussian elimination), groups (Schreier-Sims algorithm). We will discuss several results towards the following open problem: Is it true that the SMP is in P for every Maltsev algebra (Willard), or even for every algebra with Few subpowers (Idziak, Mar' oti, McKenzie, Valeriote, Willard)?
27. 11 (9-10, sala 318), P. Jedlicka (Czech University of Life Sciences in Prague), Commutative automorphic loops
Abstract: The lecture will be devoted to historical and recent results about commutative automorphic loops which became one of the main topics of contemporary loop theory. We shall present all the known structural results as well as some examples and connections to other varieties of loops.
26. 11, D. Stanovsky (Charles University in Prague), Commutator theory, nilpotence, and solvability: from general to specific
Abstract: In the first lecture, I will present the basics of the commutato> theory, as developed in universal algebra. In particular, I will explain the abstract notions of abelianess, nilpotence, and solvability. In the second lecture, I will discuss the problem of specializing the general theory to a concrete class, namely the groups and loops. (The latter is a new result jointly with Petr Vojtechovsky.)
19. 11, M. Ziembowski, O modułach nad pierścieniami rozdzielnymi
Abstrakt: Podczas referatu przedstawione zostaną nowe rezultaty dotyczące własności modułów nad pierścieniami rozdzielnymi. Zaprezentowane także zostaną przykłady ilustrujące otrzymane wyniki.
12. 11, A. Zamojska-Dzienio, O złożoności krat podklas
Abstrakt: Wiadomo, że kraty podquasirozmaitości mogą być bardzo skomplikowane. Dobrze odzwierciedla ten fakt własność Q-uniwersalności wprowadzona przez M.Sapira w 1985 r. Ostatnio, A.Nurakunov pokazał, że nie istnieje algorytm pozwalający zdecydować, czy dana skończona krata zanurza się w kratę podquasirozmaitości (dla algebr unarnych). To także pokazuje, że takie kraty mogą być bardzo złożone. Razem z M.Semenovą badałyśmy związki między obiema własnościami. W referacie przedstawię nasze rezultaty.
05. 11, A. Pilitowska, Entropiczne quandle
Abstrakt: Tematem referatu będą quandle: idempotentne i lewo-dystrybutywne grupoidy, w których lewe translacje są bijekcjami. W szczególności zostanie przedstawiona reprezentacja entropicznych quandli jako sumy grup abelowych. Będą także scharakteryzowane entropiczne quandle abelowe.
29. 10, J. Kaleta, G. Bińczak, Effect algebras
Abstrakt: Przedstawione zostaną definicje, twierdzenia, przykłady i problemy otwarte dotyczące tzw. "effect algebras", i w szczególności tzw. "sequential effect algebras.''.
15 i 22. 10, T. Brengos, Słaba bisymulacja dla koalgebr nad uporządkowanymi monadami
Abstrakt: Celem referatu jest przedstawienie koalgebraicznych definicji słabej bisymulacji dla koalgebr typu T, gdzie T jest uporządkowaną monadą spełniającą kilka dodatkowych warunków. Referat będzie podzielony na cztery części. W pierwszej części referatu zajmę się etykietowanymi systemami przejścia i przypomnę różne ale równoważne definicje słabej bisymulacji. Kluczem do definiowania słabej bismulacji dla LTSów jest pojęcie nasycenia struktury, w którym uwzględniamy wielokrotne nieme kroki. Etykietowane systemy przejścia mogą być równoważnie definiowane jako koalgebry typu P(S x Id), gdzie S jest pewnym zbiorem etykiet. Funktor P(S x Id) możemy w dość intucyjny sposób wyposażyć w strukturę monady, lub zanurzyć w monadę. Ta sztuczka pozwoli nam zdefiniować nasycenie używając pojęć teorii kategorii. W drugiej części referatu przedstawię wyniki, które uogólniają konstrukcje dla LTSów do koalgebr typu T(F+Id), gdzie T jest monadą spełniającą pewne dodatkowe warunki. W trzeciej części przedstawię definicje słabej bisymulacji dla T-koalgebr, gdzie T jest uporządkowaną *-monadą, czyli pewnym uogólnieniem tzw. monad Kleenego. Czwarta i ostatnia część referatu poświęcona będzie dalszym planom badawczym związanych z powyższymi konstrukcjami i definicjami.
08. 08, godz. 12.00, A. Kazda, Absorption: Where to find it and how to decide it.
Abstract: While studying the complexity of the Constraint Satisfaction Problem, Libor Barto and Marcin Kozik discovered the idea of absorption. If the algebra B absorbs the algebra A, then many kinds of connectivity properties of A are also true for B. This is very useful for proofs by induction, and absorption has since played a role in several other universal algebraic situations. After giving a taste of how absorption works, we would like to talk about our current project (which is a joint work with Libor Barto): How to decide, given an algebra A with finitely many basic operations and some B <= A, if B absorbs A.