On the Gap-Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.

Research through DESIGN through research - a problem statement and a conceptual sketch

This paper re-addresses the issue of a lacking genuine design research paradigm. It tries to sketch an operational model of such a paradigm, based upon a generic design process model, which is derived from basic notions of evolution and learning in different domains of knowing (and turns out to be not very different from existing ones). It does not abandon the scientific paradigm but concludes that the latter has to be embedded into / subordinated under a design paradigm.

Church-Rosser groups and growing context-sensitive groups

A finitely generated group is called a Church-Rosser group (growing context-sensitive group) if it admits a finitely generated presentation for which the word problem is a Church-Rosser (growing context-sensitive) language. Although the Church-Rosser languages are incomparable to the context-free languages under set inclusion, they strictly contain the class of deterministic context-free languages. As each context-free group language is actually deterministic context-free, it follows that all context-free groups are Church-Rosser groups. As the free abelian group of rank 2 is a non-context-free Church-Rosser group, this inclusion is proper. On the other hand, we show that there are co-context-free groups that are not growing context-sensitive. Also some closure and non-closure properties are established for the classes of Church-Rosser and growing context-sensitive groups. More generally, we also establish some new characterizations and closure properties for the classes of Church-Rosser and growing context-sensitive languages.

Observations on the Publicity and Usage of Parallel Programming Systems and Languages: A Survey Approach

In this publication, we report on an online survey that was carried out among parallel programmers. More than 250 people worldwide have submitted answers to our questions, and their responses are analyzed here. Although not statistically sound, the data we provide give useful insights about which parallel programming systems and languages are known and in actual use. For instance, the collected data indicate that for our survey group MPI and (to a lesser extent) C are the most widely used parallel programming system and language, respectively.

A User-Centric Perspective on Parallel Programming with Focus on OpenMP

The process of developing software that takes advantage of multiple processors is commonly referred to as parallel programming. For various reasons, this process is much harder than the sequential case. For decades, parallel programming has been a problem for a small niche only: engineers working on parallelizing mostly numerical applications in High Performance Computing. This has changed with the advent of multi-core processors in mainstream computer architectures. Parallel programming in our days becomes a problem for a much larger group of developers. The main objective of this thesis was to find ways to make parallel programming easier for them. Different aims were identified in order to reach the objective: research the state of the art of parallel programming today, improve the education of software developers about the topic, and provide programmers with powerful abstractions to make their work easier. To reach these aims, several key steps were taken. To start with, a survey was conducted among parallel programmers to find out about the state of the art. More than 250 people participated, yielding results about the parallel programming systems and languages in use, as well as about common problems with these systems. Furthermore, a study was conducted in university classes on parallel programming. It resulted in a list of frequently made mistakes that were analyzed and used to create a programmers' checklist to avoid them in the future. For programmers' education, an online resource was setup to collect experiences and knowledge in the field of parallel programming - called the Parawiki. Another key step in this direction was the creation of the Thinking Parallel weblog, where more than 50.000 readers to date have read essays on the topic. For the third aim (powerful abstractions), it was decided to concentrate on one parallel programming system: OpenMP. Its ease of use and high level of abstraction were the most important reasons for this decision. Two different research directions were pursued. The first one resulted in a parallel library called AthenaMP. It contains so-called generic components, derived from design patterns for parallel programming. These include functionality to enhance the locks provided by OpenMP, to perform operations on large amounts of data (data-parallel programming), and to enable the implementation of irregular algorithms using task pools. AthenaMP itself serves a triple role: the components are well-documented and can be used directly in programs, it enables developers to study the source code and learn from it, and it is possible for compiler writers to use it as a testing ground for their OpenMP compilers. The second research direction was targeted at changing the OpenMP specification to make the system more powerful. The main contributions here were a proposal to enable thread-cancellation and a proposal to avoid busy waiting. Both were implemented in a research compiler, shown to be useful in example applications, and proposed to the OpenMP Language Committee.

Physik lernen, um Physik zu lehren

