L'objectif de cette thèse est de développer une sémantique d'ordre supérieur pour l'information quantique. S'appuyant sur les travaux de master (M.Sc.) de l'auteur, nous étudions un lambda-calcul pour le calcul quantique avec contrôle classique. Le langage comporte deux aspects. Le premier, émanant du théorème dit de « no-cloning » de l'information quantique, est le besoin de distinguer entre les données duplicables et celles non-duplicables. Pour tenir compte de la duplicabilité à l'ordre supérieur, nous utilisons un système de types inspiré par la logique linéaire, logique sensible à la notion de ressource. Le deuxième aspect important est l'effet de bord probabiliste émanant de la mesure, seule opération permettant de récupérer une information classique à partir de données quantiques. Cet effet de bord nous oblige à choisir une stratégie de réduction pour pouvoir être en mesure de définir une sémantique opérationnelle. Nous résolvons le problème de la sémantique dénotationnelle de deux façons. D'abord, en restreignant l'étude du langage au fragment strictement linéaire. Ce faisant, on supprime le besoin de distinguer entre structure duplicable et structure non-duplicable. Il est alors possible de se concentrer sur la description des caractéristiques du calcul quantique. En utilisant la catégorie des fonctions strictement positives (CPM), nous construisons un modèle dénotationnel « fully-abstract », c'est-à-dire caractérisant exactement l'équivalence opérationnelle du fragment strictement linéaire. L'étude du langage au complet est plus compliquée. Pour tenir compte de l'aspect probabiliste du langage, nous utilisons une méthode développée par Moggi et construisons un modèle distinguant la notion de résultat, ou valeur, de la notion de calcul (« computational model »). Pour traiter la distinction entre donnée duplicable et donnée non-duplicable, nous adaptons la notion de catégorie linéaire développée par Bierman, où la notion de duplication est interprétée comme une comonade avec des propriétés particulières. Le modèle issu de ce travail est ce que nous avons appelé une catégorie linéaire pour la duplication. Dans un dernier temps, le langage est restreint en ne considérant que la notion d'effet de bord et la distinction éléments duplicables – éléments non-duplicables pour obtenir un lambda-calcul linéaire générique. Dans ce contexte, nous montrons que la notion de catégorie linéaire de duplication est une interprétation « full and complete » pour le langage.

L'avancée technologique que les systèmes embarqués ont connue lors de ces dernières années les rend de plus en plus complexes. Ils sont non seulement responsables de la commande des différents composants mais aussi de leur surveillance. A l'occurrence d'événement pouvant mettre en danger la vie des utilisateurs, une certaine configuration du système est exécutée afin de maintenir le système dans un état dégradé mais sûr. Il est possible que la configuration échoue conduisant le système dans un état appelé " état redouté " avec des conséquences dramatiques pour le système et l'utilisateur. La description des scénarios qui mènent le système vers l'état redouté à partir d'un état de fonctionnement 'normal' permet de comprendre les raisons de la dérive afin de prévoir les configurations nécessaires qui permettent de les éviter Dans notre approche d'analyse de sûreté de fonctionnement des systèmes dynamiques, les scénarios sont générés à partir d'un modèle réseau de Petri. En s'appuyant sur la logique linéaire comme nouvelle représentation (basée sur les causalités) du modèle réseau de Petri, une analyse qualitative permet de déterminer un ordre partiel de franchissement des transitions et ainsi extraire les scénarios redoutés. La démarche est focalisée sur les parties du modèle intéressantes pour l'analyse de fiabilité évitant ainsi l'exploration de toutes les parties du système et le problème de l'explosion combinatoire. L'objectif final consiste en la détermination de scénarios minimaux. En effet, un scénario peut bien mener vers l'état redouté sans qu'il soit minimal. Il contient des événements qui ne sont pas strictement nécessaires à l'obtention finale de l'état critique redouté. De même que la notion de coupe minimale a été définie dans le cadre des arbres de défaillance, nous proposons une définition de ce qu'est un scénario minimal dans le cas des réseaux de Petri. Pour prendre en compte La nature hybride des systèmes, nous avons développé un simulateur hybride basé sur le couplage de l'algorithme de génération de scénarios redoutés avec un solveur d'équations différentielles. L'algorithme se charge de la partie discrète modélisée par le réseau de Petri et le solveur d'équations de la partie continue modélisée par un ensemble d'équations différentielles. Afin d'avoir une approche système pour l'analyse de la sûreté de fonctionnement, nous proposons une approche qui permet de prendre en compte les exigences de sûreté dans le processus d'ingénierie des exigences qui permet d'établir un modèle de traçabilité afin de s'assurer de la prise en compte de ces exigences tout au long du cycle de vie du système. L'approche est basée sur une norme de l'ingénierie système, en l'occurrence l'EIA-632.

