Restarting automata with restricted utilization of auxiliary symbols

The restarting automaton is a restricted model of computation that was introduced by Jancar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyze sentences of natural languages. The most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.

Mythen und Mythenbildung in Kunst und Werbung

Aufgrund der breiten aktuellen Verwendung des Mythen-Begriffs in Kunst und Werbung, aber darüber hinaus auch in nahezu allen Bereichen gesellschaftlichen Lebens und vor allem in der Philosophie ergibt sich die Notwendigkeit, einen erweiterten Mythos-Begriff über das Historisch-Authentische hinaus zu verfolgen. Ausgehend von einer strukturalen Annäherung an den Mythos-Begriff im Sinne des von Roland Barthes vorgeschlagenen sekundären semiologischen Systems, d.h. einer semiologischen Sinnverschiebung zur Schaffung einer neuen – mythischen – Bedeutung, fordert diese neue Bedeutung eine Analyse, eine Mythenanalyse heraus. Dies ist deshalb so entscheidend, weil eben diese neue Bedeutung ihr mythisches Profil im Sinne von Hans Blumenberg durch forcierte Bedeutsamkeit für Individuen oder für bestimmte gesellschaftliche Gruppierungen unterlegt, z.B. durch bewusst intensive Wiederholung eines Themas oder durch unerwartete Koinzidenzen von Ereignissen oder durch Steigerung bzw. Depotenzierung von Fakten. Der erweiterte Mythen-Begriff verlangt nach einer Strukturierung und führt dabei zu unterschiedlichen Mythen-Ansätzen: zum Ursprungsstoff des authentischen Mythos und darauf basierender Geisteslage, zum Erkennen eines reflektierten Mythos, wenn es um das Verhältnis Mythos/Aufklärung geht, zum Zeitgeist-Mythos mit seinen umfangreichen Ausprägungen ideologischer, affirmativer und kritischer Art oder zu Alltagsmythen, die sich auf Persönlichkeitskulte und Sachverherrlichungen beziehen. Gerade der letztere Typus ist das Terrain der Werbung, die über den Gebrauchswert eines Produktes hinaus Wert steigernde Tauschwerte durch symbolische Zusatzattribute erarbeiten möchte. Hierbei können Markenmythen unterschiedlichster Prägung entstehen, denen wir täglich im Fernsehen oder im Supermarkt begegnen. Die Manifestation des Mythos in der Kunst ist einerseits eine unendliche Transformationsgeschichte mythischer Substanzen und andererseits ein überhöhender Bezug auf Zeitgeisterscheinungen, etwa bei dem Mythos des Künstlers selbst oder der durch ihn vorgenommenen „Verklärung des Gewöhnlichen“. Die Transformationsprozesse können u.a . prototypisch an zwei Beispielketten erläutert werden, die für den Kunst/Werbung-Komplex besonders interessant sind, weil ihr Charakter sich in einem Fall für die Werbung als äußerst Erfolg versprechend erwiesen hat und weil sich im zweiten Fall geradezu das Gegenteil abzeichnet: Zum einen ist es die Mythengestalt der Nymphe, jene jugendliche, erotisch-verführerische Frauengestalt, die über ihre antiken Wurzeln als Sinnbild der Lebensfreude und Fruchtbarkeit hinaus in und nach der Renaissance ihre Eignung als Verbildlichung der Wiederzulassung des Weiblichen in der Kunst beweist und schließlich der Instrumen-talisierung der Werbung dient. Im anderen Fall ist es die Geschichte der Medusa, die man idealtypisch als die andere Seite der Nympha bezeichnen kann. Hier hat Kunst Auf-klärungsarbeit geleistet, vor allem durch die Verschiebung des medusischen Schreckens von ihr weg zu einer allgemein-medusischen Realität, deren neue Träger nicht nur den Schrecken, sondern zugleich ihre Beteiligung an der Schaffung dieses Schreckens auf sich nehmen. Mythosanalyse ist erforderlich, um die Stellungnahmen der Künstler über alle Epochen hinweg und dabei vor allem diese Transformationsprozesse zu erkennen und im Sinne von Ent- oder Remythologisierung einzuordnen. Die hierarchische Zuordnung der dabei erkannten Bedeutungen kann zu einem Grundbestandteil einer praktischen Philosophie werden, wenn sie einen Diskurs durchläuft, der sich an Jürgen Habermas’ Aspekt der Richtigkeit für kommunikatives Handeln unter dem Gesichtspunkt der Toleranz orientiert. Dabei ist nicht nur zu beachten, dass eine verstärkte Mythenbildung in der Kunst zu einem erweiterten Mythen-begriff und damit zu dem erweiterten, heute dominierenden Kunstbegriff postmoderner Prägung geführt hat, sondern dass innerhalb des aktuellen Mythenpakets sich die Darstellungen von Zeitgeist- und Alltagsmythen zu Lasten des authentischen und des reflektierten Mythos entwickelt haben, wobei zusätzlich werbliche Markenmythen ihre Entstehung auf Verfahrensvorbildern der Kunst basieren. Die ökonomische Rationalität der aktuellen Gesellschaft hat die Mythenbildung keines-wegs abgebaut, sie hat sie im Gegenteil gefördert. Der neuerliche Mythenbedarf wurde stimuliert durch die Sinnentleerung der zweckrationalisierten Welt, die Ersatzbedarf anmeldete. Ihre Ordnungsprinzipien durchdringen nicht nur ihre Paradedisziplin, die Ökonomie, sondern Politik und Staat, Wissenschaft und Kunst. Das Umschlagen der Aufklärung wird nur zu vermeiden sein, wenn wir uns Schritt für Schritt durch Mythenanalyse unserer Unmündigkeit entledigen.

