This paper deals with different variants of grammar systems. Grammar systems combine the simplicity of Context Free Grammars with the generative power of more complex gammars. There are two main variants of grammar systems described in this paper: PC grammar systems and CD grammar systems. New type of grammar system, which is a modification of the CD grammar systems, is also described in the paper.  New method of parsing, based on this new grammar system is proposed in the paper. This new parser consists of several smaller parsers, which work in both top down and bottom up way.

This thesis defines and studies two new types of automata, cooperating distributed pushdown automata systems (CDPDAS) and parallel communicating pushdown automata systems (PCPDAS).  CDPDAS and PCPDAS adapt the main concept of cooperating distributed grammar systems (CDGS) and parallel communicating automata systems (PCPDAS), respectively.  CDPDAS are proven to have the same power as PDA and this thesis further explores the reason why CDPDAS do not increase power while CDGS do and introduces an automata system inspired by CDPDAS that does increase the power.  PCGS have similar power as CDGS, but PCPDAS are equvalent with TM, which is proven by creating a communication protocol to access a second stack.

Lipids are the main component of semipermeable cell membranes and linked to several important physiological processes. Shotgun lipidomics relies on the direct infusion of total lipid extracts from cells, tissues or organisms into the mass spectrometer and is a powerful tool to elucidate their molecular composition. Despite the technical advances in modern mass spectrometry the currently available software underperforms in several aspects of the lipidomics pipeline. This thesis addresses these issues by presenting a new concept for lipid identification using a customized query language for mass spectra in combination with efficient spectra alignment algorithms which are implemented in the open source kit “LipidXplorer”.

This paper deals with decision problems related to the star problem in trace monoids, which means to determine whether the iteration of a recognizable trace language is recognizable. Due to a theorem by G. Richomme from 1994 [32, 33], we know that the star problem is decidable in trace monoids which do not contain a submonoid of the form {a,c}* x {b,d}*. Here, we consider a more general problem: Is it decidable whether for some recognizable trace language and some recognizable or finite trace language P the intersection R ∩ P* is recognizable? If P is recognizable, then we show that this problem is decidale iff the underlying trace monoid does not contain a submonoid of the form {a,c}* x b*. In the case of finite languages P, we show several decidability and undecidability results.

No description available.

Privacy regulations impose on companies limitations about the collection, use, and disclosure of user data. One of the actions most companies undertake for this, consists in modifying their systems with processes for consent acquisition and management. Unfortunately, where systems are large and with many dependencies, they often also have little documentation, and knowledge on the system is distributed among different domain experts. These circumstances make the re-engineering of systems a tedious and complex, if not impossible, activity. This PhD Thesis proposes a model-based method with a top-down approach, for modeling consent requirements and analyzing compliance with regulations, by refinement of models from organizational structure down to business processes. The method is provided with guidelines in the form of a process and includes modeling languages and reasoning frameworks for the analysis of requirements with respect to a preset of privacy principles on consent. The Thesis includes validations with realistic scenarios and with domain practitioners from the healthcare domain.

When students use an online eTextbook with content and interactive graded exercises, they often display aspects of two types of behavior: credit-seeking, and knowledge-seeking. Any given student might behave to some degree in either way in a given assignment. In this work, we look at multiple aspects of detecting the degree to which either behavior is taking place, and investigate relationships to student performance. In particular, we focus on an eTextbook used for teaching Formal Languages, an advanced computer science course. This eTextbook is using Programmed Instruction (PI) framesets to deliver the material. We take two approaches to analyze session interactions in order to detect credit-seeking incidents. We first start with a coarse-grained approach by presenting an unsupervised model that clusters the behavior in the work sessions based on the sequence of different interactions that happens during them. Then we perform a fine-grained analysis where we consider the type of each question in the frameset, which can be a multi-choice, single-choice, or T/F question. We show that credit-seeking behavior is negatively affecting the learning outcome of the students. We also find that the type of the PI frame is a key factor in drawing students more into the credit-seeking behavior to finish the PI framesets quickly. We implement three machine learning models that predict students' midterm and overall semester grades based on their amount of credit-seeking behavior on the PI framesets. Finally, we provide a semisupervised learning model to aid in the work session labeling process. / Master of Science / Students frequently exhibit features of two types of behavior when using an online eTextbook with content and interactive graded exercises: credit-seeking and knowledge-seeking. When solving homework or studying a material, students can behave in either manner to some extent. In this research, we study links between student performance and different elements of recognizing the degree to which either behavior is occurring. We concentrate on an eTextbook used to teach an advanced computer science course, Formal Languages and Automata, using a teaching paradigm called Programmed Instruction (PI). In order to detect credit-seeking instances, we use two ways to study students' behavior in the Programmed Instruction sessions. We begin with a coarse-grained approach by building a model that can categorize work sessions into two groups based on the interactions that occur throughout them. Then we do a fine-grained analysis in which we analyze the question types in the framesets and their effect on the students' behavior. We show that credit-seeking behavior has a negative effect on students' learning outcomes. We discovered that the PI frame type is an important factor in enticing students to engage in credit-seeking behavior in an attempt to finish PI framesets fast. Finally, we present three predictive models that can forecast the students' midterm and total semester grades based on their credit-seeking behavior on the Programmed Instruction framesets.