L'objectif de cette thèse est de contribuer à l'élaboration de méthodes d'aide à la conception de systèmes coopératifs en prenant en compte les contraintes temporelles de manière quantitative. L'approche développée est fondée sur les réseaux de Petri, la logique linéaire et les graphes de contraintes temporelles. C'est une approche orientée « événements » et non orientée « états » comme c'est souvent le cas dans les approches fondées sur les réseaux de Petri. Elle est décomposée en deux étapes : une étape d'analyse « qualitative » et une étape d'analyse « quantitative ». La première consiste à obtenir les relations de causalité entre les événements appartenant à un scénario donné. L'équivalence entre un arbre de preuve en logique linéaire et le processus fini obtenu par dépliage d'un réseau de Petri à partir du même marquage initial montre que ces relations sont des relations de précédence. L'introduction de la notion de séquent caractéristique permet de mettre en Suvre une approche compositionnelle des processus à partir des règles du calcul des séquents. La deuxième étape consiste à passer du graphe décrivant les relations de précédence à un graphe de contraintes temporelles exprimant de façon linéaire l'ensemble des contraintes temporelles quantitatives que doivent vérifier les dates des franchissements des transitions dans un scénario. Il devient ainsi possible d'exploiter tous les résultats des techniques classiques d'analyse et de propagation de contraintes. Cette démarche est complètement cohérente avec les réseaux de Petri p-temporels mais difficilement compatible avec les t-temporels car ils engendrent des ensembles de contraintes qui sont plus complexes. Nous avons illustré cette démarche par un problème simple d'ordonnancement de documents multimédias. Nous avons par la suite montré comment, pour les réseaux de Petri t-temporels, nous pouvions calculer les dates de franchissements et les durées de séjour des jetons dans les places en restant sous une fo rme symbolique dans le cadre de la sémantique faible.

Dans le dernier siècle, nombreux sciences ont enrichi leur syntaxe pour pouvoir modeler des interactions. Entre eux on peut compter l'informatique, la physique quantique, et aussi la biologie et l’économie : toutes ces sciences sont des exemples de domaines qui ont besoin d'une syntaxe et d'une sémantique soit pour la concurrence que pour la séquentialité.Les diagrammes des cordes sont bien adapté à cet effet. Dans leur syntaxe on peut retrouver deux compositions : une composition parallèle et une composition séquentielle, qui peuvent interagir à travers une loi d'interchange. Si on considère cette loi comme une égalité, les diagrammes de cordes sont une syntaxe pour les catégories monoidales strictes, avec une représentation graphique plus intuitive que les formules algébriques traditionnelles.Dans cette thèse, on étude cette syntaxe de dimension 2 et sa sémantique. On considéré la réécriture des diagrammes et on donne des applications de cet méthode :- une preuve détaillée du théorème de cohérence de MacLanes pour les catégories monoidales symétriques basée sur un système de réécriture convergent donnée en arXiv:1606.01722;;- une interprétation des dérivations de preuves avec les diagrammes de preuve pour le fragment MELL de la logique linéaire, qui capture l’équivalence de preuves. On peut vérifier la séquentialité en temps linéaire, c'est à dire vérifier si un diagramme corresponds à une preuve. Cette interprétation est une extension de celle pour le fragment MLL donnée en arXiv:1606.09016 en donnant aussi un résultat de élimination du coupure. / In the last century, several sciences enriched their syntax in order to model interactions.Not only computer science and quantum physics, but also biology and economicsare examples of fields requiring syntax and semantics for concurrency as wellas for sequentiality.String diagrams are suitable for that purpose. In that syntax, we have two compositions:the parallel one and the sequential one, which may interact by the interchangerule. If we consider this rule as an equality, string diagrams are a syntax for strictmonoidal categories, with a more intuitive graphical representation than traditionalalgebraic formulas.In this thesis, we study this 2-dimensional syntax and its semantics. We considerdiagram rewriting and we give two applications of those methods:• a detailed proof of Mac Lane’s coherence theorem for symmetric monoidal categoriesbased on convergent diagram rewriting, which is given in arXiv:1606.01722;• an interpretation of proof derivations by string diagrams for the MELL fragmentof linear logic, which captures proof equivalence. We get a linear sequentializabilitytest to verify if a diagram corresponds to a proof . This interpretationextends the one for the MLL fragment given in arXiv:1606.09016,providing also a cut-elimination result.