On Vessiot's Theory of Partial Differential Equations

The object of research presented here is Vessiot's theory of partial differential equations: for a given differential equation one constructs a distribution both tangential to the differential equation and contained within the contact distribution of the jet bundle. Then within it, one seeks n-dimensional subdistributions which are transversal to the base manifold, the integral distributions. These consist of integral elements, and these again shall be adapted so that they make a subdistribution which closes under the Lie-bracket. This then is called a flat Vessiot connection. Solutions to the differential equation may be regarded as integral manifolds of these distributions. In the first part of the thesis, I give a survey of the present state of the formal theory of partial differential equations: one regards differential equations as fibred submanifolds in a suitable jet bundle and considers formal integrability and the stronger notion of involutivity of differential equations for analyzing their solvability. An arbitrary system may (locally) be represented in reduced Cartan normal form. This leads to a natural description of its geometric symbol. The Vessiot distribution now can be split into the direct sum of the symbol and a horizontal complement (which is not unique). The n-dimensional subdistributions which close under the Lie bracket and are transversal to the base manifold are the sought tangential approximations for the solutions of the differential equation. It is now possible to show their existence by analyzing the structure equations. Vessiot's theory is now based on a rigorous foundation. Furthermore, the relation between Vessiot's approach and the crucial notions of the formal theory (like formal integrability and involutivity of differential equations) is clarified. The possible obstructions to involution of a differential equation are deduced explicitly. In the second part of the thesis it is shown that Vessiot's approach for the construction of the wanted distributions step by step succeeds if, and only if, the given system is involutive. Firstly, an existence theorem for integral distributions is proven. Then an existence theorem for flat Vessiot connections is shown. The differential-geometric structure of the basic systems is analyzed and simplified, as compared to those of other approaches, in particular the structure equations which are considered for the proofs of the existence theorems: here, they are a set of linear equations and an involutive system of differential equations. The definition of integral elements given here links Vessiot theory and the dual Cartan-Kähler theory of exterior systems. The analysis of the structure equations not only yields theoretical insight but also produces an algorithm which can be used to derive the coefficients of the vector fields, which span the integral distributions, explicitly. Therefore implementing the algorithm in the computer algebra system MuPAD now is possible.

Identität der Identität und Differenz von Raum und Zeit bei Schelling mit Blick auf die Relativitäts- und Quantentheorie

