Counting and enumerating in first-order team logics

Downloadstatistik des Dokuments (Auswertung nach 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

Zeitraum, für den die Download-Zahlen angezeigt werden:

Jahr: 
Monat: 

Summe der Downloads: 63




Kleine Vorschau
Zusammenfassung: 
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.
Lizenzbestimmungen: CC BY 3.0 DE
Publikationstyp: DoctoralThesis
Publikationsstatus: publishedVersion
Erstveröffentlichung: 2024
Die Publikation erscheint in Sammlung(en):Fakultät für Elektrotechnik und Informatik
Dissertationen

Verteilung der Downloads über den gewählten Zeitraum:

Herkunft der Downloads nach Ländern:

Pos. Land Downloads
Anzahl Proz.
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%
    andere 3 4,76%

Weitere Download-Zahlen und Ranglisten:


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.