Notre propos est la conception assistée par ordinateur des scénarios comprenant des contenus multimédia qui interagissent avec les actions extérieures, notamment celles de l’interprète (e.g., spectacles vivants, installations muséales interactives et jeux vidéo). Le contenu multimédia est structuré dans un ordre spatial et temporel selon les exigences de l’auteur. Par conséquent, la complexité potentiellement élevée de ces scénarios nécessite des langages de spécification adéquats pour leur complète description et vérification.Partitions Interactives est un formalisme qui a été proposé comme un modèle pour la composition et l’exécution des scénarios multimédias interactifs. En outre, un séquenceur inter-médias, appelé ISCORE,a été élaboré à partir de la sémantique Petri net proposée par ce formalisme. Au cours des dernières années, I-SCORE a été utilisé avec succès pour la composition et l’exécution des spectacles et des expositions interactives. Néanmoins, ces applications et les applications émergentes telles queles jeux vidéo et les installations muséales interactives, de plus en plus exigent deux caractéristiques que la version stable actuelle de I-SCORE ainsi que son modèle sous-jacent ne supportent pas : (1)des structures de contrôle flexibles comme des conditionnelles et des boucles ; et (2) des mécanismes pour la vérification automatique de scénarios.Dans cette thèse, nous présentons deux modèles formels pour la composition et la vérification automatique de scénarios interactifs multimédia avec des choix interactifs, i.e., des scénarios où l’interprète ou le système peut prendre des décisions au sujet de leur état d’exécution avec un certain degré de liberté définie par le compositeur.Dans notre première approche, nous définissons un nouveau langage de programmation appelé REACTIVEIS dont les programmes sont définis comme des arbres représentant l’aspect hiérarchique des scénarios interactifs et dont les noeuds contiennent les conditions nécessaires pour démarrer et arrêter les objets temporels (TOS). En outre, nous définissons une sémantique opérationnelle basé sur des arbres marqués, contenant dans leurs noeuds, les informations sur le début et la fin de chaque TO. Nous définissons également une interprétation déclarative de REACTIVEIS comme formules de la logique linéaire intuitionniste avec sous exponentiels (SELL). Nous montrons que cette interprétation est adéquate : les dérivations dans la logique correspondent à des traces du programme et vice-versa.Dans notre deuxième approche, nous présentons un système basé sur des Automates Temporisés.Dans le système proposé, nous modélisons des scénarios interactifs comme un réseau d’automates temporisés et les étendons avec des points interactifs gardés par des conditions, permettant ainsi la spécification de comportements avec branchements. Par ailleurs, nous profitons des outils matures et efficaces pour simuler et vérifier automatiquement des scénarios modélisés comme des automates temporisés. Dans notre système, les scénarios peuvent être synthétisés dans un matériel reconfigurable afin de fournir une faible latence et l’exécution en temps réel.Dans cette thèse, nous explorons également une nouvelle façon de définir et mettre en oeuvre des scénarios interactifs, visant à un modèle plus dynamique en utilisant le langage réactif REACTIVEML.Enfin, nous présentons une extension des scénarios interactifs utilisant des réseaux de Petri colorés(CPN) qui vise à traiter des données complexes, en particulier, les données statiques et dynamiques de flux audio. / Interactive multimedia deals with the computer-based design of scenarios consisting of multimediacontent that interacts with external actions and those of the performer (e.g., multimedialive-performance arts, interactive museum installations, and video games). The multimedia content is structured in a spatial and temporal order according to the author’s requirements. Therefore, thepotentially high complexity of these scenarios requires adequate specification languages for theircomplete description and verification.Interactive scores is a formalism which has been proposed as a model for composing and performing interactive multimedia scenarios. In addition, an inter-media sequencer, called I-SCORE, hasbeen developed following the Petri Net semantics proposed by this formalism. During the last years,I-SCORE has been used successfully for the composition and performance of live performances and interactive exhibitions. Nevertheless, these applications and emergent applications such as videogames and interactive museum installations, increasingly demand two features that the current stable version of I-SCORE as well as its underlying model do not support: (1) flexible control structures such as conditionals and loops; and (2) mechanisms for the automatic verification of scenarios.In this dissertation we present two formal models for composition and automatic verification of multimedia interactive scenarios with interactive choices, i.e., scenarios where the performer or thesystem can take decisions about their execution state with a certain degree of freedom defined bythe composer.In our first approach, we define a novel programming language called REACTIVEIS. This language extends the full capacity of temporal organization of interactive scenarios by allowing the composerto use a defined logical system for the specification of the starting and stopping conditions of temporal objects (TOs). REACTIVEIS programs are formally defined as tree-like structures representing the hierarchical aspect of interactive scenarios and whose nodes contain the conditions needed to startand stop the TOs. Moreover, we define an operational semantics based on labeled trees, containing in their nodes, the information about the start and stop times of each TO.We show that this operational semantics offers an intuitive yet precise description of the behavior of interactive scenarios.We also endowed REACTIVEIS with a declarative interpretation as formulas in Intuitionistic LinearLogic with Subexponentials (SELL). We shall show that such interpretation is adequate: derivations in the logic correspond to traces of the program and vice-versa. Hence, we can use all the meta-theory of Intuitionistic Linear Logic (ILL) to reason about interactive scenarios and develop tools for theverification and analysis of interactive scenarios.In our second approach, we present a Timed Automata (TA) based framework. In the proposed framework, we model interactive scenarios as a network of timed automata and extend them with interactive points (IPs) guarded by conditions, thus allowing for the specification of branching behaviors.Moreover, we take advantage of the mature and efficient tools for TA to simulate and automatically verify scenarios. In our framework, scenarios can be synthesized into a reconfigurable hardware in order to provide a low-latency and real-time execution by taking advantage of the physical parallelism,low-latency, and high-reliability of these devices. Furthermore, we implemented a tool to systematically construct bottom-up TA models from the composition environment of I-SCORE. Doing that, we provide a friendly and specialized environment for composing and automatic verification of interactive scenarios. Finally, we present an extension of interactive scenarios using Colored Petri Nets (CPNs) thataims to handle complex data, in particular, dynamic and static data audio streams. [...]