In genannter Schrift soll versucht werden, einen aus der Kantschen und Fichteschen Erkenntnistheorie erfolgenden allgemeinen Zusammenhang herzustellen zwischen dem kategorialen Denken hinsichtlich Denken und Anschauen und dem Problem von Raum und Zeit, wie es sich mit der Entwicklung der modernen Physik durch die Relativitäts- und Quantentheorie deutlich aufdrängt. Es wird gezeigt, dass F.W.J. Schelling grundlegende Lösungsansätze hierzu bereitstellt, welche auf dem Gebiet der Logik, der Epistomologie und Naturphilosophie in der Nachfolge von Kant, Fichte und Spinoza stattfinden, jedoch weit über seine Zeit hinausreichen. Diese Ansätze werden von Schelling selbst unter den Begriff einer „Identität der Identität und Differenz“ gesetzt. In der genannten Dissertation sollen Denkbewegungen dargestellt werden, die eine Anbindung der Schellingschen Naturphilosophie an die sich mit den genannten unterschiedlichen Theorien bzw. deren problematischer Vereinheitlichung beschäftigende Physik zu erreichen versuchen. Der formelle Aufbau der Arbeit gehorcht der inhaltlichen Struktur dieser Anbindungsbemühung, insofern unterstellt wird, dass diese rein nur aus einem dialektischen Denken (sowohl in der Erkenntnistheorie, als auch Naturphilosophie) heraus überhaupt erreicht werden kann. So werden sowohl die Tätigkeiten des Verstandes als die des Anschauens in ihrem Zusammenspiel, wie aber auch die Verstandes- und Anschauungstätigkeiten an sich selbst betrachtet, dialektisch vermittelt dargestellt, was innerhalb der formellen Deduktion der Kantschen Kategorien und der korrespondierenden Anschauungsformen selbst durchgeführt wird. Schellings Intention seines späteren Denkens, die philosophischen Probleme auf die Geschichtlichkeit, die Freiheit und den Erfahrungsbezug des Menschen zu beziehen, wird nicht als Gegenposition zu den frühen Ansätze der Logik und Transzendentalphilosophie gedeutet, sondern selbst als Endpunkt einer dialektischen Entwicklung des Schellingschen Denkens gefasst. Dies ergibt folgenden formellen Aufbau der Arbeit: Zunächst wird in einem einleitenden Abschnitt über die Aufgabe der Philosophie selbst und ihrer Darstellbarkeit im Zusammenhang mit der Hegel-Schelling-Kontroverse gearbeitet, um Schelling als adäquaten Bezugspunkt für unsere moderne Diskussion auf der methodischen und sprachlichen Ebene einzuführen. Im Hauptteil werden die wesentlichen Momente der für Schelling wichtigen Transzendentalphilosophie der Jahrhundertwende dargestellt, um diese dann an den späteren phänomenologisch-epistemologischen Ansätzen zu spiegeln. Von der theoretischen Seite kommend werden die Hauptmomente der praktischen Philosophie Schellings aufgezeigt, um dann den Menschen in einem dritten Schritt Symbol der Ununterschiedenheit von logischen und freien Tätigkeiten bzw. von Leib und Seele zu deuten. Diese Resultate bleiben zunächst einmal liegen, um in dem zweiten Hauptabschnitt auf grundlegende naturphilosophische Voraussetzungen und Resultate derjenigen Physik einzugehen, welche die prinzipiellen Verständnisschwierigkeiten der Physik des frühen 20. Jahrhundert in die heutige kosmologische und atomistische Diskussion mitbringt. Der dritte Hauptabschnitt stellt den Versuch dar, Schellings Naturphilosophie an symptomatische Anschauungen der Physik heranzuführen, um ihn als zeitgenössischen Kritiker einzuführen, wie aber auch als einen, der bestimmte moderne naturwissenschaftliche bzw. physikalische Resultate im Besonderen vorwegzunehmen vermochte. Die Einführung seiner Philosophie in aktuelle naturphilosophische Diskussion wird als unabdingbare Voraussetzung zu einem zukünftigen Verständnis des Natur, des Kosmos´ und des Menschen gefordert.

The Pursuit of Alternatives

