Algebrák, varietások és algoritmusok  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
77409
típus K
Vezető kutató B. Szendrei Mária
magyar cím Algebrák, varietások és algoritmusok
Angol cím Algebras, varieties and algorithms
magyar kulcsszavak véges algebra, félcsoport, csoport, klón, varietás
angol kulcsszavak finite algebra, semigroup, group, clone, variety
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)100 %
Ortelius tudományág: Algebra
zsűri Matematika–Számítástudomány
Kutatóhely Bolyai Intézet (Szegedi Tudományegyetem)
résztvevők B. Szendrei Mária
Maróti Miklós
Szendrei Ágnes
Waldhauser Tamás
Zádori László
Zádori László
Zádori László
projekt kezdete 2009-04-01
projekt vége 2013-03-31
aktuális összeg (MFt) 9.600
FTE (kutatóév egyenérték) 6.30
állapot lezárult projekt
magyar összefoglaló
A pályázat célja új összefüggések feltárása a matematika egy fontos ágában, az algebrában. A tanulmányozandó kérdések az univerzális algebra és a félcsoportelmélet területére esnek. A kutatási témák közös vonása, hogy a klasszikus algebrai és az univerzális algebrai eszköztár mellett kombinatorikai módszerek is szerephez jutnak. A vizsgálandó problémák közül többet algoritmikus kérdések motiválnak, illetve több kapcsolódik ilyen kérdésekhez. Az eredmények alkalmazása elsősorban a matematikán belül, illetve a számítástudományban várható.
A következő témákban tervezünk kutatást:
(1) Véges Mal'cev-algebrák klasszifikációja
(2) Két kétváltozós művelettel rendelkező turnamentek azonosságbázisa
(3) Reguláris félcsoportok fedői
(4) Csoportklónok
(6) Minimális klónok
(7) Algebrák és varietások kompatibilis relációi és műveletei
(8) Klónhálók definiálhatósága
(9) Dualitás
A kutatás részben nemzetközi együttműködés keretében történik, többek között USA-beli, kanadai, portugál, osztrák, német, cseh és szerb algebristákkal. A pályázat keretében elért eredményeket nemzetközi matematikai folyóiratokban és/vagy konferenciakiadványokban közöljük.
angol összefoglaló
The aim of the project is to obtain new results in algebra which is an important branch of pure mathematics. The proposed research objectives belong to universal algebra and semigroup theory, and have the common feature that they require a combination of ideas and methods from classical algebra, universal algebra, and combinatorics. Some of the problems are motivated by or related to algorithmic questions, and are expected to be applicable primarily within mathematics and in computer science.
The proposed research focuses on the following topics:
(1) Classification of finite Mal'tsev algebras
(2) The equational base of tournaments with two binary operations
(3) Covers of regular semigroups
(4) Clones of groups
(6) Minimal clones
(7) Compatible relations and operations of algebras and varieties
(8) Definability in the lattice of clones
(9) Duality
Part of the research will be carried out in collaboration with algebraists from abroad—e.g. from the USA, Canada, Portugal, Austria, Germany, the Czech Republic, and Serbia. The results of the project will be published in international mathematical journals and/or conference proceedings.





 

