REAL

Algebrák, varietások és algoritmusok = Algebras, varieties and algorithms

B. Szendrei, Mária and Maróti, Miklós and Szendrei, Ágnes and Waldhauser, Tamás and Zádori, László and Zádori, László (2013) Algebrák, varietások és algoritmusok = Algebras, varieties and algorithms. Project Report. OTKA.

[img]
Preview
PDF
77409_ZJ1.pdf

Download (93kB) | Preview

Abstract

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. | 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.

Item Type: Monograph (Project Report)
Uncontrolled Keywords: Matematika
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: Kotegelt Import
Date Deposited: 01 May 2014 06:17
Last Modified: 22 Aug 2014 10:58
URI: http://real.mtak.hu/id/eprint/12494

Actions (login required)

Edit Item Edit Item