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ó
Starting date
2009-04-01
Closing date
2013-03-31
Funding (in million HUF)
9.600
FTE (full time equivalent)
6.30
state
closed project
Summary in Hungarian
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.
Summary
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.
Final report
Results in Hungarian
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.
Results in English
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.
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
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
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
