Automatic code generation: from process algebraic architectural descriptions to multithreaded java programs

Process algebraic architectural description languages provide a formal means for modeling software systems and assessing their properties. In order to bridge the gap between system modeling and system im- plementation, in this thesis an approach is proposed for automatically generating multithreaded object-oriented code from process algebraic architectural descriptions, in a way that preserves – under certain assumptions – the properties proved at the architectural level. The approach is divided into three phases, which are illustrated by means of a running example based on an audio processing system. First, we develop an architecture-driven technique for thread coordination management, which is completely automated through a suitable package. Second, we address the translation of the algebraically-specified behavior of the individual software units into thread templates, which will have to be filled in by the software developer according to certain guidelines. Third, we discuss performance issues related to the suitability of synthesizing monitors rather than threads from software unit descriptions that satisfy specific constraints. In addition to the running example, we present two case studies about a video animation repainting system and the implementation of a leader election algorithm, in order to summarize the whole approach. The outcome of this thesis is the implementation of the proposed approach in a translator called PADL2Java and its integration in the architecture-centric verification tool TwoTowers.

Periodic Higgs-de Rham flows and representations of algebraic fundamental groups

Let k := bar{F}_p for p > 2, W_n(k) := W(k)/p^n and X_n be a projective smooth W_n(k)-scheme which is W_{n+1}(k)-liftable. For all n > 1, we construct explicitly a functor, which we call the inverse Cartier functor, from a subcategory of Higgs bundles over X_n to a subcategory of flat Bundles over X_n. Then we introduce the notion of periodic Higgs-de Rham flows and show that a periodic Higgs-de Rham flow is equivalent to a Fontaine-Faltings module. Together with a p-adic analogue of Riemann-Hilbert correspondence established by Faltings, we obtain a coarse p-adic Simpson correspondence.

Polar Codes for error correction: Analysis and Decoding Algorithms

I Polar Codes sono la prima classe di codici a correzione d’errore di cui è stato dimostrato il raggiungimento della capacità per ogni canale simmetrico, discreto e senza memoria, grazie ad un nuovo metodo introdotto recentemente, chiamato ”Channel Polarization”. In questa tesi verranno descritti in dettaglio i principali algoritmi di codifica e decodifica. In particolare verranno confrontate le prestazioni dei simulatori sviluppati per il ”Successive Cancellation Decoder” e per il ”Successive Cancellation List Decoder” rispetto ai risultati riportati in letteratura. Al fine di migliorare la distanza minima e di conseguenza le prestazioni, utilizzeremo uno schema concatenato con il polar code come codice interno ed un CRC come codice esterno. Proporremo inoltre una nuova tecnica per analizzare la channel polarization nel caso di trasmissione su canale AWGN che risulta il modello statistico più appropriato per le comunicazioni satellitari e nelle applicazioni deep space. In aggiunta, investigheremo l’importanza di una accurata approssimazione delle funzioni di polarizzazione.

Approximate decoding approaches for network coded correlated data

This paper considers a framework where data from correlated sources are transmitted with the help of network coding in ad hoc network topologies. The correlated data are encoded independently at sensors and network coding is employed in the intermediate nodes in order to improve the data delivery performance. In such settings, we focus on the problem of reconstructing the sources at decoder when perfect decoding is not possible due to losses or bandwidth variations. We show that the source data similarity can be used at decoder to permit decoding based on a novel and simple approximate decoding scheme. We analyze the influence of the network coding parameters and in particular the size of finite coding fields on the decoding performance. We further determine the optimal field size that maximizes the expected decoding performance as a trade-off between information loss incurred by limiting the resolution of the source data and the error probability in the reconstructed data. Moreover, we show that the performance of the approximate decoding improves when the accuracy of the source model increases even with simple approximate decoding techniques. We provide illustrative examples showing how the proposed algorithm can be deployed in sensor networks and distributed imaging applications.

Involvement of a region of 23S ribosomal RNA of {\it E. coli\/} in decoding of termination codons

Involvement of E. coli 23S ribosomal RNA (rRNA) in decoding of termination codons was first indicated by the characterization of a 23S rRNA mutant that causes UGA-specific nonsense suppression. The work described here was begun to test the hypothesis that more 23S rRNA suppressors of specific nonsense mutations can be isolated and that they would occur non-randomly in the rRNA genes and be clustered in specific, functionally significant regions of rRNA.^ Approximately 2 kilobases of the gene for 23S rRNA were subjected to PCR random mutagenesis and the amplified products screened for suppression of nonsense mutations in trpA. All of the suppressor mutations obtained were located in a thirty-nucleotide part of the GTPase center, a conserved rRNA sequence and structure, and they and others made in that region by site-directed mutagenesis were shown to be UGA-specific in their suppression of termination codon mutations. These results proved the initial hypothesis and demonstrated that a group of nucleotides in this region are involved in decoding of the UGA termination codon. Further, it was shown that limitation of cellular availability or synthesis of L11, a ribosomal protein that binds to the GTPase center rRNA, resulted in suppression of termination codon mutations, suggesting the direct involvement of L11 in termination in vivo.^ Finally, in vivo analysis of certain site-specific mutations made in the GTPase center RNA demonstrated that (a) the G$\cdot$A base pair closing the hexanucleotide hairpin loop was not essential for normal termination, (b) the "U-turn" structure in the 1093 to 1098 hexaloop is critical for normal termination, (c) nucleotides A1095 and A1067, necessary for the binding to ribosomes of thiostrepton, an antibiotic that inhibits polypeptide release factor binding to ribosomes in vitro, are also necessary for normal peptide chain termination in vivo, and (d) involvement of this region of rRNA in termination is determined by some unique subset structure that includes particular nucleotides rather than merely by a general structural feature of the GTPase center.^ This work advances the understanding of peptide chain termination by demonstrating that the GTPase region of 23S rRNA participates in recognition of termination codons, through an associated ribosomal protein and specific conserved nucleotides and structural motifs in its RNA. ^