Cette thèse, s'intéresse aux systèmes d'interaction, une notion visant à modéliser les interactions entre un système informatique et son environnement.<br /><br />La première partie développe, dans le cadre de la théorie des types de Martin-Löf, la théorie de base des systèmes d'interaction et des constructions inductives et co-inductives qu'ils permettent. On trouve dans cette partie une étude des liens entre systèmes d'interaction et topologies formelles et une formulation (en terme de systèmes d'interaction) d'un théorème de complétude vis-à-vis d'une sémantique topologique des théories géométriques (linéaires).<br /><br />Dans cette étude, la notion complètement standard de simulation, joue un rôle fondamental car elle permet de définir la notion de morphisme entre systèmes d'interaction. Ceci permet d'établir une équivalence entre la catégorie ainsi définie et une autre catégorie, beaucoup plus simple à décrire, celle des transformateurs de prédicats.<br /><br />En traduisant dans ce nouveau vocabulaire les constructions précédentes, on observe que les transformateurs de prédicats forment un nouveau modèle de la logique linéaire, qui est décrit puis étendu au second ordre.<br /><br />Enfin, les propriétés particulières des systèmes d'interaction / transformateurs de prédicats sont mises à profit pour donner une interprétation du lambda-calcul différentiel. Cela suppose d'introduire du non déterminisme, ce que les systèmes d'interaction et les transformateurs de prédicats permettent de faire.

