Gleichungen in Polymorphismenalgebren unendlicher Strukturen
Identities in polymorphism algebras of infinite structures
Wissenschaftsdisziplinen
Informatik (10%); Mathematik (90%)
Keywords
-
Clone,
Polymorphism,
Oligomorphic Permutation Group,
Algebraic Identity,
Constraint Satisfaction Problem,
Variety Of Algebras
Eine Algebra besteht aus einer Menge und Funktionen auf dieser Menge. Beispiele sind die Menge der ganzen Zahlen mit den Funktionen der Addition und Multiplikation; die Menge der der reellen Zahlen mit der Addition, der Multiplikation, und der Potenzfunktion; oder die Menge bestehend aus zwei Elementen, 0 und 1, mit der Maximumsfunktion. Aufgrund ihrer Allgemeinheit treten Algebren in allen Gebieten der Mathematik auf, und modellieren Situationen, in denen wir es mit Objekten zu tun haben (die den Elementen der Menge entsprechen, auf denen die Algebra lebt), zwischen denen es Interaktionen gibt (die den Funktionen auf den Elementen entsprechen). Theoretisch könnte man jede Algebra, welche in der Mathematik auftritt, getrennt erforschen; dies ist auch für besonders wichtige Algebren der Fall. Das Gebiet der universellen Algebra erforscht nun aber abstrakt den Zusammenhang zwischen den Gleichungen, welche in einer Algebra gelten, und deren Struktur, ohne eine konkrete Algebra zu betrachten. So erfüllt beispielsweise die Algebra auf den ganzen Zahlen mit der Addition die Gleichungen x-x+y=y=y-x+x, was allgemeine strukturelle Konsequenzen hat: jede beliebige Algebra, in der eine ähnliche Gleichung gilt, teilt mit dieser Algebra gewisse strukturelle Eigenschaften. Die Theorie der Gleichungen in endlichen Algebren, zu denen beispielsweise die oben genannte Algebra auf den Elementen 0,1 mit der Maximumsfunktion gehört, wird schon seit den Anfängen der universellen Algebra erforscht, hat aber unlängst grosse Fortschritte erfahren, seit Anwendungen in der theoretischen Informatik entdeckt wurden: es modellieren endliche Algebren nämlich bestimmte Berechnungsprobleme, und wie sich herausgestellt hat, bestimmen die Gleichungen, welche in einer Algebra gelten, die Komplexität des modellierten Berechnungsproblemes. Fast zwanzig Jahre nach dieser Entdeckung wurde schliesslich letztes Jahr klassifiziert, welche Gleichungen implizieren, dass ein Berechnungsproblem effizient gelöst werden kann. In diesem Projekt wollen wir die neuen Methoden von endlichen Algebren auf unendliche Algebren erweitern. Während schon einige sporadische und überraschende Ergebnisse in dieser Richtung für unendliche Algebren erzielt wurden, gibt es, im Unterschied zu endlichen Algebren, noch keine allgemeine Methode, um solche Ergebnisse zu zeigen. Unser Projekt ist einerseits durch die oben genannten Anwendungen in der theoretischen Informatik motiviert, andererseits hat die Erforschung der Struktur von unendlichen Algebren über ihre Gleichungen ihren Wert für sich, da diese natürlich auftreten; siehe die obigen Beispiele. Wir hoffen auch, die endlichen Methoden selbst durch ihre Anwendung in einem breiteren Kontext besser verstehen zu können.
Eine Algebra besteht aus einer Menge und Funktionen auf dieser Menge. Beispiele sind die Menge der ganzen Zahlen mit den Funktionen der Addition und Multiplikation; die Menge der der reellen Zahlen mit der Addition, der Multiplikation, und der Potenzfunktion; oder die Menge bestehend aus zwei Elementen, 0 und 1, mit der Maximumsfunktion. Aufgrund ihrer Allgemeinheit treten Algebren in allen Gebieten der Mathematik auf, und modellieren Situationen, in denen wir es mit Objekten zu tun haben (die den Elementen der Menge entsprechen, auf denen die Algebra lebt), zwischen denen es Interaktionen gibt (die den Funktionen auf den Elementen entsprechen). Theoretisch könnte man jede Algebra, welche in der Mathematik auftritt, getrennt erforschen; dies ist auch für besonders wichtige Algebren der Fall. Das Gebiet der universellen Algebra erforscht nun aber abstrakt den Zusammenhang zwischen den Gleichungen, welche in einer Algebra gelten, und deren Struktur, ohne eine konkrete Algebra zu betrachten. So erfüllt beispielsweise die Algebra auf den ganzen Zahlen mit der Addition die Gleichungen x-x+y=y=y-x+x, was allgemeine strukturelle Konsequenzen hat: jede beliebige Algebra, in der eine ähnliche Gleichung gilt, teilt mit dieser Algebra gewisse strukturelle Eigenschaften. Die Theorie der Gleichungen in endlichen Algebren, zu denen beispielsweise die oben genannte Algebra auf den Elementen 0,1 mit der Maximumsfunktion gehört, wird schon seit den Anfängen der universellen Algebra erforscht, hat aber unlängst grosse Fortschritte erfahren, seit Anwendungen in der theoretischen Informatik entdeckt wurden: es modellieren endliche Algebren nämlich bestimmte Berechnungsprobleme, und wie sich herausgestellt hat, bestimmen die Gleichungen, welche in einer Algebra gelten, die Komplexität des modellierten Berechnungsproblemes. Fast zwanzig Jahre nach dieser Entdeckung wurde schliesslich 2017 klassifiziert, welche Gleichungen implizieren, dass ein Berechnungsproblem effizient gelöst werden kann. In diesem Projekt konnten wir einige der neuen Methoden von endlichen Algebren auf unendliche Algebren erweitern.
- Technische Universität Wien - 100%
- Manuel Bodirsky, Technische Universität Dresden - Deutschland
- Andrei Bulatov, Simon Fraser University - Kanada
- Marcin Kozik, Jagellonian University - Polen
- Libor Barto, Charles University Prague - Tschechien
- Keith Kearnes, University of Colorado Boulder - Vereinigte Staaten von Amerika
Research Output
- 21 Zitationen
- 28 Publikationen
- 5 Wissenschaftliche Auszeichnungen
- 2 Weitere Förderungen
-
2021
Titel CORES OVER RAMSEY STRUCTURES DOI 10.1017/jsl.2021.6 Typ Journal Article Autor Mottet A Journal The Journal of Symbolic Logic -
2023
Titel Corrigendum to "-categorical structures avoiding height 1 identities" DOI 10.1090/tran/8501 Typ Journal Article Autor Bodirsky M Journal Transactions of the American Mathematical Society -
2021
Titel Galois covers of ℙ1 and number fields with large class groups DOI 10.1142/s1793042122500646 Typ Journal Article Autor Gillibert J Journal International Journal of Number Theory -
2023
Titel Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing DOI 10.1109/lics56636.2023.10175732 Typ Conference Proceeding Abstract Autor Barto L Seiten 1-13 -
2023
Titel Polish topologies on endomorphism monoids of relational structures DOI 10.1016/j.aim.2023.109214 Typ Journal Article Autor Elliott L Journal Advances in Mathematics Seiten 109214 Link Publikation -
2020
Titel ? \omega -categorical structures avoiding height 1 identities DOI 10.1090/tran/8179 Typ Journal Article Autor Bodirsky M Journal Transactions of the American Mathematical Society Seiten 327-350 Link Publikation -
2022
Titel The VC-dimension of axis-parallel boxes on the Torus DOI 10.1016/j.jco.2021.101600 Typ Journal Article Autor Gillibert P Journal Journal of Complexity Seiten 101600 Link Publikation -
2022
Titel When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems DOI 10.1137/20m1383471 Typ Journal Article Autor Gillibert P Journal SIAM Journal on Computing Seiten 175-213 Link Publikation -
2022
Titel Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep DOI 10.1109/ismvl52857.2022.00019 Typ Conference Proceeding Abstract Autor Pinsker M Seiten 80-87 Link Publikation -
2022
Titel Smooth approximations and CSPs over finitely bounded homogeneous structures DOI 10.1145/3531130.3533353 Typ Conference Proceeding Abstract Autor Mottet A Seiten 1-13 Link Publikation -
2023
Titel ON THE ZARISKI TOPOLOGY ON ENDOMORPHISM MONOIDS OF OMEGA-CATEGORICAL STRUCTURES DOI 10.1017/jsl.2023.81 Typ Journal Article Autor Pinsker M Journal The Journal of Symbolic Logic -
0
DOI 10.1145/3531130 Typ Other -
2020
Titel When symmetries are not enough: a hierarchy of hard Constraint Satisfaction Problems DOI 10.48550/arxiv.2002.07054 Typ Preprint Autor Gillibert P -
2020
Titel Cores over Ramsey structures DOI 10.48550/arxiv.2004.05936 Typ Other Autor Mottet A -
2020
Titel The VC-Dimension of Axis-Parallel Boxes on the Torus DOI 10.48550/arxiv.2004.13861 Typ Journal Article Autor Gillibert Pierre Journal arXiv e-prints -
2020
Titel Smooth approximations and CSPs over finitely bounded homogeneous structures DOI 10.48550/arxiv.2011.03978 Typ Preprint Autor Mottet A -
2021
Titel When symmetries are enough: collapsing the bounded width hierarchy for infinite-domain CSPs DOI 10.48550/arxiv.2102.07531 Typ Preprint Autor Mottet A -
2022
Titel Polish topologies on endomorphism monoids of relational structures DOI 10.48550/arxiv.2203.11577 Typ Preprint Autor Elliott L -
2022
Titel Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep DOI 10.48550/arxiv.2203.17182 Typ Preprint Autor Pinsker M -
2023
Titel AN ORDER OUT OF NOWHERE: A NEW ALGORITHM FOR INFINITE-DOMAIN CSPS Typ Other Autor Mottet -
2020
Titel Cores over Ramsey structures Typ Other Autor Mottet -
2021
Titel Smooth approximations and relational width collapses Typ Other Autor Mottet -
2020
Titel ω-Categorical structures avoiding height 1 identities Typ Other Autor Bodirsky -
2020
Titel Smooth approximations and CSPS over finitely bounded homogeneous structures Typ Other Autor Mottet -
2023
Titel An order out of nowhere: a new algorithm for infinite-domain CSPs DOI 10.48550/arxiv.2301.12977 Typ Preprint Autor Mottet A -
2023
Titel Submaximal clones over a three-element set up to minor-equivalence DOI 10.48550/arxiv.2304.12807 Typ Preprint Autor Vucaj A -
2023
Titel The semigroup of increasing functions on the rational numbers has a unique Polish topology DOI 10.48550/arxiv.2305.04921 Typ Preprint Autor Pinsker M -
2023
Titel On the Zariski topology on endomorphism monoids of omega-categorical structures DOI 10.48550/arxiv.2308.09466 Typ Preprint Autor Pinsker M
-
2022
Titel Plenary talk at the IEEE International Symposium on Multiple-Valued Logic 2022 Typ Personally asked as a key note speaker to a conference Bekanntheitsgrad Continental/International -
2021
Titel Plenary talk at the 100th Arbeitstagung Allgemeine Algebra Typ Personally asked as a key note speaker to a conference Bekanntheitsgrad Continental/International -
2023
Titel Plenary talk at the Algebra Week 2023 Typ Personally asked as a key note speaker to a conference Bekanntheitsgrad Continental/International -
2019
Titel Two invited plenary talks at the 57th Summer School on General Algebra and Ordered Sets in Karolinka, Czech Republic. Typ Personally asked as a key note speaker to a conference Bekanntheitsgrad Continental/International -
2023
Titel Distinguished paper award Typ Poster/abstract prize Bekanntheitsgrad Continental/International
-
2023
Titel ERC Synergy Grant Typ Research grant (including intramural programme) Förderbeginn 2023 Geldgeber European Research Council (ERC) -
2022
Titel WEAVE Typ Research grant (including intramural programme) Förderbeginn 2022 Geldgeber Austrian Science Fund (FWF)