Stories of peoples’ struggles across the globe are testaments to their determination to resist exploitation and injustice, and to imagine and construct their own narratives of economic and political difference. These stories of emancipatory moments demonstrate that something radically different in terms of dominant socio-economic relations and mental conceptions of the world may arise out of and beyond capitalism. The Pursuit of Alternatives: Stories of Peoples’ Economic and Political Struggles Around the World presents a fresh and new perspective on how the ‘process of becoming’ alternatives might take place based on peoples’ lived experiences. The chapters here, by labour activists and academics, explore how various forms of peoples’ economic and political initiatives and struggles in six countries – Brazil, Canada, Colombia, Nigeria, the Philippines, and South Korea – might become ‘actually existing’ spaces and moments for the development of critical consciousness and transformative capacities which are both central in challenging the dominant social, economic and political relations. The stories in this book bring to light today’s language of peoples’ struggles; what inspires people to create their own emancipatory moments and spaces for transformative self-change. While this book does not aim to propose an alternative to capitalism per se, it makes a stimulating contribution to the continuing debate on what alternatives to capitalist relations and arrangements might look like by grounding these alternatives in the everyday lives and struggles of workers, women, aboriginal peoples, the unemployed, and the poor.

Capturing Emergent Semantics from Social Annotation Systems

The ongoing growth of the World Wide Web, catalyzed by the increasing possibility of ubiquitous access via a variety of devices, continues to strengthen its role as our prevalent information and commmunication medium. However, although tools like search engines facilitate retrieval, the task of finally making sense of Web content is still often left to human interpretation. The vision of supporting both humans and machines in such knowledge-based activities led to the development of different systems which allow to structure Web resources by metadata annotations. Interestingly, two major approaches which gained a considerable amount of attention are addressing the problem from nearly opposite directions: On the one hand, the idea of the Semantic Web suggests to formalize the knowledge within a particular domain by means of the "top-down" approach of defining ontologies. On the other hand, Social Annotation Systems as part of the so-called Web 2.0 movement implement a "bottom-up" style of categorization using arbitrary keywords. Experience as well as research in the characteristics of both systems has shown that their strengths and weaknesses seem to be inverse: While Social Annotation suffers from problems like, e. g., ambiguity or lack or precision, ontologies were especially designed to eliminate those. On the contrary, the latter suffer from a knowledge acquisition bottleneck, which is successfully overcome by the large user populations of Social Annotation Systems. Instead of being regarded as competing paradigms, the obvious potential synergies from a combination of both motivated approaches to "bridge the gap" between them. These were fostered by the evidence of emergent semantics, i. e., the self-organized evolution of implicit conceptual structures, within Social Annotation data. While several techniques to exploit the emergent patterns were proposed, a systematic analysis - especially regarding paradigms from the field of ontology learning - is still largely missing. This also includes a deeper understanding of the circumstances which affect the evolution processes. This work aims to address this gap by providing an in-depth study of methods and influencing factors to capture emergent semantics from Social Annotation Systems. We focus hereby on the acquisition of lexical semantics from the underlying networks of keywords, users and resources. Structured along different ontology learning tasks, we use a methodology of semantic grounding to characterize and evaluate the semantic relations captured by different methods. In all cases, our studies are based on datasets from several Social Annotation Systems. Specifically, we first analyze semantic relatedness among keywords, and identify measures which detect different notions of relatedness. These constitute the input of concept learning algorithms, which focus then on the discovery of synonymous and ambiguous keywords. Hereby, we assess the usefulness of various clustering techniques. As a prerequisite to induce hierarchical relationships, our next step is to study measures which quantify the level of generality of a particular keyword. We find that comparatively simple measures can approximate the generality information encoded in reference taxonomies. These insights are used to inform the final task, namely the creation of concept hierarchies. For this purpose, generality-based algorithms exhibit advantages compared to clustering approaches. In order to complement the identification of suitable methods to capture semantic structures, we analyze as a next step several factors which influence their emergence. Empirical evidence is provided that the amount of available data plays a crucial role for determining keyword meanings. From a different perspective, we examine pragmatic aspects by considering different annotation patterns among users. Based on a broad distinction between "categorizers" and "describers", we find that the latter produce more accurate results. This suggests a causal link between pragmatic and semantic aspects of keyword annotation. As a special kind of usage pattern, we then have a look at system abuse and spam. While observing a mixed picture, we suggest that an individual decision should be taken instead of disregarding spammers as a matter of principle. Finally, we discuss a set of applications which operationalize the results of our studies for enhancing both Social Annotation and semantic systems. These comprise on the one hand tools which foster the emergence of semantics, and on the one hand applications which exploit the socially induced relations to improve, e. g., searching, browsing, or user profiling facilities. In summary, the contributions of this work highlight viable methods and crucial aspects for designing enhanced knowledge-based services of a Social Semantic Web.