Cette thèse d'HDR en anglais, présente l'essentiel de mes travaux de 1996 à 2005. Voir le résumé anglais pour plus de détails.

L'interprétation abstraite est une méthode générale qui permet de déterminer de manière automatique des invariants de programmes. Cette méthode conduit à résoudre un problème de point fixe non linéaire de grande taille mais qui possède des propriétés de monotonie. Ainsi, déterminer des bornes sur les valeurs prises par une variable au cours de l'exécution d'un programme, est un problème de point fixe équivalent à un problème de jeu à deux joueurs, à somme nulle et avec options d'arrêt. Cette dernière observation explique la mise en oeuvre d'algorithmes d'itérations sur les politiques. Dans un premier temps, nous avons généralisé les domaines numériques polyédriques par un domaine numérique abstrait permettant de représenter des invariants non-linéaires. Nous avons défini une fonction sémantique abstraite sur ce domaine à partir d'une correspondance de Galois. Cependant, l'évaluation de celle-ci est aussi difficile qu'un problème d'optimisation globale non-convexe. Cela nous a amené à définir une fonction sémantique relâchée, construite à partir de la théorie de la dualité, qui sur-approxime de la fonction sémantique abstraite. La théorie de la dualité a également motivé une construction d'une itération sur les politiques dynamique pour calculer des invariants numériques. En pratique pour des programmes écrits en arithmétique affine, nous avons combiné la relaxation de Shor et l'information des fonctions de Lyapunov quadratique pour évaluer la fonction sémantique relâchée et ainsi générer des invariants numériques sous forme d'ellipsoïdes tronquées. Le deuxième travail concerne l'itération sur les politiques et le calcul du plus petit point fixe qui fournit l'invariant le plus précis. Nous avons raffiné l'itération sur les politiques afin de produire le plus petit point fixe dans le cas des jeux stochastiques. Ce raffinement repose sur des techniques de théorie de Perron-Frobenius non-linéaire. En effet, la fonction sémantique abstraite sur les intervalles peut être vue comme un opérateur de Shapley en information parfaite: elle est semidifférentiable. L'approche conjointe de la semidifférentielle et des rayons spectraux non linéaires nous a permis, dans le cas des contractions au sens large de caractériser le plus petit point fixe. Cette approche mène à un critère d'arrêt pour l'itération sur politique dans le cas des fonctions affines par morceaux contractantes au sens large. Quand le point fixe est non minimal, le problème consiste à exhiber un point fixe négatif non nul de la semidifférentielle. Ce vecteur conduit à une nouvelle politique qui fournit un point fixe strictement plus petit que le point fixe courant. Cette approche a été appliquée à quelques exemples de jeux stochastiques à paiements positifs et de vérification de programmes.

Concevoir et mettre en œuvre des méthodes pour la spécification, l'analyse et la vérification de logiciels et de systèmes sont les principaux moteurs des activités de recherche présentées dans ce manuscrit. Dans ce cadre, nos travaux se positionnent dans la catégorie dite des méthodes formelles appartenant à la communauté plus large du génie logiciel. A l'interface des travaux théoriques et applicatifs, notre objectif est de contribuer aux méthodes permettant d'assurer la correction et la sûreté des systèmes (fonctionnalité, sécurité, fiabilité, ...) en développant ou en améliorant des langages de spécification, des techniques et des outils permettant leur analyse formelle. Dans ce but, nous nous sommes attaché dans cette thèse à proposer et à étudier un cadre formel permettant la définition de politiques de sécurité et la vérification de leurs propriétés. A cet effet, nous avons proposé un cadre pour la spécification de politiques de sécurité basé sur une approche modulaire dans laquelle une politique est vue comme la composition d'un modèle de sécurité et d'une configuration. Nous avons investigué les possibilités offertes par de telles spécifications lorsque les modèles sont exprimés au moyen de contraintes du premier ordre et les configurations au moyen de programmes logiques. En particulier, nous avons proposé un algorithme permettant de transformer une politique exprimée dans un modèle donné vers une autre politique équivalente (au sens où elle engendre les mêmes autorisations) exprimée dans un autre modèle. Dans un second temps, nous nous sommes proposé de tenir compte des aspects dynamiques de la configuration d'une politique vue comme un état du système sur lequel la politique est mise en œuvre et où chaque action est associée à une procédure de modification des états. Nous avons proposé un langage formel simple pour spécifier séparément les systèmes et les politiques de sécurité puis avons donné une sémantique des spécifications exprimées dans ce cadre sous la forme de systèmes de réécriture. Nous nous sommes ensuite attachés à montrer que les systèmes de réécriture obtenus permettent l'étude de propriétés de sécurité. Dans une troisième partie, nous nous sommes focalisé sur les mécanismes permettant la mise en œuvre de politiques de sécurité dans les réseaux. Dans ce cadre, nous avons proposé une spécification des firewalls et de leurs compositions basée sur les automates d'arbres et les systèmes de réécriture puis avons montré en quoi ces spécifications nous permettent d'analyser de façon automatique les politiques de sécurité sous-jacentes.