MA thesis project Klára Schneiderová PREDICATE ANALYSIS AND ANALYSIS OF METAPHORS USED IN MESSAGES ATTRIBUTED TO OSAMA BIN LADEN REGARDING THE UNITED STATES OF AMERICAAND THEIR EUROPEAN ALLIES FOLLOWING THE 2003 INVASION OF IRAQ INTRODUCTION - War on terror = war on Islam? (analysis of fundamentalist logic and stream of thought) For this Master thesis project, I chose to analyze the terrorist discourse of Osama bin Laden, the leader of the global Jihadist network, al-Qaeda, particularly his messages regarding the United States of America and its European allies following the 2003 invasion of Iraq, as they were gathered in various relevant sources of record up to the near present.1 I chose this topic due to my long-term interest in the Middle East, particularly the relationship and links between religious ideology and politics in the region. The methodology chosen for this work is closely related to media image analysis which I became familiar with during my previous studies and which I applied in my Bachelor's thesis. In the world today, I believe it has become increasingly important to reflect, observe and closely examine the roots and foundations of fundamentalist argumentation and logic, which in this case serve as the key motors of the global Jihadist movement. Following the 9-11-01 terrorist attacks...

We examine the complexity and expressivity of the combination of the Description Logic ALCQI with a terminological formalism based on cardinality restrictions on concepts. This combination can naturally be embedded into C², the two variable fragment of predicate logic with counting quantifiers. We prove that ALCQI has the same complexity as C² but does not reach its expressive power. / An abriged version of this paper has been submitted to CSL'99

Predicate abstraction is a key enabling technology for applying model checkers to programs written in mainstream languages. It has been used very successfully for debugging sequential system-level C code. Although model checking was originally designed for analysing concurrent systems, there is little evidence of fruitful applications of predicate abstraction to shared-variable concurrent software. The goal of the present thesis is to close this gap. We propose an algorithmic solution implementing predicate abstraction that targets safety properties in non-recursive programs executed by an unbounded number of threads, which communicate via shared memory or higher-level mechanisms, such as mutexes and broadcasts. As system-level code makes frequent use of such primitives, their correct usage is critical to ensure reliability. Monotonicity - the property that thread actions remain executable when other threads are added to the current global state - is a natural and common feature of human-written concurrent software. It is also useful: if every thread’s memory is finite, monotonicity often guarantees the decidability of safety properties even when the number of running threads is unspecified. In this thesis, we show that the process of obtaining finite-data thread abstrac tions for model checking is not always compatible with monotonicity. Predicate-abstracting certain mainstream asynchronous software such as the ticket busy-wait lock algorithm results in non-monotone multi-threaded Boolean programs, despite the monotonicity of the input program: the monotonicity is lost in the abstraction. As a result, the unbounded thread Boolean programs do not give rise to well quasi-ordered systems [1], for which sound and complete safety checking algorithms are available. In fact, safety checking turns out to be undecidable for the obtained class of abstract programs, despite the finiteness of the individual threads’ state spaces. Our solution is to restore the monotonicity in the abstract program, using an inexpensive closure operator that precisely preserves all safety properties from the (non-monotone) abstract program without the closure. As a second contribution, we present a novel, sound and complete, yet empirically much improved algorithm for verifying abstractions, applicable to general well quasi-ordered systems. Our approach is to gradually widen the set of safety queries during the search by program states that involve fewer threads and are thus easier to decide, and are likely to finalise the decision on earlier queries. To counter the negative impact of "bad guesses", i.e. program states that turn out feasible, the search is supported by a parallel engine that generates such states; these are never selected for widening. We present an implementation of our techniques and extensive experiments on multi-threaded C programs, including device driver code from FreeBSD and Solaris. The experiments demonstrate that by exploiting monotonicity, model checking techniques - enabled by predicate abstraction - scale to realistic programs even of a few thousands of multi-threaded C code lines.

<p>Doktorska disertacija prezentuje nov i opštiji način analiziranja&nbsp;semantike strukturiranih i objektno orijentisanih programa i to&nbsp;isključivo u okvirima predikatske logike prvog reda. Doktorska&nbsp;disertacija razmatra sledeće teme:<br />1.) S-programski račun,<br />2.) Definicija i osobine dinamičkih postuslova u S-računu,<br />3.) Konceptualne definicije objekta, klase i invarijante,<br />4.) Analiza invarijanata u klasi (SP-analiza i DP-analiza).</p> / <p>Doctoral thesis presents a new and more general method for analizing of&nbsp;structured and object-oriented program semantics, based on the first-order&nbsp;predicate logic. Doctoral thesis consideres next topics:<br />1.) S-program calculus,<br />2.) Definition and characteristics of dynamic postconditions in S-calculus,<br />3.) Conceptual definitions of object, class and invariant,<br />4.) Analyses of invariants in class (SP-analyses and DP-analyses).</p>