Zárójelentés

 
kutatási eredmények (magyarul)
A pályázat keretében három fő témakörben --- általános algebra és alkalmazásai, 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. Kiterjesztettük Rosenberg teljességi tételét a Slupecki-klón környezetében, általánosítottuk Wiegold dichotómiatételét parallelogramma-algebrákra, és az eddig ismerteknél egyszerűbb jellemzést adtunk a kongruenciamodularitásra. Karakterizáltuk a döntések kvalitatív modellezésére szolgáló hasznossági függvényeket, és eljárást adtunk egyszerűbb függvények kompozíciójaként való előállításukra. Kiterjesztettük a McAlister-Lawson-féle elmélet egyes fedési, illetve beágyazási tételeit a lokálisan inverz félcsoportokra a majdnem faktorizálhatóság általánosításával, illetve a bal és kétoldali megszorításos félcsoportokra a W-szorzatba való beágyazhatóság jellemzésével. A homomorfizmus-problémára vonatkozó dichotómiasejtést bebizonyítottuk két különböző új algebraosztályra. Megmutattuk, hogy egy véges idempotens algebra pontosan akkor örökletesen véges relációbázisú, ha van élkifejezése. Széles algebraosztályok esetén algebrailag jellemeztük az egyenletrendszer-problémák komplexitását. Algebrai eszközökkel bizonyítottuk Valeriote egy sejtését a reflexív irányított gráfok speciális esetére, valamint igazoltuk Stahl Kneser-gráfokra vonatkozó sejtésének speciális esetét.
kutatási eredmények (angolul)
The results of the project belong to three areas: universal algebra and applications, semigroup theory, and complexity theory. Most of the research was carried out in international cooperation. We extended Rosenberg’s completeness theorem in the neighborhood of Slupecki’s clone, we generalized Wiegold’s dichotomy theorem to parallelogram algebras, and we found a characterization for congruence modularity which is simpler than the known criteria. We characterized utility functions which provide a tool for qualitative modelling of decision-making, and gave a procedure to express them as compositions of simpler functions. We extended some of the covering and embedding theorems of the McAlister-Lawson theory for locally inverse semigroups by generalizing almost factorizability, and for left and two-sided restriction semigroups by characterizing embeddability in W-products. We verified the constraint satisfaction problem dichotomy conjecture for two new classes of algebras. We proved that a finite idempotent algebra is inherently finitely related if and only if it has an edge term. We gave an algebraic characterization of the complexity of the problems of systems of equations for broad classes of finite algebras. Based on algebraic methods, we confirmed the Valeriote conjecture for the special case of finite reflexive digraphs, and verified a special case of the Stahl conjecture on Kneser graphs.
döntés eredménye
igen





 

