Frankfurt (Main), University, Diss., 2008. / Erscheinungsjahr an der Haupttitelstelle: 2007.

Techn. University, Diss., 2004--Darmstadt.

Stuttgart, Univ., Diss., 2005.

Starfree regular languages can be build up from alphabet letters by using only Boolean operations and concatenation. The complexity of these languages can be measured with the so-called dot-depth. This measure leads to concatenation hierarchies like the dot-depth hierarchy (DDH) and the closely related Straubing-Thérien hierarchy (STH). The question whether the single levels of these hierarchies are decidable is still open and is known as the dot-depth problem. In this thesis we prove/reprove the decidability of some lower levels of both hierarchies. More precisely, we characterize these levels in terms of patterns in finite automata (subgraphs in the transition graph) that are not allowed. Therefore, such characterizations are called forbidden-pattern characterizations. The main results of the thesis are as follows: forbidden-pattern characterization for level 3/2 of the DDH (this implies the decidability of this level) decidability of the Boolean hierarchy over level 1/2 of the DDH definition of decidable hierarchies having close relations to the DDH and STH Moreover, we prove/reprove the decidability of the levels 1/2 and 3/2 of both hierarchies in terms of forbidden-pattern characterizations. We show the decidability of the Boolean hierarchies over level 1/2 of the DDH and over level 1/2 of the STH. A technique which uses word extensions plays the central role in the proofs of these results. With this technique it is possible to treat the levels 1/2 and 3/2 of both hierarchies in a uniform way. Furthermore, it can be used to prove the decidability of the mentioned Boolean hierarchies. Among other things we provide a combinatorial tool that allows to partition words of arbitrary length into factors of bounded length such that every second factor u leads to a loop with label u in a given finite automaton. / Sternfreie reguläre Sprachen können aus Buchstaben unter Verwendung Boolescher Operationen und Konkatenation aufgebaut werden. Die Komplexität solcher Sprachen lässt sich durch die sogenannte "Dot-Depth" messen. Dieses Maß führt zu Konkatenationshierarchien wie der Dot-Depth-Hierachie (DDH) und der Straubing-Thérien-Hierarchie (STH). Die Frage nach der Entscheidbarkeit der einzelnen Stufen dieser Hierarchien ist als (immer noch offenes) Dot-Depth-Problem bekannt. In dieser Arbeit beweisen wir die Entscheidbarkeit einiger unterer Stufen beider Hierarchien. Genauer gesagt charakterisieren wir diese Stufen durch das Verbot von bestimmten Mustern in endlichen Automaten. Solche Charakterisierungen werden Verbotsmustercharakterisierungen genannt. Die Hauptresultate der Arbeit lassen sich wie folgt zusammenfassen: Verbotsmustercharakterisierung der Stufe 3/2 der DDH (dies hat die Entscheidbarkeit dieser Stufe zur Folge) Entscheidbarkeit der Booleschen Hierarchie über der Stufe 1/2 der DDH Definition von entscheidbaren Hierarchien mit engen Verbindungen zur DDH und STH Darüber hinaus beweisen wir die Entscheidbarkeit der Stufen 1/2 und 3/2 beider Hierarchien (wieder mittels Verbotsmustercharakterisierungen) und die der Booleschen Hierarchien über den Stufen 1/2 der DDH bzw. STH. Dabei stützen sich die Beweise größtenteils auf eine Technik, die von Eigenschaften bestimmter Worterweiterungen Gebrauch macht. Diese Technik erlaubt eine einheitliche Vorgehensweise bei der Untersuchung der Stufen 1/2 und 3/2 beider Hierarchien. Außerdem wird sie in den Beweisen der Entscheidbarkeit der genannten Booleschen Hierarchien verwendet. Unter anderem wird ein kombinatorisches Hilfsmittel zur Verfügung gestellt, das es erlaubt, Wörter beliebiger Länge in Faktoren beschränkter Länge zu zerlegen, so dass jeder zweite Faktor u zu einer u-Schleife in einem gegebenen endlichen Automaten führt.

Stuttgart, Univ., Habil.-Schr., 2003.

Wir schlagen eine praxisorientierte Explikation der philosophischen Position des Mathematischen Pluralismus vor. Dieser Position zufolge existieren mehr als ein legitimes mathematisches System. Wir interpretieren 'legitim' als 'geeignet zur Realisierung wissenschaftlicher Ziele' und wenden die resultierende pluralistische Position auf die Mathematische Ökonomie an. Wir präsentieren ein begriffliches Rahmenwerk, in dem pluralistische Thesen formuliert und evaluiert werden können, stellen ein informelles System der Konstruktiven Mathematik als Alternative zur Klassischen Mathematik vor, und zeigen, dass verschiedene ökonomische Theoreme nicht konstruktiv beweisbar sind. Auf dieser Basis argumentieren wir, dass Pluralismus relativ zu Zielen mit Bezug zu Erklärung und Simplizität in der Ökonomie vorliegt. / We propose a practice-oriented explication of the philosophical position known as mathematical pluralism. According to this position there exist more than one legitimate mathematical system. We interpret 'legitimate' as 'suitable for realizing scientific goals' and apply the resultant pluralist position to mathematical economics. We present a conceptual framework within which pluralist theses can be formulated and evaluated, introduce an informal system of constructive mathematics as an alternative to classical mathematics, and point out that central theorems of economic equilibrium theory are not constructively provable. On this basis, we argue that pluralism obtains with respect to goals related to explanation and simplicity in economics.