Würzburg, Univ., Diss., 2001. / Erscheinungsjahr an der Haupttitelstelle: 2000. Computerdatei im Fernzugriff.

Würzburg, Univ., Diss., 2001. / Erscheinungsjahr an der Haupttitelstelle: 2000. Computerdatei im Fernzugriff.

München, Univ., Diss., 2002. / Computerdatei im Fernzugriff.

München, Univ., Diss., 2002. / Computerdatei im Fernzugriff.

Würzburg, University, Diss., 2001. / Erscheinungsjahr an der Haupttitelstelle: 2000.

Zugl.: Berlin, Techn. Univ., Diss., 2009

Zugl.: Bochum, Univ., Diss., 2009

Universiẗat, Diss., 2002--München.

Computational complexity theory usually investigates the complexity of sets, i.e., the complexity of partitions into two parts. But often it is more appropriate to represent natural problems by partitions into more than two parts. A particularly interesting class of such problems consists of classification problems for relations. For instance, a binary relation R typically defines a partitioning of the set of all pairs (x,y) into four parts, classifiable according to the cases where R(x,y) and R(y,x) hold, only R(x,y) or only R(y,x) holds or even neither R(x,y) nor R(y,x) is true. By means of concrete classification problems such as Graph Embedding or Entailment (for propositional logic), this thesis systematically develops tools, in shape of the boolean hierarchy of NP-partitions and its refinements, for the qualitative analysis of the complexity of partitions generated by NP-relations. The Boolean hierarchy of NP-partitions is introduced as a generalization of the well-known and well-studied Boolean hierarchy (of sets) over NP. Whereas the latter hierarchy has a very simple structure, the situation is much more complicated for the case of partitions into at least three parts. To get an idea of this hierarchy, alternative descriptions of the partition classes are given in terms of finite, labeled lattices. Based on these characterizations the Embedding Conjecture is established providing the complete information on the structure of the hierarchy. This conjecture is supported by several results. A natural extension of the Boolean hierarchy of NP-partitions emerges from the lattice-characterization of its classes by considering partition classes generated by finite, labeled posets. It turns out that all significant ideas translate from the case of lattices. The induced refined Boolean hierarchy of NP-partitions enables us more accuratly capturing the complexity of certain relations (such as Graph Embedding) and a description of projectively closed partition classes. / Die klassische Komplexitätstheorie untersucht in erster Linie die Komplexität von Mengen, d.h. von Zerlegungen (Partitionen) einer Grundmenge in zwei Teile. Häufig werden aber natürliche Fragestellungen viel angemessener durch Zerlegungen in mehr als zwei Teile abgebildet. Eine besonders interessante Klasse solcher Fragestellungen sind Klassifikationsprobleme für Relationen. Zum Beispiel definiert eine Binärrelation R typischerweise eine Zerlegung der Menge aller Paare (x,y) in vier Teile, klassifizierbar danach, ob R(x,y) und R(y,x), R(x,y) aber nicht R(y,x), nicht R(x,y) aber dafür R(y,x) oder weder R(x,y) noch R(y,x) gilt. Anhand konkreter Klassifikationsprobleme, wie zum Beispiel der Einbettbarkeit von Graphen und der Folgerbarkeit für aussagenlogische Formeln, werden in der Dissertation Instrumente für eine qualitative Analyse der Komplexität von Partitionen, die von NP-Relationen erzeugt werden, in Form der Booleschen Hierarchie der NP-Partitionen und ihrer Erweiterungen systematisch entwickelt. Die Boolesche Hierarchie der NP-Partitionen wird als Verallgemeinerung der bereits bekannten und wohluntersuchten Boolesche Hierarchie über NP eingeführt. Während die letztere Hierarchie eine sehr einfache Struktur aufweist, stellt sich die Boolesche Hierarchie der NP-Partitionen im Falle von Zerlegungen in mindestens 3 Teile als sehr viel komplizierter heraus. Um einen Überblick über diese Hierarchien zu erlangen, werden alternative Beschreibungen der Klassen der Hierarchien mittels endlicher, bewerteter Verbände angegeben. Darauf aufbauend wird die Einbettungsvermutung aufgestellt, die uns die vollständige Information über die Struktur der Hierarchie liefert. Diese Vermutung wird mit verschiedene Resultaten untermauert. Eine Erweiterung der Booleschen Hierarchie der NP-Partitionen ergibt sich auf natürliche Weise aus der Charakterisierung ihrer Klassen durch Verbände. Dazu werden Klassen betrachtet, die von endlichen, bewerteten Halbordnungen erzeugt werden. Es zeigt sich, dass die wesentlichen Konzepte vom Verbandsfall übertragen werden können. Die entstehende Verfeinerung der Booleschen Hierarchie der NP-Partitionen ermöglicht die exaktere Analyse der Komplexität bestimmter Relationen (wie zum Beispiel der Einbettbarkeit von Graphen) und die Beschreibung projektiv abgeschlossener Partitionenklassen.