Közleményjegyzék

 
Lehtonen E; Szendrei Á: Clones with finitely many relative R-classes, Algebra Universalis 65: 109-159, 2011
Maróti M: Maltsev on top, benyújtva, 2014
Szendrei Á: Completeness criteria for cognates of Slupecki's clone, kézirat, 2014
Szendrei MB: Almost factorizable locally inverse semigroups, Internat. J. Algebra Comput. 21: 1037-1052, 2011
Behrisch M; Waldhauser T: Minimal clones with many majority operations, Acta Sci. Math. (Szeged) 77: 389-402, 2011
Zádori L: On solvability of systems of polynomial equations, Algebra Universalis 65: 277-283, 2011
Markovic P; Maróti M; McKenzie R: Finitely related clones and algebras with cube-terms, Order 29: 345-359, 2012
Maróti M; Zádori L: Reflexive digraphs with near unanimity polymorphisms, Discrete Mathematics 312: 2316-2328, 2012
Dent T; Kearnes KA; Szendrei Á: An easy test for congruence modularity, Algebra Universalis 67:375-392, 2012
Behrisch M; Couceiro M; Kearnes KA; Lehtonen E; Szendrei Á: Commuting polynomial operations of distributive lattices, Order 29:245-269, 2012
Couceiro M; Lehtonen E; Waldhauser T: Decompositions of functions based on arity gap, Discrete Math. 312: 238-247, 2012
Couceiro M; Lehtonen E; Waldhauser T: The arity gap of order-preserving functions and extensions of pseudo-Boolean functions, Discrete Applied Math. 160: 383-390, 2012
Shattuck M; Waldhauser T: Proofs of some binomial identities using the method of last squares, Fibonacci Quart. 48: 290-297, 2010
Marichal J-L; Mathonet P; Waldhauser T: On signature-based expressions of system reliability, J. Multivariate Anal. 102: 1410-1416, 2011
Couceiro M; Waldhauser T: Axiomatizations and factorizations of Sugeno utility functions, Internat. J. Uncertain. Fuzziness Knowledge-Based Systems 19: 635-658, 2011
Couceiro M; Lehtonen E; Marichal J-L; Waldhauser T: An algorithm for producing median formulas for Boolean functions, Reed Muller Workshop (Tuusula, May 25-26 2011), CD-n megjelent, 2011
Lehtonen E; Szendrei Á: Partial orders induced by quasilinear clones, General Algebra 20 (Proceedings of the Salzburg Workshop 2011 on General Algebra), Verlag Johannes Heyn, Klagenfurt, 51-83, 2012
Kincses J; Makay G; Maróti M; Osztényi J; Zádori L: A special case of the Stahl conjecture, European Journal of Combinatorics 34: 502-511, 2013
Gould, V; Szendrei MB: Proper left restriction semigroups―semidirect products and W-products, Acta Math. Hungar., elfogadva, 2013
Szendrei Á: Rosenberg-type completeness criteria for subclones of Slupecki's clone, 42nd International Symposium on Multiple-Valued Logic (ISMVL 2012, Victoria, BC, Canada), pp. 349-354, 2012
Couceiro M; Lehtonen E; Waldhauser T: On the arity gap of polynomial functions, benyújtva, 2014
Couceiro M; Lehtonen E; Waldhauser T: Additive decomposability of functions over abelian groups, Internat. J. Algebra Comput. 23: 643-662, 2013
Couceiro M; Lehtonen E; Waldhauser T: Parametrized arity gap, Order, online megjelent, 2013
Couceiro M; Lehtonen E; Waldhauser T: A survey on the arity gap, benyújtva, 2014
Couceiro M; Waldhauser T: Pseudo-polynomial functions over finite distributive lattices, Fuzzy Sets and Systems, online megjelent, 2013
Couceiro M; Waldhauser T: Interpolation by polynomial functions of distributive lattices: a generalization of a theorem of R. L. Goodstein, Algebra Universalis 69: 287-299, 2013
Couceiro M; Marichal J-L; Waldhauser T: Locally monotone Boolean and pseudo-Boolean functions, Discrete Applied Mathematics 160: 1651-1660, 2013
Couceiro M; Lehtonen E; Waldhauser T: On equational definability of function classes, benyújtva, 2014
Couceiro M; Dubois D; Prade H; Waldhauser T: Decision-making with Sugeno integrals: DMU vs. MCDM, 20th European Conference on Artificial Intelligence (ECAI 2012, Montpellier), Frontiers in Artificial Intelligence and Applications 242, IOS Press, Amsterdam, pp. 288-293, 2012
Szendrei MB: Embedding of a restriction semigroup into a W-product, Semigroup Forum, elfogadva, 2013
Kearnes KA; Kiss EW; Szendrei Á: Growth rates of finite algebras, kézirat, 2014
Maróti M: Tree on top of Maltsev, kézirat, 2014
Couceiro M; Dubois D; Prade H; Rico A; Waldhauser T: General interpolation by polynomial functions of distributive lattices, 14th Internat. Conf. on Inf. Proc. and Manag. of Uncertain. in Knowledge-Based Systems (IPMU 2012, Catania), Comm. Comp. Inf. Sci. 299, Springer, pp. 347-355, 2012
Horváth E K; Makay G; Pöschel R; Waldhauser T: Invariance groups of finite functions and orbit equivalence of permutation groups, benyújtva, 2014
Haddad L; Schölzel K; Couceiro M; Waldhauser T: A solution to a problem of D. Lau: Complete classification of intervals in the lattice of partial Boolean clones, 43rd International Symposium on Multiple-Valued Logic (ISMVL 2013, Toyama), elfogadva, 2013





 

Projekt eseményei

 
2012-02-14 14:10:49
Vezető kutató váltás
B. Szendrei Mária SAB 81142 sz. projektje 2011.05.31-én zárult, ezért a megbízott vezető kutató megbízatása lejárt.
2011-04-04 08:35:59
Vezető kutató váltás
SAB 81142 pályázat 2010.06.01-től 12 hónapra támogatást nyert.




vissza »