Les substitutions explicites ont été introduites comme un raffinement du lambda-calcul, celui-ci étant le<br />formalisme utilisé pour étudier la sémantique des langages de programmation. L'objet de cette thèse<br />est l'étude de leurs propriétés de normalisation forte et de préservation de la normalisation forte. Ce<br />manuscrit rend compte de plusieurs travaux autour de ces propriétés de normalisation, regroupés en<br />trois volets.<br /><br />Le premier d'entre eux formalise une technique générale de preuve de normalisation forte utilisant<br />la préservation de la normalisation forte. On applique cette technique à un spectre assez large de calculs<br />avec substitutions explicites afin de mesurer les limites de son utilisation. Grâce à cette technique, on<br />prouve un résultat nouveau : la normalisation forte du lambda-upsilon-calcul simplement typé.<br /><br />Le deuxième travail est l'étude de la normalisation d'un calcul symétrique non-déterministe issu de<br />la logique classique formulée dans le calcul des séquents, auquel est ajouté des substitutions explicites.<br />La conjonction des problèmes posés par les calculs symétriques et ceux posés par les substitutions<br />explicites semble vouer à l'échec l'utilisation de preuves par réductibilité. On utilise alors la technique<br />formalisée dans le premier travail, ce qui nous demande de prouver tout d'abord la préservation de la<br />normalisation forte. A cette fin, on utilise un fragment de la théorie de la perpétuité dans les systèmes<br />de réécriture.<br /><br />La définition d'une nouvelle version du lambda-ws-calcul avec nom, le lambda-wsn-calcul, constitue le troisième<br />volet de la thèse. Pour prouver sa normalisation forte par traduction et simulation dans les réseaux<br />de preuve, on enrichit l'élimination des coupures de ceux-ci avec une nouvelle règle, ce qui nous oblige<br />à prouver que cette nouvelle notion de réduction est fortement normalisante.

Lintégration progressive de lélectronique dans les secteurs automobile et avionique a amélioré le confort et les services rendus. Toutefois, cela a complexifié la conception des systèmes pilotés par calculateurs (systèmes mécatroniques, calculateurs de vol, etc.), ce qui rend difficile la maîtrise de leur fiabilité. Par ailleurs, la phase de conception doit être rapide et peu coûteuse (le moins de prototypes possible, le plus tard possible) avec un niveau de sécurité garantie. De plus, les ressources en moyens matériels étant limitées, pour des raisons de coûts et de mise en Suvre, les concepteurs évitent au maximum les redondances matérielles. Des études de Sûreté de Fonctionnement réalisées dès la phase de conception permettent une meilleure maîtrise des risques et de la fiabilité des systèmes conçus. En effet, les points faibles qui sont mis en évidence lors de lévaluation du niveau de sûreté des systèmes conçus permettent aux concepteurs de spécifier des stratégies de pilotage et des modes de reconfiguration avant les premiers essais sur un prototype réel. Les systèmes pilotés par calculateurs combinant des technologies mécaniques, hydrauliques, électroniques et informatiques sont hybrides: la dynamique continue est associée à la partie énergétique et la dynamique discrète est liée à la commande numérique et à lexistence dévénements discrets (défaillances, dépassements de seuils). Létude de la sûreté de fonctionnement de tels systèmes doit nécessairement tenir compte des interactions existantes entre leurs paramètres physiques (température, pression, vitesse&) et le dysfonctionnement de leurs composants. Les méthodes classiques de la sûreté de fonctionnement, comme les arbres de défaillances sont insuffisantes pour de tels systèmes complexes et hybrides car ils sont dynamiques. La sûreté de ces systèmes doit tenir compte du temps et de lordre dapparition des événements. La rareté de ces scénarios expose les méthodes basées seulement sur la simulation. au problème dexplosion combinatoire. Il existe en effet des techniques daccélération de la simulation, largement utilisées avec succès, dans lingénierie nucléaire notamment. Mes travaux de thèse sont placés dans le cadre de la fiabilité dynamique. Lobjectif est de réaliser une analyse qualitative de la sûreté de fonctionnement des systèmes pilotés par calculateurs pour extraire des scénarios menant à des états redoutés. Il sagit de caractériser ces scénarios au plus tôt dans la phase de conception, ce qui permet dévaluer leurs probabilités doccurrence pour valider larchitecture du système. Nous proposons une approche basée sur la logique linéaire et les Réseaux de Petri Prédicats Transitions Différentiels Stochastiques (RdP PTDS) qui garantissent le respect de la nature hybride de ces systèmes. Cette approche tient partiellement compte de laspect continu du système et plus particulièrement des seuils associés à certaines transitions dans le modèle RdP. Cela permet de déterminer plus précisément les conditions exactes de loccurrence de lévénement redouté : ce qui pousse le système à quitter son fonctionnement normal et à évoluer vers létat redouté. Loriginalité de notre approche est que lordre doccurrence des événements est pris en compte et les scénarios incohérents vis-à-vis de la dynamique continue du système sont éliminés. Notre approche est également orientée vers la vérification de certaines propriétés des systèmes pilotés par calculateur. Ces propriétés peuvent êtres de type temporel (la durée maximale dun scénario ou la durée entre deux commandes) ou de type accessibilité entre deux états. Lautomatisation de toutes les étapes de notre approche nous a paru indispensable dans le cas des systèmes complexes où le risque derreur humaine est très important. C'est pourquoi, j développé un outil ESA_PetriNet (Extraction & Scenarios Analyser by PetriNet model) qui permet dextraire les scénarios critiques qui mènent vers létat redouté à partir du n modèle Réseau de Petri temporel et de vérifier certaines propriétés des systèmes pilotés par calculateurs. null