The topic of this thesis is a cryptosystem, precisely a public key encryption scheme, that is based on the knapsack problem. At first we formulate terms like \mathcal{NP} -complete problem, one-way function, hard-core predicate, public key encryption scheme and semantic security which we connect in this thesis. After that we present the knapsack problem. Then we prove that the knapsack problem with appropriate parameters has a property that leads to semantic security of the encryption scheme which we present afterwards. This public key encryption scheme is based on the scheme proposed by Vadim Lyubashevsky, Adriana Palacio and Gil Segev. Powered by TCPDF (www.tcpdf.org)

Magister Legum - LLM

Alors que les valeurs temporelles, aspectuelles et modales en français sont principalement exprimées par les déterminants grammaticaux du verbe, l’expression de la temporalité en vietnamien s’appuie sur des marqueurs d’ordre lexical. L’objectif de cette recherche a été de montrer la différence qui existe dans la manière d’exprimer la temporalité en français et en vietnamien et donc de concevoir l’expression des valeurs temporelles, aspectuelles et modales dans chacune de ces langues. Ces valeurs étant véhiculées par des déterminants grammaticaux du verbe en français et par des marqueurs lexicaux en vietnamien, l’analyse a consisté tout d’abord à préciser les valeurs de ces éléments dans chaque langue, après avoir rappelé les points de vue de certains prédécesseurs dans ces domaines. Ensuite, une étude contrastive d’un extrait du Petit Prince en français et de deux de ses traductions en vietnamien a permis de mettre en évidence non seulement les facteurs qui régissent la présence ou l’absence de marqueurs en vietnamien, mais aussi les changements de sens et d’effets stylistiques qu’induisent le passage d’une langue à l’autre et le choix singulier qu’est à même de faire le traducteur. Cette recherche peut donc avoir une incidence immédiate pour l’enseignement du français à des apprenants vietnamiens et plus largement à des étudiants de Français Langue Etrangère comme pour la traduction. / While temporal, aspectual and modal values in French are mainly expressed by the verb’s grammatical determinants, the expression of temporality in Vietnamese is based on lexical markers. The objective of this research was to point out the difference in the manners of expressing temporality in French and Vietnamese, and therefore to figure out the expression of temporal, aspectual and modal values in each of these languages. With these values being conveyed by grammatical determinants of the verb in French and lexical markers in Vietnamese, the analysis was first to determine the values of these elements in each language, after recalling the views of some predecessors in these areas. Then, a contrastive study of an extract of the Little Prince in French and two of its translations in Vietnamese helped to highlight not only the factors that govern the presence or absence of markers in Vietnamese, but also semantic changes and stylistic effects induced by the transition from one language to the other and the singular choice of the translator. So this research can have an immediate impact on the teaching of French language to Vietnamese learners and more widely to students learning French as a foreign language as well as for translation.

Le travail de thèse présente une méthode de développement de systèmes automatisés basée sur les méthodes formelles B et TLA+. Le développement par raffinement est au cœur de la méthode proposée. Un système automatisé est modélisé par deux composants, un contrôlé formé par le dispositif physique et son environnement et un contrôleur pilotant ce dernier. Il est exprimé par un produit synchronisé sur les actions de ces deux composants. La première contribution de la thèse concerne la proposition d'une approche qui combine le B événementiel et le langage de modélisation TLA+ pour la vérification des propriétés de vivacité. Nous définissons une extension syntaxique et sémantique du B événementiel permettant d'exprimer des propriétés de vivacité. Nous développons un prototype pour la transformation d'un modèle B en un module TLA+ sur lequel nous effectuons la preuve des propriétés de vivacité avec le model checker TLC. Pour la vérification de ce type de propriétés sur des systèmes infinis, nous proposons l'utilisation des diagrammes de prédicats qui sont des abstractions des systèmes modélisés en TLA+. La deuxième contribution est la proposition d'une technique pour représenter explicitement le temps en B événementiel. Cette technique s'appuie sur la réalisation d'un entrelacement entre un processus qui gère le temps avec les autres processus du système. Le temps modélisé est discret et son écoulement est modélisé par des événements. Cette approche est assez différente des systèmes temporisés où l'on considère que le temps s'écoule indépendamment du système. Dans la troisième contribution, nous proposons une approche de développement des systèmes automatisés en utilisant la technique de composition où il s'agit de développer conjointement le contrôleur et le composant physique qu'il contrôle et appliquer le raffinement aussi bien sur le contrôleur que le contrôlé. Le raffinement est une technique de base des méthodes que nous proposons et si notre objectif est de construire des contrôleurs corrects, le critère de correction porte sur le comportement du système automatisé qui résulte de la composition du contrôleur et du contrôlé. Nous présentons également un théorème de compositionnalité qui indique sous quelles conditions il est possible de déduire que le composé des raffinements des contrôleur et contrôlé est un raffinement du composé des contrôleur et contrôlé abstraits. La dernière contribution porte sur la définition, la preuve et l'utilisation d'un patron de raffinement pour les processus continus dans des systèmes de production manufacturière. Ce type de patron prouvé permet d'utiliser l'abstraction discrète de l'effet d'un processus continu agissant pendant un certain temps / This thesis deals with the development of automated systems while following the formal methods B and TLA+. We propose a formal methodology based on the refinement paradigm to specify and verify the system that we model by two components: the controlled system representing the physical device and its environment, and the controller that controls the system. A synchronised product on the actions of these two components is applied to specify the automated system. As a first contribution, we propose an approach combining the event B method and the language TLA+ in order to verify liveness properties defined in user requirements. Inspired by the temporal logic of actions TLA, we first extend the event B notation to specify liveness properties and we give semantics of this extended syntax over traces. Second, we give transformation rules from a temporal B model into a TLA+ module. We present, in particular, our prototype system called B2TLA+, that we have developed to support this transformation. To consider infinite systems, we use predicate diagrams as abstractions of systems modelled with TLA+. To consider the real-time concept in automated systems, we propose as a second contribution a technique explicitly representing time in B event systems. This technique is based on an interleaving between any event handling time and the other system events. By considering the well known co-design technique, we propose as a third contribution a refinement-based composition technique keeping a separation between controller and controlled systems in order to build correct automated systems satisfying user requirements. We prove a compositionality theorem with respect to refinement to get an efficient approach to verify the refinement of a synchronized composition between components. We verify the refinement of a synchronized composition by verifying separately the refinement of each component. Finally, we define, prove and use in a case study as a fourth contribution the concept of a refinement pattern for continuous processes in manufacturing systems. Such proven pattern allows us to use the discrete abstraction of the effect of continuous processes operating for a while

