Theoretical and implementation aspects in the mechanization of the metatheory of programming languages

Interactive theorem provers are tools designed for the certification of formal proofs developed by means of man-machine collaboration. Formal proofs obtained in this way cover a large variety of logical theories, ranging from the branches of mainstream mathematics, to the field of software verification. The border between these two worlds is marked by results in theoretical computer science and proofs related to the metatheory of programming languages. This last field, which is an obvious application of interactive theorem proving, poses nonetheless a serious challenge to the users of such tools, due both to the particularly structured way in which these proofs are constructed, and to difficulties related to the management of notions typical of programming languages like variable binding. This thesis is composed of two parts, discussing our experience in the development of the Matita interactive theorem prover and its use in the mechanization of the metatheory of programming languages. More specifically, part I covers: - the results of our effort in providing a better framework for the development of tactics for Matita, in order to make their implementation and debugging easier, also resulting in a much clearer code; - a discussion of the implementation of two tactics, providing infrastructure for the unification of constructor forms and the inversion of inductive predicates; we point out interactions between induction and inversion and provide an advancement over the state of the art. In the second part of the thesis, we focus on aspects related to the formalization of programming languages. We describe two works of ours: - a discussion of basic issues we encountered in our formalizations of part 1A of the Poplmark challenge, where we apply the extended inversion principles we implemented for Matita; - a formalization of an algebraic logical framework, posing more complex challenges, including multiple binding and a form of hereditary substitution; this work adopts, for the encoding of binding, an extension of Masahiko Sato's canonical locally named representation we designed during our visit to the Laboratory for Foundations of Computer Science at the University of Edinburgh, under the supervision of Randy Pollack.

Measurement of the K + - pi + pi - e + - (-) v e form factors and of the pi pi scattering length a 0 0

The quark condensate is a fundamental free parameter of Chiral Perturbation Theory ($chi PT$), since it determines the relative size of the mass and momentum terms in the power expansion. In order to confirm or contradict the assumption of a large quark condensate, on which $chi PT$ is based, experimental tests are needed. In particular, the $S$-wave $pipi$ scattering lengths $a_0^0$ and $a_0^2$ can be predicted precisely within $chi PT$ as a function of this parameter and can be measured very cleanly in the decay $K^{pm} to pi^{+} pi^{-} e^{pm} stackrel{mbox{tiny(---)}}{nu_e}$ ($K_{e4}$). About one third of the data collected in 2003 and 2004 by the NA48/2 experiment were analysed and 342,859 $K_{e4}$ candidates were selected. The background contamination in the sample could be reduced down to 0.3% and it could be estimated directly from the data, by selecting events with the same signature as $K_{e4}$, but requiring for the electron the opposite charge with respect to the kaon, the so-called ``wrong sign'' events. This is a clean background sample, since the kaon decay with $Delta S=-Delta Q$, that would be the only source of signal, can only take place through two weak decays and is therefore strongly suppressed. The Cabibbo-Maksymowicz variables, used to describe the kinematics of the decay, were computed under the assumption of a fixed kaon momentum of 60 GeV/$c$ along the $z$ axis, so that the neutrino momentum could be obtained without ambiguity. The measurement of the form factors and of the $pipi$ scattering length $a_0^0$ was performed in a single step by comparing the five-dimensional distributions of data and MC in the kinematic variables. The MC distributions were corrected in order to properly take into account the trigger and selection efficiencies of the data and the background contamination. The following parameter values were obtained from a binned maximum likelihood fit, where $a_0^2$ was expressed as a function of $a_0^0$ according to the prediction of chiral perturbation theory: f'_s/f_s = 0.133+- 0.013(stat)+- 0.026(syst) f''_s/f_s = -0.041+- 0.013(stat)+- 0.020(syst) f_e/f_s = 0.221+- 0.051(stat)+- 0.105(syst) f'_e/f_s = -0.459+- 0.170(stat)+- 0.316(syst) tilde{f_p}/f_s = -0.112+- 0.013(stat)+- 0.023(syst) g_p/f_s = 0.892+- 0.012(stat)+- 0.025(syst) g'_p/f_s = 0.114+- 0.015(stat)+- 0.022(syst) h_p/f_s = -0.380+- 0.028(stat)+- 0.050(syst) a_0^0 = 0.246+- 0.009(stat)+- 0.012(syst)}+- 0.002(theor), where the statistical uncertainty only includes the effect of the data statistics and the theoretical uncertainty is due to the width of the allowed band for $a_0^2$.

Eine neue Form der Pyruvatkinase in Säugerspermien

Nach Homogenisation ejakulierter Eberspermien und Zentrifugation des Homogenates blieben mehr als 60% der Aktivität des glykolytischen Enzyms Pyruvatkinase (PK) an Zellfragmenten im Sediment gebunden. Diese strukturgebundene PK wurde als PK-S bezeichnet. Das Detergenz Triton X-100 führte nicht zur Ablösung der PK-S; mit Trypsin konnten jedoch rund 80% der PK-S ohne Verlust an Aktivität von den Strukturen gelöst und durch kombinierte Kationenaustausch- und Hydrophobizitätschromatographie gereinigt werden (spezifische Aktivität: 116,7 U/mg Protein). Die lösliche PK aus Eberspermien konnte ebenfalls durch ein ähnliches Verfahren angereichert werden. Im Gel (SDS-PAGE) zeigten die Untereinheiten der PK-S mit 64.400 eine geringfügig größere relative Molekülmasse als die der PK-M1 aus Kaninchenmuskel (62.000). Die kinetischen Eigenschaften der abgelösten PK-S als auch der noch an Spermienstrukturen gebundenen PK-S und der löslichen PK aus Eberspermien waren sehr ähnlich und entsprachen der M1-Isoform der PK. Antikörper gegen Kaninchenmuskel-PK (Anti-PK-M1) reagierten auch mit der löslichen PK und der PK-S aus Eberspermien. Edman-Abbau der ersten 19 Aminosäuren zeigte, dass die tryptisch abgelöste PK-S am N-Terminus um 5 Aminosäuren gegenüber nativer PK-M1 verlängert ist, während der C-Terminus der erhaltenen PK-S-Sequenz mit einem meist nahe dem N-Terminus gelegenen Sequenzabschnitt der PK-M1 und -M2 übereinstimmt. Die N-terminale Verlängerung der nativen PK-S enthält sicherlich mehr als die nach tryptischer Lyse nachgewiesenen 5 Aminosäuren. Vergleiche der Aminosäure- und übersetzten Nukleotidsequenzen sowie die kinetischen Eigenschaften lassen vermuten, dass die PK-S, wie die PK-M1 und PK-M2, vom PKM-Gen codiert wird. Gegen die gereinigte PK-S wurden Antikörper in Kaninchen produziert. Da das Antiserum nicht ausreichend spezifisch für PK-S war, wurden aus ihm affinitätschromatographisch Antikörper (Anti-PK-S) isoliert, die hohe Affinität zu einem synthetisierten PK-S-Peptid (13 N-terminale Aminosäuren der tryptisch abgelösten PK-S) hatten. Dieses Anti-PK-S-Präparat war spezifisch für PK-S; es reagierte weder mit Kaninchenmuskel-PK noch mit löslicher PK oder anderen Proteinen aus Eberspermien. Anti-PK-S und Anti-PK-M1 wurden zur Lokalisierung von PK-S und löslicher PK in Spermien von Eber, Bulle und Mensch sowie in Schnitten von Eberhoden eingesetzt. Mit Anti-PK-S wurden der Bereich des Akrosoms und das lange flagellare Hauptstück sowie der Übergangsbereich zwischen Kopf und Mittelstück von Eberspermien fluoreszenzmarkiert, wogegen das kurze, die Mitochondrien enthaltende Mittelstück des Flagellums und der postakrosomale Kopfbereich nur mit Anti-PK-M1 markiert wurden. Immunogoldmarkierung in elektronenmikroskopischen Bildern bestätigte die Lokalisierung von PK-S im Akrosombereich. Im Hauptstück banden Anti-PK-M1 und Anti-PK-S an die fibröse Scheide. Glyzerinaldehyd-3-phosphat Dehydrogenase (GAPDH) konnte von mir ebenfalls im Akrosombereich, im Übergangsbereich zwischen Kopf und Mittelstück und an der fibrösen Scheide detektiert werden. Auch an Bullen- und Humanspermien konnte über Immunogoldmarkierung PK und vermutlich GAPDH an der fibrösen Scheide gezeigt werden. Im Akrosombereich dieser Spermien waren die Nachweise von PK und GAPDH jedoch nicht sicher. In Eberhodenschnitten war die PK-S erstmals, oder zumindest vermehrt, in den elongierenden Spermatiden über Fluoreszenzmarkierung nachweisbar, während andere, vermutlich somatische PK vermehrt in den früheren Stadien (Spermatogonien, aber auch in den Spermatozyten und runden Spermatiden) auftrat. Für die GAPDH zeigte sich ein ähnlicher Entwicklungsverlauf. Die Ergebnisse zeigen, dass in Eberspermien zwei Isoformen der PK auftreten: eine N-terminal verlängerte, strukturgebundene Form, die PK-S, und eine lösliche Form, die beide der PK-M1 ähneln. Der ungewöhnliche N-Terminus der PK-S dient vermutlich der spezifischen räumlichen Anordnung der PK-S im Akrosombereich und an der fibrösen Scheide, nicht aber der Modulation kinetischer Eigenschaften. Meine Untersuchungen stützen die Hypothese, dass in bestimmten Kompartimenten von Säugerspermien die Glykolyse durch Verankerung einiger ihrer Enzyme strukturell hochgeordnet ist. Dadurch wird vermutlich die Versorgung der Mitochondrien-freien Regionen mit ATP sichergestellt. Man kann diese Organisation als Anpassung des Stoffwechsels von Spermien deuten, bei denen die Mitochondrien in einem kleinen Bereich (Mittelstück) hinter dem Spermienkopf kompartimentiert sind. Im Hauptstück des Flagellums könnte die Glykolyse ATP für die Spermienmotilität liefern, im Akrosombereich für die Verhinderung einer vorzeitigen Akrosomreaktion. Somit käme der strukturierten Glykolyse eine essentielle Bedeutung für die Befruchtungsfähigkeit von Säugerspermien zu.

Pseudodifferential operators on Hilbert space riggings with associated psi *-algebras and generalized Hörmander classes

The present thesis is concerned with certain aspects of differential and pseudodifferential operators on infinite dimensional spaces. We aim to generalize classical operator theoretical concepts of pseudodifferential operators on finite dimensional spaces to the infinite dimensional case. At first we summarize some facts about the canonical Gaussian measures on infinite dimensional Hilbert space riggings. Considering the naturally unitary group actions in $L^2(H_-,gamma)$ given by weighted shifts and multiplication with $e^{iSkp{t}{cdot}_0}$ we obtain an unitary equivalence $F$ between them. In this sense $F$ can be considered as an abstract Fourier transform. We show that $F$ coincides with the Fourier-Wiener transform. Using the Fourier-Wiener transform we define pseudodifferential operators in Weyl- and Kohn-Nirenberg form on our Hilbert space rigging. In the case of this Gaussian measure $gamma$ we discuss several possible Laplacians, at first the Ornstein-Uhlenbeck operator and then pseudo-differential operators with negative definite symbol. In the second case, these operators are generators of $L^2_gamma$-sub-Markovian semi-groups and $L^2_gamma$-Dirichlet-forms. In 1992 Gramsch, Ueberberg and Wagner described a construction of generalized Hörmander classes by commutator methods. Following this concept and the classical finite dimensional description of $Psi_{ro,delta}^0$ ($0leqdeltaleqroleq 1$, $delta< 1$) in the $C^*$-algebra $L(L^2)$ by Beals and Cordes we construct in both cases generalized Hörmander classes, which are $Psi^*$-algebras. These classes act on a scale of Sobolev spaces, generated by our Laplacian. In the case of the Ornstein-Uhlenbeck operator, we prove that a large class of continuous pseudodifferential operators considered by Albeverio and Dalecky in 1998 is contained in our generalized Hörmander class. Furthermore, in the case of a Laplacian with negative definite symbol, we develop a symbolic calculus for our operators. We show some Fredholm-criteria for them and prove that these Fredholm-operators are hypoelliptic. Moreover, in the finite dimensional case, using the Gaussian-measure instead of the Lebesgue-measure the index of these Fredholm operators is still given by Fedosov's formula. Considering an infinite dimensional Heisenberg group rigging we discuss the connection of some representations of the Heisenberg group to pseudo-differential operators on infinite dimensional spaces. We use this connections to calculate the spectrum of pseudodifferential operators and to construct generalized Hörmander classes given by smooth elements which are spectrally invariant in $L^2(H_-,gamma)$. Finally, given a topological space $X$ with Borel measure $mu$, a locally compact group $G$ and a representation $B$ of $G$ in the group of all homeomorphisms of $X$, we construct a Borel measure $mu_s$ on $X$ which is invariant under $B(G)$.

Monte-Carlo simulation of hard spherocylinders under confinement