Cette thèse, s'intéresse aux systèmes d'interaction, une notion visant à modéliser les interactions entre un système informatique et son environnement.<br /><br />La première partie développe, dans le cadre de la théorie des types de Martin-Löf, la théorie de base des systèmes d'interaction et des constructions inductives et co-inductives qu'ils permettent. On trouve dans cette partie une étude des liens entre systèmes d'interaction et topologies formelles et une formulation (en terme de systèmes d'interaction) d'un théorème de complétude vis-à-vis d'une sémantique topologique des théories géométriques (linéaires).<br /><br />Dans cette étude, la notion complètement standard de simulation, joue un rôle fondamental car elle permet de définir la notion de morphisme entre systèmes d'interaction. Ceci permet d'établir une équivalence entre la catégorie ainsi définie et une autre catégorie, beaucoup plus simple à décrire, celle des transformateurs de prédicats.<br /><br />En traduisant dans ce nouveau vocabulaire les constructions précédentes, on observe que les transformateurs de prédicats forment un nouveau modèle de la logique linéaire, qui est décrit puis étendu au second ordre.<br /><br />Enfin, les propriétés particulières des systèmes d'interaction / transformateurs de prédicats sont mises à profit pour donner une interprétation du lambda-calcul différentiel. Cela suppose d'introduire du non déterminisme, ce que les systèmes d'interaction et les transformateurs de prédicats permettent de faire.

Les travaux de cette thèse se situent dans le cadre de la linguistique computationnelle. La problématique est de définir une interface syntaxe / sémantique basée sur les théories de la grammaire générative.<br />Une première partie, concernant le problème de l'analyse syntaxique, présente tout d'abord, la syntaxe générative, puis un formalisme la réalisant: les grammaires minimalistes de Stabler. <br />À partir de ces grammaires, nous réalisons une étude sur les propriétés de l'opération de fusion pour laquelle nous définissons des notions d'équivalence, ainsi qu'une modélisation abstraite des lexiques.<br />Une seconde partie revient sur le problème de l'interface. Pour cela, nous proposons un formalisme de type logique, basé sur la logique mixte (possédant des connecteurs commutatifs et non-commutatifs), qui équivaut, sous certaines conditions, aux grammaires de Stabler. <br />Dans ce but, nous introduisons une normalisation des preuves de cette logique, normalisation permettant de vérifier la propriété de la sous-formule. Ces propriétés sont également étendues au calcul de Lambek avec produit.<br />À partir de l'isomorphisme de Curry-Howard, nous synchronisons un calcul sémantique avec les preuves réalisant l'analyse syntaxique. Les termes de notre calcul font appel aux propriétés du lambda mu-calcul, ainsi qu'à celles de la DRT (Discourse Representative Theory).<br />Une dernière partie applique ces formalismes à des cas concrets. Nous établissons des fragments d'une grammaire du français autour du problème des clitiques.