Functions and intramolecular interactions of ribosomal RNA in decoding of termination codons

Two regions in the 3$\prime$ domain of 16S rRNA (the RNA of the small ribosomal subunit) have been implicated in decoding of termination codons. Using segment-directed PCR random mutagenesis, I isolated 33 translational suppressor mutations in the 3$\prime$ domain of 16S rRNA. Characterization of the mutations by both genetic and biochemical methods indicated that some of the mutations are defective in UGA-specific peptide chain termination and that others may be defective in peptide chain termination at all termination codons. The studies of the mutations at an internal loop in the non-conserved region of helix 44 also indicated that this structure, in a non-conserved region of 16S rRNA, is involved in both peptide chain termination and assembly of 16S rRNA.^ With a suppressible trpA UAG nonsense mutation, a spontaneously arising translational suppressor mutation was isolated in the rrnB operon cloned into a pBR322-derived plasmid. The mutation caused suppression of UAG at two codon positions in trpA but did not suppress UAA or UGA mutations at the same trpA positions. The specificity of the rRNA suppressor mutation suggests that it may cause a defect in UAG-specific peptide chain termination. The mutation is a single nucleotide deletion (G2484$\Delta$) in helix 89 of 23S rRNA (the large RNA of the large ribosomal subunit). The result indicates a functional interaction between two regions of 23S rRNA. Furthermore, it provides suggestive in vivo evidence for the involvement of the peptidyl-transferase center of 23S rRNA in peptide chain termination. The $\Delta$2484 and A1093/$\Delta$2484 (double) mutations were also observed to alter the decoding specificity of the suppressor tRNA lysT(U70), which has a mutation in its acceptor stem. That result suggests that there is an interaction between the stem-loop region of helix 89 of 23S rRNA and the acceptor stem of tRNA during decoding and that the interaction is important for the decoding specificity of tRNA.^ Using gene manipulation procedures, I have constructed a new expression vector to express and purify the cellular protein factors required for a recently developed, realistic in vitro termination assay. The gene for each protein was cloned into the newly constructed vector in such a way that expression yielded a protein with an N-terminal affinity tag, for specific, rapid purification. The amino terminus was engineered so that, after purification, the unwanted N-terminal tag can be completely removed from the protein by thrombin cleavage, yielding a natural amino acid sequence for each protein. I have cloned the genes for EF-G and all three release factors into this new expression vector and the genes for all the other protein factors into a pCAL-n expression vector. These constructs will allow our laboratory group to quickly and inexpensively purify all the protein factors needed for the new in vitro termination assay. (Abstract shortened by UMI.) ^

Decoding Delay Minimization in Inter-Session Network Coding

Intra-session network coding has been shown to offer significant gains in terms of achievable throughput and delay in settings where one source multicasts data to several clients. In this paper, we consider a more general scenario where multiple sources transmit data to sets of clients over a wireline overlay network. We propose a novel framework for efficient rate allocation in networks where intermediate network nodes have the opportunity to combine packets from different sources using randomized network coding. We formulate the problem as the minimization of the average decoding delay in the client population and solve it with a gradient-based stochastic algorithm. Our optimized inter-session network coding solution is evaluated in different network topologies and is compared with basic intra-session network coding solutions. Our results show the benefits of proper coding decisions and effective rate allocation for lowering the decoding delay when the network is used by concurrent multicast sessions.

Flexibility Properties in Complex Analysis and Affine Algebraic Geometry

In the last decades affine algebraic varieties and Stein manifolds with big (infinite-dimensional) automorphism groups have been intensively studied. Several notions expressing that the automorphisms group is big have been proposed. All of them imply that the manifold in question is an Oka–Forstnerič manifold. This important notion has also recently merged from the intensive studies around the homotopy principle in Complex Analysis. This homotopy principle, which goes back to the 1930s, has had an enormous impact on the development of the area of Several Complex Variables and the number of its applications is constantly growing. In this overview chapter we present three classes of properties: (1) density property, (2) flexibility, and (3) Oka–Forstnerič. For each class we give the relevant definitions, its most significant features and explain the known implications between all these properties. Many difficult mathematical problems could be solved by applying the developed theory, we indicate some of the most spectacular ones.