A directed graph (digraph) G can primitively positively construct another digraph H if H is homomorphically equivalent to a first order interpretation of G that only uses primitive positive formulas. In this way, we define the poset of all finite digraphs ordered by primitive positive constructability. This poset, which is the object studied in this dissertation, is important for studying the complexity of constraint satisfaction problems and for studying clones ordered by minion homomorphisms. In this thesis I will introduce the poset and amoung other results I will present the three topmost levels of the poset and I will describe the subposet consisting of digraphs without sources or sinks.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:93075 |
| Date | 16 August 2024 |
| Creators | Starke, Florian |
| Contributors | Bodirsky, Manuel, Dalmau, Victor, Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds