Classes of algebras and clones  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
60148
Type K
Principal investigator Zádori, László
Title in Hungarian Algebraosztályok és klónok
Title in English Classes of algebras and clones
Keywords in Hungarian algebra, varietás, félcsoport, háló, geometria, klón
Keywords in English algebra, variety, semigroup, lattice, geometry, clone
Discipline
Mathematics (Council of Physical Sciences)100 %
Panel Mathematics and Computing Science
Department or equivalent Bolyai Institute (University of Szeged)
Participants B. Szendrei, Mária
Czédli, Gábor
Dormán, Miklós
Maróti, Miklós
Szabó, László
Szendrei, Ágnes
Waldhauser, Tamás
Starting date 2006-02-01
Closing date 2010-01-31
Funding (in million HUF) 16.000
FTE (full time equivalent) 3.47
state closed project
Summary in Hungarian
A tervezett projektben algebraosztályok --varietások, hálóosztályok és félcsoportosztályok -- vizsgálatával foglalkozunk. Az algebrák term- ill. polinomműveleteinek klónjai lényeges szerepet játszanak kutatásainkban. Így érthető, hogy a klónok tanulmányozása önmagában is fontos részét képezi a pályázatnak.

A projekt keretében kutatandó témák az univerzális algebra, félcsoportelmélet, hálóelmélet és klónelmélet nemzetközi érdeklődésre számot tartó, jelenleg is művelt területeiről kerülnek ki. A tervezett kutatások a projektben résztvevő kutatók és nemzetközileg elismert kutatók eredményeire támaszkodnak.

Terveink szerint az eredmények és a publikációk a következő speciális témakörökben várhatók: végesen generált varietások struktúralemélete, reziduált hálók, félcsoportfedők elmélete, hálóazonosságok és geometriák kapcsolata, G-zárt klónok, klónhálóbeli monoidális intervallumok, centralizátor klónok szerkezete.

A projekt keretében elért eredményekhez alkalmazásokat keresünk más tudományterületen, pl. a számítástudomány területén, speciálisan a bonyolultságelméletben és az eldönthetőségi elméletben.
Summary
The project proposed focuses on the study of structural properties of classes of algebras such as varieties of algebras, classes of semigroups and lattices. Information obtained on the clones of term operations or polynomial operations of algebras plays a crucial role in these investigations. Hence the study of clones itself is an essential part of the present proposal.

The topics investigated in the project are in the main stream of current research in the field of universal algebra, semigroup theory, lattice theory and clone theory. The research proposed relies on earlier results of the participants and internationally acknowledged experts of these fields.

Our aim is to prove and publish new results in the following specific subjects:
structure theory of finitely generated varieties, varieties of residuated lattices, covers of semigroups, connection of lattice equations and geometries, G-closed clones, monoidal intervals in the clone lattice, centralizer clones.

We search for applications of the new results in other disciplines such as computer science, in particular, complexity theory and decidability theory.




 

Final report

  
Results in Hungarian
Főbb eredményeink a következők. Beláttuk, hogy többségi kifejezésfüggvény létezése eldönthető véges algebrákra. Igazoltuk, hogy bármely nem-triviális idempotens Malcev-feltételt teljesítő véges algebrának van gyenge többségi kifejezésfüggvénye, és 2-uniform kongruenciái felcserélhetőek. Bizonyítottuk, hogy a k-parallelogramma-kifejezéssel rendelkező véges, reziduálisan kicsi algebrák és a véges 2-nilpotens csoportok kifejezésfüggvényeinek klónját véges sok reláció meghatározza. Új dichotómiatételeket kaptunk a kényszer-kielégíthetőségi problémára és az egyenletrendszer-megoldhatósági problémára. Számos új eredményt kaptunk hálók kombinatorikai vonatkozásairól, fraktál- és féligmoduláris hálókról. Struktúratételeket bizonyítottunk az E-tömör lokálisan inverz félcsoportokra, az E-unitér majdnem faktorizálható ortodox félcsoportokra, valamint kiterjesztettük a majdnem faktorizálható inverz félcsoportok elméletét a lokálisan inverz félcsoportok osztályára. Jellemeztünk bizonyos transzformáció-monoidokat, amelyek egyelemű monadikus intervallumot határoznak meg a klónhálóban. Leírtuk a centralizátorklónt véges, egyszerű, idempotens algebrák és bizonyos kongruencia disztributív varietást generáló véges algebrák esetén. Új eredményeket kaptunk 3-változós többségi függvénnyel rendelkező minimális klónokra. Beláttuk, hogy a kompozícióra zárt függvényosztályok hálója kontinuum számosságú a kételmű halmazon, és leírtuk e háló szerkezetét.
Results in English
Our main results are as follows. We proved that the existence of a near-unanimity term operation is decidable for finite algebras. We showed that if a finite algebra admits a nontrivial idempotent Maltsev condition, then it has a weak near-unanimity term operation, and its 2-uniform congruences permute. We proved that the clone of any finite residually small algebra with a k-parallelogram term operation and any finite 2-nilpotent group is determined by finitely many relations. We obtained new dichotomy theorems for the constraint satisfaction problem and for the solvability problem of systems of equations. We proved a number of theorems on the combinatorial aspects of lattices and on fractal and semimodular lattices. We obtained new structure theorems for E-solid locally inverse semigroups and E-unitary almost factorizable orthodox semigroups. Furthermore we extended the theory of almost factorizable inverse semigroups to the class of locally inverse semigroups. We characterized certain transformation monoids which determine a one-element monoidal interval in the lattice of clones. We described the centralizer clones of finite simple idempotent algebras and of certain algebras in congruence distributive varieties. We obtained new results on the minimal clones containing majority operations. We proved that on the two-element set the lattice of function classes closed under composition has the cardinality of the continuum, and described the structure of this lattice.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=60148
Decision
Yes





 