Aus mehreren Untersuchungen zum Interesse der Schülerinnen und Schüler am Physikunterricht ist bekannt, dass der Unterricht dann für sie interessant ist, wenn die fachlichen Inhalte in einen für die Schülerinnen und Schüler relevanten Kontext eingebunden sind. Die vorliegende empirische Untersuchung beschäftigt sich mit dem Kontext „Physik lernen durch lehren“. Bei diesem Kontext sollen Schülerinnen und Schüler des Gymnasiums Physik lernen, um anschließend Kindern in der Vor- und Grundschule selbst naturwissenschaftliche Inhalte zu vermitteln. Der Kontext wurde dahingehend untersucht, inwiefern er das situationale Interesse der Schülerinnen und Schüler am Physikunterricht beeinflusst und welchen Einfluss er auf die Vermittlung fachlicher und überfachlicher Kompetenzen hat. Die Arbeit basiert auf der Selbstbestimmungstheorie der Motivation von Deci u. Ryan (1993) sowie der pädagogischen Interessentheorie von Krapp u. Prenzel (1992). Um die Interessantheit des Unterrichts im Kontext und den Erwerb von Kompetenzen festzustellen, wurden im Rahmen der Untersuchung zwei quantitative Studien mittels Fragebogenerhebungen und eine qualitative Studie in Form von Leitfaden-Interviews sowohl mit Schülerinnen und Schülern als auch mit Lehrkräften durchgeführt. Die Ergebnisse der Untersuchung zeigen, dass der Unterricht im Kontext „Physik lernen durch lehren“ hinsichtlich der Interessantheit deutlich den herkömmlichen Zugängen überlegen ist. In der Untersuchung wurde eine Reihe von potenziellen Einflussvariablen auf die festgestellte Interessantheit am Unterricht in dem zu unter-suchenden Kontext ermittelt. Der Unterricht wurde in erster Linie aufgrund der naturwissenschaftlichen Veranstaltungen mit den Vor- und Grundschulkindern für die Schülerinnen und Schüler interessanter. Es wurde festgestellt, dass der Kontext besonders bei Schülerinnen und Schülern, die am Unterrichtsfach Physik allgemein unterdurchschnittlich interessiert sind, auf ein größeres situationales Interesse stößt. Insbesondere Mädchen zeigen ein großes situationales Interesse an dem Kontext. Bei dem kontextorientierten Unterricht werden neben fachlichen Kompetenzen vor allem überfachliche Kompetenzen bei den Schülerinnen und Schülern gefördert. Der Schwerpunkt bei den fachlichen Kompetenzen liegt im Bereich des Prozesswissens, und bei den überfachlichen Kompetenzen werden primär das methodisch-problemlösende Lernen und das sozial-kommunikative Lernen gefördert.

The problem of noncharacteristic quasimolecular X-rays in heavy ion collision

Quasi-molecular X-rays observed in heavy ion collisions are interpreted within a relativistic calculation of correlation diagrams using the Dirac-Slater model. A semiquantitative description of noncharacteristic M X rays is given for the system Au-I.

Approximate solutions and error estimates for a Stokes boundary value problem

The aim of this paper is the numerical treatment of a boundary value problem for the system of Stokes' equations. For this we extend the method of approximate approximations to boundary value problems. This method was introduced by V. Maz'ya in 1991 and has been used until now for the approximation of smooth functions defined on the whole space and for the approximation of volume potentials. In the present paper we develop an approximation procedure for the solution of the interior Dirichlet problem for the system of Stokes' equations in two dimensions. The procedure is based on potential theoretical considerations in connection with a boundary integral equations method and consists of three approximation steps as follows. In a first step the unknown source density in the potential representation of the solution is replaced by approximate approximations. In a second step the decay behavior of the generating functions is used to gain a suitable approximation for the potential kernel, and in a third step Nyström's method leads to a linear algebraic system for the approximate source density. For every step a convergence analysis is established and corresponding error estimates are given.