Algebraic structures and algorithms  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
48809
Type K
Principal investigator B. Szendrei, Mária
Title in Hungarian Algebrai struktúrák és algoritmusok
Title in English Algebraic structures and algorithms
Panel Mathematics and Computing Science
Department or equivalent Bolyai Institute (University of Szeged)
Participants Hartmann, Miklós
Maróti, Miklós
Szabó, László
Szendrei, Ágnes
Waldhauser, Tamás
Zádori, László
Starting date 2005-01-01
Closing date 2009-12-31
Funding (in million HUF) 11.730
FTE (full time equivalent) 7.00
state closed project





 

Final report

  
Results in Hungarian
A pályázat keretében három témakörben --- általános algebra, félcsoportelmélet és döntési problémák bonyolultsága --- nyertünk eredményeket. A kutatás jelentős része hazai, illetve külföldi kutatókkal való együttműködésben született. Bebizonyítottuk, hogy algebrák egy igen tág osztályában azokat a véges algebrákat, amelyek reziduálisan kicsi varietást generálnak, meghatározzák a c-változós kompatibilis relációi, ahol c csak az osztály egy paraméterétől és az alaphalmaz nagyságától függő konstans. Meghatároztuk a legfeljebb 4 többségi függvényt tartalmazó minimális klónokat, valamint azokat a minimális klónt generáló kétváltozós műveleteket, amelyek „majdnem asszociatívak”. Általánosítottuk kvázivarietásokra Willard véges azonosságbázis tételét, és egy speciális esetben bebizonyítottuk Pigozzi relatív kongruenciamoduláris kvázivarietásokra vonatkozó véges azonosságbázis sejtését. Jellemeztük a kötegek csoportokkal vett szemidirekt szorzatainak idempotens-szétválasztó homomorf képeit, és ezek reguláris részfélcsoportjait. Bebizonyítottuk, hogy minden E-tömör lokálisan inverz félcsoport beágyazható teljesen egyszerű félcsoport inverz félcsoporttal vett lambda-szemidirekt szorzatába. Algebrai és kombinatorikai jellegű feltételeket adtunk arra, hogy egy lokálisan véges varietás típushalmaza nem tartalmaz 1-es típust, illetve 1-es és 2-es típust. Dichotómiatételt bizonyítottunk polinom-egyenletrendszerek megoldhatóságára olyan algebrák felett, melyek „kizárják” az 1-es típust.
Results in English
The results of the project belong to three areas: universal algebra, semigroup theory and complexity theory. Most of the research was carried out in international cooperation. We proved that in a wide class of algebras, the finite algebras that generate residually small varieties are determined by their c-ary compatible relations where c is a constant that depends only on a parameter of the class and on the size of the underlying set. We described the minimal clones with at most 4 majority operations, and those binary operations generating a minimal clone which are “almost associative”. We generalized the finite basis theorem of Willard to quasivarieties, and proved a conjecture of Pigozzi regarding the finite axiomatizability of relative congruence-modular quasivarieties in a special case. We characterized the idempotent separating homomorphic images of semidirect products of bands by groups, and their regular subsemigroups. We proved that each E-solid locally inverse semigroup is embeddable in a lambda-semidirect product of a completely simple semigroup by an inverse semigroup. We gave algebraic and combinatorial characterizations of the locally finite varieties omitting type 1 and of those omitting types 1 and 2. We proved a dichotomy theorem for the solvability problem of systems of polynomial equations over certain finite algebras.
Full text http://real.mtak.hu/1870/
Decision
Yes





 