Menée dans une perspective comparative, cette recherche a pour ambition une description du lexique des noms d’affect dans le but de relever des zones convergentes et des zones divergentes dans deux langues apparentées généalogiquement – le français et le roumain - selon deux axes de réflexion : l’analyse diachronique de la dynamique de l’évolution du lexique affectif roumain imprégné de mots d’origine française et l’analyse synchronique des particularités combinatoires des noms d’affect. Une telle recherche a mis en évidence des cas très intéressants, des points où les deux systèmes se rapprochent, sans pour autant coïncider totalement. Mais, malgré les petites différences morphosyntaxiques et combinatoires spécifiques attestées dans l’expression des affects, ces derniers présentent globalement une homogénéité du fonctionnement linguistique. Ce fait n’est pas seulement intéressant en termes de syntaxe comparée, mais aussi par le fait que les noms d’affect qui réalisent le même scénario cognitif ont un comportement similaire dans les deux langues confrontées. / Conducted in a comparative perspective, this research aims to describe the lexicon of affect nouns in order to underline the converging areas and diverging areas in two genealogically related languages - French and Romanian - in two lines of thought: diachronic analysis concerning the dynamics of the evolution of the Romanian emotional vocabulary permeated with words of French origin and synchronic analysis of combinatorial features of affect nouns. Such research has highlighted some very interesting cases, the points where these two systems are similar, but not completely coincide. But despite the small specific morphosyntactic and combinatorial differences evidenced in the expression of emotions, they generally bear homogeneity of linguistic functioning. This fact is not only interesting in terms of comparative syntax, but also by the fact that the affect nouns performing the same cognitive scenario have similar behavior in both languages faced.

Due to the significant limitations of static analysis and the dynamic nature of pointers in weakly typed programming languages like C and C++, the points-to sets obtained at compile time are quite conservative. Most static pointer analysis methods trade the precision for the analysis speed. The methods that perform the analysis in a reasonable amount of time are often context and/or flow insensitive. Other methods that are context, flow, and field sensitive have to perform the whole program inter-procedural analysis, and do not scale with respect to the program size. A large class of problems involving optimizations such as instruction prefetching, control and data speculation, redundant load/store instructions removal, instruction scheduling, and memory disambiguation suffer due to the imprecise and conservative points-to sets computed statically. One could possibly live without optimizations, but in domains involving memory security and safety, lack of the precise points-to sets can jeopardize the security and safety. In particular, the lack of dynamic points-to sets drastically reduce the ability to reason about a program's memory access behavior, and thus illegal memory accesses can go unchecked leading to bugs as well as security holes. On the other hand, the points-to sets can be very useful for other domains such as the heap shape analysis and garbage collection. The knowledge of precise points-to sets is therefore becoming very important, but has received little attention so far beyond a few studies, which have shown that the pointers exhibit very interesting behaviors during execution. How to track such behaviors dynamically and benefit from them is the topic covered by this research. In this work, we propose a technique to compute the precise points-to sets through dynamic pointer tracking. First, the compiler performs the pointer analysis to obtain the static points-to sets. Then, the compiler analyzes the program, and inserts the necessary instructions to refine the points-to sets. At runtime, the inserted instructions automatically update the points-to sets. Dynamic pointer tracking in software can be expensive and can be a barrier to the practicality of such methods. Several optimizations including removal of redundant update, post-loop update, special pattern driven update removal, pointer initialization update removal, update propagation, invariant removal, and on demand update optimization are proposed. Our experimental results demonstrate that our mechanism is able to compute the points-to sets dynamically with tolerable overheads. Finally, the memory protection and garbage collection work are presented as the consumers of dynamic pointer tracking to illustrate its importance. In particular, it is shown how different memory properties can be easily tracked using the dynamic points-to sets opening newer possibilities.