List of publications

  
[BS1] Szendrei, M. B., Szittyai, I: E-solid locally inverse semigroups, kézirat, 2006
[BS2] Szendrei, M. B: Problems on finite regular semigroups, Proc. Conf. “International Symposium on Semigroups and Applications” (eds. A. R. Rajan, L. John); 37-45, 2007
[BS3] Szendrei, M. B.: E-unitary almost factorizable orthodox semigroups, kézirat, 2008
[BS4] Szendrei, M. B.: Almost factorizable locally inverse semigroups, kézirat, kézirat, 2009
[C01] G. Czédli: Idempotent Mal'cev conditions and 2-uniform congruences, Algebra Universalis 59, 303-309, 2008
[C02] G. Czédli: Some new closures on orders, Mathematica Slovaca, elfogadva, 2009
[C03] G. Czédli, B. Seselja and A. Tepavcevic: On the semidistributivity of elements in weak congruence lattices of algebras and groups, Algebra Universalis, 58, 349-355, 2008
[C04] G. Czédli: Some varieties and convexities generated by fractal lattices, Algebra Universalis, 60, 107-124, 2009
[C05] G. Czédli: The product of von Neumann n-frames, its characteristic, and modular fractal lattices, Algebra Universalis, 60, 217-230, 2009
[C06] G. Czédli: The number of rectangular islands by means of distributive lattices, European Journal of Combinatorics, 30, 208-215, 2009
[C07] G. Czédli: A fixed point theorem for stronger association rules and its computational aspects, Acta Cybernetica, 19, 149-158, 2009
[C08] G. Czédli: Stronger association rules for positive attributes, Novi Sad Journal of Mathematics, 38, 103-110, 2008
[C09] G. Czédli: On averaging Frankl's conjecture for large union-closed sets, Journal of Combinatorial Theory - Series A, 116, 724-729, 2009
[C10] G. Czédli and E. T. Schmidt: How to derive finite semimodular lattices from distributive lattices?, Acta Mathematica Hungarica, 121/3, 277-282, 2008
[C11] G. Czédli, M. Maróti and E. T. Schmidt: On the scope of averaging for Frankl's conjecture, Order, 26, 31-48, 2009
[C12] G. Czédli and E. T. Schmidt: CDW-independent subsets in distributive lattices, Acta Sci. Math. (Szeged), 75, 49-53, 2009
[C13] G. Czédli and E. T. Schmidt: Frankl's conjecture for large semimodular and planar semimodular lattices, Acta Univ. Palacki. Olomuc., Fac. rer. nat., Mathematica 47, 2008
[C14] G. Czédli, M. Hartmann and E.T. Schmidt: CD-independent subsets in distributive lattices, Publicationes Mathematicae Debrecen, 74/1-2 , 127-134, 2009
[C15] G. Czédli: A visual approach to test lattices, Acta Univ. Palacki. Olomuc., Fac. rer. nat., Mathematica, elfogadva, 2008
[C16] G. Czédli, M. Erné, B. Seselja and A. Tepavcevic: Characteristic triangles of closure operators with applications in general algebra, Algebra Universalis, elfogadva, 2008
[C17] G. Czédli and M. Maróti: Two notes on the variety generated by planar modular lattices, Order, 26, 109-117, 2009
[C18] G. Czédli and E. T. Schmidt: A cover-preserving embedding of semimodular lattices into geometric lattices, Advances in Mathematics, benyújtva., 2008
[C19] G. Czédli and M. Maróti: On the height of order ideals, Mathematica Bohemica, elfogadva, 2009
[C20] G. Czédli and E. T. Schmidt: Finite distributive lattices are congruence lattices of almost-geometric lattices, Algebra Universalis, benyújtva, 2008
[C21] G. Czédli: Sums of lattices and a relational category, Order 26, 309–318, 2009
[C22] G. Czédli, B. Skublics: The ring of an outer von Neumann frame in modular lattices, Algebra Universalis, elfogadva, 2009
[D1] Dormán, M: Collapsing monoids consisting of permutations and constants, Algebra Universalis 58, 479--492, 2008
[D2] Dormán, M: A 6-element monoidal interval, kézirat, 2007
[M1] M. Maróti: On the (un)decidability of a near-unanimity term, Algebra Universalis 57, no 2, 215–237, 2007
[M2] M. Maróti, R. McKenzie: Existence theorems for weakly symmetric operations, Algebra Universalis 59 no. 3–4, 463–489, 2008
[M3] W. Dziobiak, M. Maróti, R. McKenzie, A. Nurakunov: The weak extension property and finite axiomatizability for quasivarieties, Fundamenta Mathematicae, benyújtva, 2007
[M4] L. Barto, M. Kozik, M. Maróti, R. McKenzie and T. Niven: Congruence modularity implies cyclic terms for finite algebras, Algebra Universalis, elfogadva, 2008
[M5] W. Dziobiak, J. Ježek and M. Maróti: Varieties and quasivarieties of semilattices with one automorphism, Semigroup Forum, elfogadva, 2008
[M6] L. Barto, M. Kozik, M. Maróti and T. Niven: CSP dichotomy for special triads, Proceedings of the AMS 137, 2921–2934, 2009
[M7] J. Ježek, T. Kepka and M. Maróti: The endomorphism semiring of a semilattice, Semigroup Forum 78, no. 1, 21–26, 2009
[M8] C. Carvalho, V. Dalmau, P. Marković and M. Maróti: CD(4) has bounded width, Algebra Universalis 60, 3, 293–307, 2009
[M9] M. Maróti: The existence of a near-unanimity term in a finite algebra is decidable, Journal of Symbolic Logic 74, 3, 1001–1014, 2009
[SL1] László Szabó: On algebras with primitive positive clones, Acta Sci. Math. (Szeged) 73, 2007
[SZ1] K. A. Kearnes, J. Shaw, Á. Szendrei: Clones of 2-step nilpotent groups, Algebra Universalis 59, 491-512., 2008
[SZ2] E. Lehtonen, Á. Szendrei: Equivalence of operations with respect to discriminator clones, Discrete Math., 309, 673—685, 2009
[SZ3] K. A. Kearnes, Á. Szendrei: Clones of parallelogram algebras, benyújtva, 2009
[SZ4] E. Lehtonen, Á. Szendrei: Clones with finitely many relative R-classes, benyújtva, 2009
[SZ5] E. Lehtonen, Á. Szendrei: The submaximal clones on the three element set with finitely many relative R-classes, Discussiones Mathematicae, General Algebra and Applications, elfogadva, 2009
[W1] T. Waldhauser: Minimal clones with few majority operations, Acta Sci. Math. (Szeged) 73, 471--486, 2007
[W2] S. Liebscher, T. Waldhauser: On associative spectra of operations, Acta Sci. Math. (Szeged), 75, 433—456, 2009
[W3] T. Waldhauser: On composition-closed classes of Boolean functions, kézirat, 2008
[W4] M. Berisch, T. Waldhauser: Minimal clones with many majority operations, kézirat, 2009
[Z1] L. Zádori: Solvability of systems of polynomial equations over finite algebras, Internat. J. Algebra Comput Vol 17, Issue 4, 821-835, 2007
[Z2] B. Larose, M. Valeriote, L. Zádori: Omitting types, bounded width and the ability to count, Internat. J. Algebra Comput. 19, 5, 647–668, 2009
[Z3] L. Zádori: Subspace lattices of finite vector spaces are 5-generated, Acta Sci. Math. (Szeged), 74, 491--497, 2008
[Z4] J. Nesetril, M. Siggers, L. Zádori: A combinatorial CSP dichotomy classification conjecture, European Journal of Combinatorics 31, No. 1, 280-296, 2010
[Z5] L. Zádori: On solvability of systems of polynomial equations, Algebra Universalis, benyújtva, 2009




 

Events of the project

  
2009-02-11 09:13:48
Résztvevők változása



Back »