Hiponimia ni uhusiano wa kifahiwa unaodhihirika baina ya leksimu ya jumla (hipanimu) na mahususi (hiponimu). Kama vile hipanimu mzazi hujumuisha hiponimu baba na mama. Uhusiano huu wa kihiponimia ulidhukuriwa na wanaisimu wa awali kuwa unahusisha leksimu nomino pekee. Hata hivyo, tafiti za hivi punde zinadhihirisha kuwa hiponimia huweza kudhihirika pia miongoni mwa kategoria za vivumishi, vielezi na vitenzi. Ingawa kuna midhihiriko ya hiponimia za vitenzi vya Kiswahili, wataalamu kadha wameelekea kushughulikia hiponimia za nomino na kutotilia maanani vitenzi. Hivyo basi, makala hii imechanganua uhusiano wa kihiponimia unaodhihirika miongoni mwa vitenzi teule vya Kiswahili. Katika kushughulikia suala hili, hipanimu vitenzi 24 kutoka kamusi za Kiswahili zimeteuli¬wa kimakusudi na hiponimu husika kutolewa. Nadharia ya Uchanganuzi Vijenzi kwa mujibu wa Katz na Fodor imezingatiwa katika uchanganuzi wa hiponimia hizi. Katika nadharia hii, sifa bainifu za hiponimu husika huonyeshwa kwa kutumia alama maalum za [+, -]. Data kuhusu hiponimia za vitenzi ilipekuliwa kutoka kamusi za Kiswahili kwa kuzingatia mwelekeo wa kiishara au kisintaksia kwa mujibu wa Hearst, na Snow na wenzake ili kuweza kutambua hipanimu na hiponimu husika katika sentensi. Hiponimia hizi zimechanganuliwa na kuwasilishwa kwa mtindo wa nadharia ya seti. / Hyponymy is a sense relation existing between general lexemes (hypernym) and the specific ones (hyponym). For instance, a hypernym parent includes hyponyms like father and mother. The hyponymy relation was regarded by earlier linguists that it could exist only amongst nouns. However, recent studies indicate that hyponymy can also be manifested in other categories such as adjectives, adverbs and verbs. Though there is hyponymy relation existing amongst Kiswahili verbs, various scho¬lars have tended to focus on nominal hyponymy and disregard verbal hyponymy. Therefore, this article has analyzed the hyponymy relation existing amongst selected Kiswahili verbs. In this regard, 24 verbal hypernyms from Kiswahili dictionaries were purposively sampled and their specific hyponyms indicated. Componential Analysis theory by Katz and Fodor has been used in the analysis of these hyponyms. The theory focuses on distinctive features of specific hyponyms that are normally shown by the use of specific signs [+, -]. The data on verbal hyponymy was observed from the Kiswahili dictionaries by the application of symbolic or syntactic approach propounded by Hearst, and Snow et al in order to identify the hypernyms and specific hyponyms in a sentence. These hyponymy relations are analyzed and presented using the set theory style.