When a liquid crystal is confined to a cavity its director field becomes subject to competing forces: on the one hand, the surface of the cavity orients the director field (``surface anchoring''), on the other hand deformations of the director field cost elastic energy. Hence the equilibrium director field is determined by a compromise between surface anchoring and elasticity. One example of a confined liquid crystal that has attracted particular interest from physicists is the nematic droplet. In this thesis a system of hard rods is considered as the simplest model for nematic liquid crystals consisting of elongated molecules. First, systems of hard spherocylinders in a spherical geometry are investigated by means of canonical Monte Carlo simulations. In contrast to previous simulation work on this problem, a continuum model is used. In particular, the effects of ordering near hard curved walls are studied for the low-density regime. With increasing density, first a uniaxial surface film forms and then a biaxial surface film, which eventually fills the entire cavity. We study how the surface order, the adsorption and the shape of the director field depend on the curvature of the wall. We find that orientational ordering at a curved wall in a cavity is stronger than at a flat wall, while adsorption is weaker. For densities above the isotropic-nematic transition, we always find bipolar configurations. As a next step, an extension of the Asakura-Oosawa-Vrij model for colloid-polymer mixtures to anisotropic colloids is considered. By means of computer simulations we study how droplets of hard, rod-like particles optimize their shape and structure under the influence of the osmotic compression caused by the presence of spherical particles that act as depletion agents. At sufficiently high osmotic pressures the rods that make up the drops spontaneously align to turn them into uniaxial nematic liquid crystalline droplets. The nematic droplets or ``tactoids'' that so form are not spherical but elongated, resulting from the competition between the anisotropic surface tension and the elastic deformation of the director field. In agreement with recent theoretical predictions we find that sufficiently small tactoids have a uniform director field, whilst large ones are characterized by a bipolar director field. From the shape and director-field transformation of the droplets we estimate the surface anchoring strength.

Der Wille zur Form - ein ästhetisch-anthropologischer Diskurs

Die vorliegende Arbeit untersucht die Formästhetik im Kunstdenken der Moderne. Bedeutend ist, dass im Zusammenhang mit der Formästhetik meist auch gewisse ästhetische Anthropologieentwürfe entstehen. In Ermangelung geeigneter Definitionsansätze wird die Form, frei von Vordeutungen, als dynamisches Konstrukt betrachtet. Dementsprechend verändert sich auch der Blick auf die anthropologischen Konzepte der untersuchten Texte. Bei allen behandelten Autoren wird deutlich, dass der Verlust absoluter Werte, der sich in der Moderne immer weiter ausdifferenziert, zum Fundament der Kunstanschauung wird. Der Mensch ist einer gewissen Tragik ausgeliefert: Er ist fortan Schöpfer der eigenen Realität, aber auch immer an die Materie gebunden. Dies führt zu einer Widersprüchlichkeit des menschlichen Daseins, für das eine ‚reine Identität’ nicht erreichbar ist. Die Befreiung von der menschlichen Zerissenheit kann scheinbar durch die ästhetische Betrachtung erlangt werden. Die künstlerische Formgebung entlastet von der widersprüchlichen menschlichen Realität und die Kunst wird zum Ideal der Freiheit. Mittels der schöpferischen Kraft kann der Mensch ein Bild seiner Menschlicheit formen und bestimmen. Der künstlerischen Form wird der Stellenwert eines Mythos zugeordnet. Eine solche Kunstanschauung birgt Gefahren, denn mit der Erhebung in den Stand eines Mythos wird sie zum absoluten Welterklärungsmodell oder gar zur Ideologie. Tatsächlich fehlt jedoch jegliche ethische Untermauerung in der Lebenswirklichkeit. Die ausgewählten Autoren beleuchten den Diskurs und die ihm innewohnenden Gefahren auf unterschiedliche Art und Weise: Friedrich Schiller, die Denker der Frühromantik, Arthur Schopenhauer, Friedrich Nietzsche, Gottfried Benn, Thomas Mann, Theodor W. Adorno, Elias Canetti und die Denker der Postmoderne. Der subversive Einfluss der unterschiedlichen Formentwürfe wird bei mehr als einem Autor deutlich. Daher ist die Frage, wie eine ideologische Vereinnahmung dieser Ideenkonstrukte verhindert werden kann. Dies führt zu einer Neudefinition der Formästhetik. Neuer Fixpunkt muss die Realität des Denkens sein, d.h. Realität und Idee dürfen nicht im Kontrast, sondern müssen in Relation betrachtet werden, denn schließlich ist es diese Relation, die den Menschen zu bestimmen scheint. Die Distanz von Ästhetik und Realität muss bewusst und kritisch hinterfragt werden, um zu einer ‚Ästhetik des Negativen’ zu führen.