Counting and enumerating in first-order team logics

Download statistics - Document (COUNTER):

Müller, Fabian: Counting and enumerating in first-order team logics. Hannover : Gottfried Wilhelm Leibniz Universität, Diss., 2024, v, 87 S., DOI: https://doi.org/10.15488/16831

Selected time period:

year: 
month: 

Sum total of downloads: 63




Thumbnail
Abstract: 
Descriptive complexity theory is the study of the expressibility of computationalproblems in certain logics. Most of the results in this field use (fragments orextensions of) first-order logic or second-order logic to describe decision complexityclasses. For example the complexity class NP can be characterized asthe set of problems that are describable by a dependence logic formula, in shortNP = FO(=(...)). Dependence logic is a certain team logic, where a team logicis an extension of first-order logic by some new atoms, with new semantics, calledteam semantics. Compared to decision complexity where one is interested in theexistence of a solution to an input instance, in counting complexity one is interestedin the number of solutions and in enumeration complexity one wants to computeall solutions. Counting complexity has been less studied in terms of descriptivecomplexity than decision complexity, whereas there are no results for enumerationcomplexity in this field. The latter is because the concept of hardness in theenumeration setting was first introduced rather recently.In this thesis, we characterize counting and enumeration complexity classes withteam logics and compare the results to the corresponding results for decision complexityclasses. To study the framework of hard enumeration a bit more, weinvestigate further team logic based enumeration problems.In the counting setting we characterize the classes #P and #•NP as #P =#FOT and #•NP = #FO(⊥). Furthermore, we establish two team logic basedclasses #FO(⊆) and #FO(=(...)) which seem to have no direct counterpart inclassical counting complexity, but contain problems that are complete under Turingreductions for #P and #•NP, respectively. To show the latter we identify a new#•NP-complete problem with respect to Turing reductions.We show that in the enumeration setting the classes behave very similarlyto the corresponding classes in the decision setting. We translate the resultsP = FO(⊆) and NP = FO(=(...)) to the enumeration setting which results inDelP = DelFO(⊆) and DelNP = DelFO(=(...)). Furthermore, we identify severalDelP and DelNP-complete problems which yield additional characterisationsof DelP and DelNP. For one of the investigated problems we were only able toshow Del+NP membership (and DelNP-hardness), a precise classification remainsopen.
License of this version: CC BY 3.0 DE
Document Type: DoctoralThesis
Publishing status: publishedVersion
Issue Date: 2024
Appears in Collections:Fakultät für Elektrotechnik und Informatik
Dissertationen

distribution of downloads over the selected time period:

downloads by country:

pos. country downloads
total perc.
1 image of flag of Germany Germany 30 47.62%
2 image of flag of United States United States 5 7.94%
3 image of flag of France France 5 7.94%
4 image of flag of Czech Republic Czech Republic 5 7.94%
5 image of flag of Netherlands Netherlands 3 4.76%
6 image of flag of Greece Greece 3 4.76%
7 image of flag of Australia Australia 3 4.76%
8 image of flag of Sweden Sweden 2 3.17%
9 image of flag of Israel Israel 2 3.17%
10 image of flag of United Kingdom United Kingdom 2 3.17%
    other countries 3 4.76%

Further download figures and rankings:


Hinweis

Zur Erhebung der Downloadstatistiken kommen entsprechend dem „COUNTER Code of Practice for e-Resources“ international anerkannte Regeln und Normen zur Anwendung. COUNTER ist eine internationale Non-Profit-Organisation, in der Bibliotheksverbände, Datenbankanbieter und Verlage gemeinsam an Standards zur Erhebung, Speicherung und Verarbeitung von Nutzungsdaten elektronischer Ressourcen arbeiten, welche so Objektivität und Vergleichbarkeit gewährleisten sollen. Es werden hierbei ausschließlich Zugriffe auf die entsprechenden Volltexte ausgewertet, keine Aufrufe der Website an sich.

Search the repository


Browse