List of publications

  
Szendrei MB: Problems on finite regular semigroups, Proc. Conf. ''International Symposium on Semigroups and Applications'' (eds. Rajan AR, John L); 37-45, 2007
Szendrei MB, Szittyai I: E-solid locally inverse semigroups, kézirat, 2010
Berman JD, Kearnes KA, Szendrei Á: Free spectra of intermediate growth, kézirat, 2010
Larose B, Zádori L: Bounded width problems and algebras, Algebra Universalis 56: 439-466, 2007
Maróti M: The existence of a near-unanimity term in a finite algebra is decidable, J. Symbolic Logic, 2009
Szendrei MB: Factorizability in certain classes over inverse semigroups, Proc. Conf. ''Semigroups and Formal Languages'' (eds. André JM, Branco MJ, Fernandes VH, Fountain J, Gomes GMS, Meakin JC); 266--277, 2007
Waldhauser T: Minimal clones with few majority operations, Acta Sci. Math. 73: 471-486, 2007
Maróti M, McKenzie R: Existence theorems for weakly symmetric operations, Algebra Universalis 59: 463-489, 2008
Hartmann M: Embedding into almost factorizable orthodox semigroups, Acta Sci. Math. 73: 71-89, 2007
Dzobiak W, Maróti M, McKenzie R, Nurakunov A: The weak extension property and finite axiomatizability for quasivarieties, Fundamenta Mathematicae, közlésre benyújtva, 2010
Larose B, Zádori L: Omitting types, bounded width and the ability to count, közlésre benyújtva, 2010
Lehtonen E, Szendrei Á: Equivalence of operations with respect to discriminator clones, Discrete Math., 2009
Dziobiak W, Ježek J, Maróti M: Minimal varieties and quasivarieties of semilattices with one automorphism, Semigroup Forum, 2009
Czédli G, Hartmann M, Schmidt ET: CD-independent subsets in distributive lattices, Publ. Math. Debrecen, 2009
Barto L, Kozik M, Maróti M, McKenzie R, Niven T: Congruence modularity implies cyclic terms for finite algebras, Algebra Universalis, 2009
Liebscher S, Waldhauser T: On associative spectra of binary operations, Acta Sci. Math. (Szeged), 2009
Kearnes KA, Szendrei Á: Clones of parallelogram algebras, közlésre benyújtva, 2010
Lehtonen E , Szendrei Á: Clones with finitely many relative R-classes, kézirat, 2010
Qiu S, Hartmann M, Guo X: Almost factorizable IC quasi-adequate semigroups, Comm. Algebra, közlésre benyújtva, 2010
Barto L, Kozik M, Maróti M, Niven T: CSP dichotomy for special triads, Trans. Amer. Math. Soc., 2009
Carvalho C, Dalmau V, Markovic P, Maróti M: CD(4) has bounded width, Algebra Universalis, 2009
Jezek J, Kepka T, Maróti M: The endomorphism semiring of a semilattice, Semigroup Forum, 2009
Czédli G, Maróti M, Schmidt ET: On the scope of averaging for Frankl's conjecture, közlésre benyújtva, 2010
Czédli G, Maróti M: Two notes on the variety generated by planar modular lattices, Order, 2009
Nesetril J, Siggers M, Zádori L: A combinatorial CSP dichotomy classification conjecture, közlésre benyújtva, 2010
Waldhauser T: On composition-closed classes of Boolean functions, kézirat, 2010
Szendrei MB: E-unitary almost factorizable orthodox semigroups, kézirat, 2010
Hartmann M: Ortodox félcsoportok és szemidirekt szorzatok, SZTE, 2008
Davey BA, Jackson M, Maróti M, McKenzie R: Principal and syntactic congruences in congruence-distributive and congruence-permutable varieties, J. Austral. Math. Soc. 85: 59-74, 2008
Gomes GMS, Szendrei MB: Even covers for left ample semigroups, Semigroup Forum 74: 293-305, 2007
Hartmann M: Almost factorizable orthodox semigroups, Semigroup Forum 74: 106-124, 2007
Kearnes KA, Shaw J, Szendrei Á: Clones of 2-step nilpotent groups, Algebra Universalis 59: 491-512, 2008
Szabó L: On algebras with primitive positive clones, Acta Sci. Math. 73: 463-470, 2007
Waldhauser T: Almost associative operations generating a minimal clone, Discuss. Math. Gen. Algebra Appl. 26: 45-73, 2006
Zádori L: Solvability of systems of polynomial equations over finite algebras, Internat. J. Algebra Comput. 17: 821-835, 2007



Back »