Search

We introduce a new formalisation of languages, called keyboards. We consider a set of elementary operations (writing/erasing a letter, going to the right or to the left,...) and we define a keyboard as a set of finite sequences of such operations, called keys. The corresponding language is the set of words obtained by applying some sequence of those keys. Unlike classical models of computation, every key can be applied anytime. We define various classes of languages based on different sets of elementary operations, and compare their expressive powers. We also compare them to well-known classes of languages (Chomsky hierarchy). We obtain a strict hierarchy of languages, whose expressivity is orthogonal to the one of the aforementionned classical models. -- Nous introduisons une nouvelle repr\'esentation de langages, les claviers. On se munit d'un ensemble d'op\'erations \'el\'ementaires (ajout, effacement d'une lettre, d\'eplacement \`a droite, \`a gauche, ...), et on d\'efinit un clavier comme un ensemble de suites finies d'op\'erations \'el\'ementaires, appel\'ees touches. Son langage sera l'ensemble des mots obtenus en appliquant une suite quelconque de touches. Contrairement \`a des mod\`eles de calcul classiques, toutes les touches peuvent \^etre appliqu\'ees \`a tout moment. En premier lieu nous d\'efinissons diff\'erentes classes de claviers en faisant varier l'ensemble des op\'erations \'el\'ementaires autoris\'ees, et nous comparons l'expressivit\'e des classes de langages obtenues. Nous comparons \'egalement ces classes \`a la hi\'erarchie de Chomsky. Nous obtenons que toutes les classes \'etudi\'ees sont diff\'erentes, et nous caract\'erisons les classes inclues dans les rationnels et les alg\'ebriques. L'expressivit\'e des claviers semble orthogonale \`a celle des mod\`eles \'evoqu\'es pr\'ec\'edemment., Comment: Two versions, in French and in English

Il importe de bien situer la tâche du traducteur pour en saisir les enjeux et la dignité. Les conceptions vulgaires de la traduction en font le transfert d’un message formulé en quelque code vers un autre code, le message restant essentiellement le même. Or Walter Benjamin a fourni un paradigme qui permet de penser autrement la traduction et le rapport entre les idiomes. Selon lui, le soi-disant message n’a pas d’existence en-dehors de son expression langagière et le fait de la traduction est plutôt le symptôme d’un creux au beau milieu de la ronde que les langues forment dès lors que l’activité de la traduction s’installe parmi les humains. Ce creux définit dès lors le lieu de l’indicible qu’il importe donc de penser dans son rapport au dire. Ce modèle permet d’élaborer une pensée du trauma et de son rapport à la diversité des langues ; il valorise la tâche du traducteur et de son désir au passage d’un dire vers l’autre et la replace au milieu du concert des langues ; il en souligne le rôle culturel et humain irréductible qui ne saurait être rempli par quelque procédé automatisé que ce soit. Walter Benjamin hat in seinem Beitrag über die Aufgabe des Übersetzers ein Modell geliefert, an dessen Hand die Übersetzung jenseits ihrer Trivialisierung als Herstellung eines äquivalenten Ausdrucks desselben Inhaltes in einem anderen Idiom begriffen werden kann. Nach Benjamin hat die Botschaft diesseits ihres sprachlichen Ausdruckes keine Existenz, so dass die Vielheit der Sprachen und die bloße Existenz des Problems der Übersetzung Anzeige tut auf einen Bereich, der, inmitten des Reigens der Sprachen liegend, strukturell von keiner erreicht zu werden vermag. Dieser Bereich kann als der Ort des Unsäglichen verstanden werden und bietet damit ein Modell zur Erklärung des Traumas und seiner Beziehung zur Vielfalt der Sprachen. Umgekehrt erlaubt es, das Übersetzen als eine Arbeit zu würdigen, die, wenn sie ihre wesentliche Aufgabe für die menschliche Gemeinschaft erfüllen soll, unbedingt von menschlichen Subjekten verrichtet werden muss und durch kein technisches Dispositiv ersetzt werden darf. Walter Benjamin has provided a model through his contribution to the task of the translator, through which the translation can be understood beyond its trivialization as a producer of an equivalent expression of equal content in a different idiom. According to Benjamin the message doesn’t have an existence beyond its spoken expression, so that the plurality of languages and the sole existence of the problem of translation both point towards a space that lies in the midst of languages, but which remains structurally unreachable by any. This space can be understood as the place of the unspeakable and it therefore provides a model for the explanation of trauma and its relationship to the plurality of languages. It allows for translation to be respected as a work, which, if it should fulfil its basic task for the human community, must be exercised by human subjects and cannot be replaced by a technical device.

Current musical improvisation systems are able to generate unidimensional musical sequences by recombining their musical contents. However, considering several dimensions (melody, harmony...) and several temporal levels are difficult issues. In this thesis, we propose to combine probabilistic approaches with formal language theory in order to better assess the complexity of a musical discourse, both from a multidimensional and multi-level point of view in the context of improvisation where the amount of data is limited. First, we present a system able to follow the contextual logic of an improvisation modelled by a factor oracle whilst enriching its musical discourse with multidimensional knowledge represented by interpolated probabilistic models. Then, this work is extended to create another system using a belief propagation algorithm representing the interaction between several musicians, or between several dimensions, in order to generate multidimensional improvisations. Finally, we propose a system able to improvise on a temporal scenario with multi-level information modelled with a hierarchical grammar. We also propose a learning method for the automatic analysis of hierarchical temporal structures. Every system is evaluated by professional musicians and improvisers during listening sessions; Les systèmes actuels d’improvisation musicales sont capables de générer des séquences musicales unidimensionnelles par recombinaison du matériel musical. Cependant, la prise en compte de plusieurs dimensions (mélodie, harmonie...) et la modélisation de plusieurs niveaux temporels sont des problèmes difficiles. Dans cette thèse, nous proposons de combiner des approches probabilistes et des méthodes issues de la théorie des langages formels afin de mieux apprécier la complexité du discours musical à la fois d’un point de vue multidimensionnel et multi-niveaux dans le cadre de l’improvisation où la quantité de données est limitée. Dans un premier temps, nous présentons un système capable de suivre la logique contextuelle d’une improvisation représentée par un oracle des facteurs tout en enrichissant son discours musical à l’aide de connaissances multidimensionnelles représentées par des modèles probabilistes interpolés. Ensuite, ces travaux sont étendus pour modéliser l’interaction entre plusieurs musiciens ou entre plusieurs dimensions par un algorithme de propagation de croyance afin de générer des improvisations multidimensionnelles. Enfin, nous proposons un système capable d’improviser sur un scénario temporel avec des informations multi-niveaux représenté par une grammaire hiérarchique. Nous proposons également une méthode d’apprentissage pour l’analyse automatique de structures temporelles hiérarchiques. Tous les systèmes sont évalués par des musiciens et improvisateurs experts lors de sessions d’écoute

Amongst the classical results of the language theory, one can cite the known characterization of algebraic languages proved by Chomsky and Schützenberger and which states that a language is algebraic if and only if it is the homomorphic image of a regular set intersected with the Dyck language. This result has opened a new line of research and defined a new type of characterizations known as \emph{representation theorems}. In this thesis, we prove various representation theorems for the higher order languages hierarchy. In particular, we introduce a notion of higher order Dyck languages and a hierarchy of classes of transductions that we call $\varepsilon$-stable (or $\varepsilon$-safe) transductions and we prove that a language belongs to some level $k+l$ of the higher order hierarchy if and only if it can be represented as the image of a level-$k$ Dyck language by a level-$l$ $\varepsilon$-stable transduction. These representations also allow us to approach other types of characterizations such as logical characterizations.; Une ligne de recherche présente dans la littérature depuis les années soixante est celle des \emph{théorèmes de représentation}. Son résultat fondateur est le théorème de Chomsky--Schützenberger qui stipule qu'un langage est algébrique si et seulement si il est l'image par homomorphisme de l'intersection entre un langage régulier et le langage de Dyck. Ce résultat a connu depuis diverses généralisations à différentes familles de langages. Dans cette thèse, nous proposons plusieurs généralisations de ce résultat aux langages d'ordres supérieurs. En particulier, nous introduisons une notion de langages de Dyck d'ordres supérieurs, nous définissons et étudions des classes de transductions que nous qualifions d'$\varepsilon$-sûres et nous montrons qu'un langage appartient à un niveau $k+l$ de la hiérarchie des ordres supérieurs si et seulement si il est l'image d'un langage de Dyck de niveau $k$ par une transductions $\varepsilon$-sûre de niveau $l$. Ces résultats nous permettent aussi d'obtenir d'autres types de caractérisations tels que des caractérisations logiques.

In order to facilitate the engineers task of evaluating the fire safety level, and to allow the specialists involved in the field to use their preferred languages and tools, we propose to create a language dedicated to the field of fire safety, which automatically generates a simulation, taking into account the specific languages used by the specialists involved in the field. This DSL requires the definition, the formalization, the composition and the integration of several models, regardig to the specific languages used by the specialists involved in the field. The specific language dedicated to the field of fire safety is designed by composing and integrating several other DSLs described by technical and natural languages (as well as natural languages referring to technical ones). These latter are modeled in a way that their components must be precise and based on mathematical foundations, in order to verify the consistency of the system (people and materials are safe) before it implementation. In this context, we propose to adopt a formal approach, based on algebraic specifications, to formalize the languages used by the specialists involved in the generation system, focusing on both syntaxes and semantics of the dedicated languages. In the algebraic approach, the concepts of the domain are abstracted by data types and the relationships between them. The semantics of specific languages is described by the relationships, the mappings between the defined data types and their properties. The simulation language is based on a composition of several specific DSLs previously described and formalized. The DSLs are implemented based on the concepts of functional programming and the Haskell functional language, well adapted to this approach. The result of this work is a software dedicated to the automatic generation of a simulation, in order to facilitate the evaluation of the fire safety level to the engineers. This tool is the property of the Scientific and Technical Center for Building (CSTB), an organization whose mission is to guarantee the quality and safety of buildings by combining multidisciplinary skills to develop and share scientific and technical knowledge, in order to provide to the different actors the expected answers in their professional practice.; Dans le but de faciliter la tâche d'évaluation du niveau de sécurité incendie aux ingénieurs et permettre aux spécialistes impliqués dans le domaine d'utiliser leurs langages et outils préférés, nous proposons de créer un langage dédié au domaine de la sécurité incendie générant automatiquement une simulation en prenant en considération les langages métiers utilisés par les spécialistes intervenants dans le domaine. Ce DSL nécessite la définition, la formalisation, la composition et l'intégration de plusieurs modèles, par rapport aux langages spécifiques utilisés par les spécialistes impliqués dans le domaine. Le langage spécifique dédié au domaine de la sécurité incendie est conçu par composition et intégration de plusieurs autres DSLs décrits par des langages techniques et naturels (ainsi que des langages naturels faisant référence à des langages techniques). Ces derniers sont modélisés de manière à ce que leurs composants soient précis et fondés sur des bases mathématiques permettant de vérifier la cohérence du système (personnes et matériaux sont en sécurité) avant sa mise en œuvre. Dans ce contexte, nous proposons d'adopter une approche formelle, basée sur des spécifications algébriques, pour formaliser les langages utilisés par les spécialistes impliqués dans le système de génération, en se concentrant à la fois sur les syntaxes et les sémantiques des langages dédiés. Dans l'approche algébrique, les concepts du domaine sont abstraits par des types de données et les relations entre eux. La sémantique des langages spécifiques est décrite par les relations, le mapping (correspondances) entre les types de données définis et leurs propriétés. Le langage de simulation est basé sur un langage conçu par la composition de plusieurs DSL spécifiques précédemment décrits et formalisés. Les différents DSLs sont implémentés en se basant sur les concepts de la programmation fonctionnelle et le langage fonctionnel Haskell bien adapté à cette approche. Le résultat de ce travail est un outil informatique dédié à la génération automatique de simulation, dans le but de faciliter la tâche d'évaluation du niveau de sécurité incendie aux ingénieurs. Cet outil est la propriété du Centre Scientifique et Technique du bâtiment (CSTB), une organisation dont la mission est de garantir la qualité et la sécurité des bâtiments, en réunissant des compétences multidisciplinaires pour développer et partager des connaissances scientifiques et techniques, afin de fournir aux différents acteurs les réponses attendues dans leur pratique professionnelle.

We study the notion of quasiperiodicity, introduced by Apostolico and Ehrenfeucht at the beginning of the 1990's, then extended to infinite words by Solomon Marcus at the beginning of the 2000's. A (finite or infinite) word w is quasiperiodic if it can be covered by occurrences, possibly overlapping, of another finite word, call its quasiperiod. In 2006, Monteil and Marcus introduced a stronger notion: multi-scale quasiperiodicity, the property of having infinitely many quasiperiods.First we study quasiperiodicity of two-dimensional infinite words. We show that, by contrast with the one-dimensional case where quasiperiodicity do not force any property on infinite words, there exist quasiperiods q which force 2D q-quasiperiodic words to have zero entropy. We also show that multi-scale quasiperiodicity in two dimension force the existence of uniform frequencies for factors.Then we give results on infinite words in one dimension. Most notably we give a method to determine the quasiperiods of an infinite words from its square and special factors. We show that the family of periodic words and standard Sturmian words are characterizable in terms of multi-scale quasiperiodicity.; Nous étudions dans cette thèse la notion de quasipériodicité,introduite par Apostolico et Ehrenfeucht au début des années 1990,puis étendue aux mots infinis par Solomon Marcus au début des années2000. Un mot (fini ou infini) w est quasipériodique s'il peut êtrecouvert par des occurrences, éventuellement chevauchantes, d'un autremot, fini, appelé sa quasipériode. En 2006, Monteil etMarcus ont introduit la notion plus forte de quasipériodicitémulti-échelles : le fait d'avoir une infinité de quasipériodes.Dans un premier temps, nous étudions la quasipériodicité des motsinfinis bidimensionnels. Nous montrons que, contrairement au casunidimensionnel où la quasipériodicité ne force aucune propriété fortedes mots infinis, il existe des quasipériodes q qui forcent les mots2D q-quasipériodiques à être d'entropie nulle. Nous montrons égalementque la quasipériodicité multi-échelles en deux dimensions forcel'existence de fréquences uniformes pour les facteurs.Dans un deuxième temps, nous donnons des résultats sur les motsinfinis en une dimension. Nous donnons notament une approchepermettant de déterminer les quasipériodes d'un mot infini à partir deses facteurs carrés et de ses facteurs spéciaux. Nous montrons ensuiteque la famille des mots périodiques, ainsi que celle des mots standardsturmiens, peuvent être caractérisées en termes de quasipériodicitémulti-échelles.

We study the notion of quasiperiodicity, introduced by Apostolico and Ehrenfeucht at the beginning of the 1990's, then extended to infinite words by Solomon Marcus at the beginning of the 2000's. A (finite or infinite) word w is quasiperiodic if it can be covered by occurrences, possibly overlapping, of another finite word, call its quasiperiod. In 2006, Monteil and Marcus introduced a stronger notion: multi-scale quasiperiodicity, the property of having infinitely many quasiperiods.First we study quasiperiodicity of two-dimensional infinite words. We show that, by contrast with the one-dimensional case where quasiperiodicity do not force any property on infinite words, there exist quasiperiods q which force 2D q-quasiperiodic words to have zero entropy. We also show that multi-scale quasiperiodicity in two dimension force the existence of uniform frequencies for factors.Then we give results on infinite words in one dimension. Most notably we give a method to determine the quasiperiods of an infinite words from its square and special factors. We show that the family of periodic words and standard Sturmian words are characterizable in terms of multi-scale quasiperiodicity.; Nous étudions dans cette thèse la notion de quasipériodicité,introduite par Apostolico et Ehrenfeucht au début des années 1990,puis étendue aux mots infinis par Solomon Marcus au début des années2000. Un mot (fini ou infini) w est quasipériodique s'il peut êtrecouvert par des occurrences, éventuellement chevauchantes, d'un autremot, fini, appelé sa quasipériode. En 2006, Monteil etMarcus ont introduit la notion plus forte de quasipériodicitémulti-échelles : le fait d'avoir une infinité de quasipériodes.Dans un premier temps, nous étudions la quasipériodicité des motsinfinis bidimensionnels. Nous montrons que, contrairement au casunidimensionnel où la quasipériodicité ne force aucune propriété fortedes mots infinis, il existe des quasipériodes q qui forcent les mots2D q-quasipériodiques à être d'entropie nulle. Nous montrons égalementque la quasipériodicité multi-échelles en deux dimensions forcel'existence de fréquences uniformes pour les facteurs.Dans un deuxième temps, nous donnons des résultats sur les motsinfinis en une dimension. Nous donnons notament une approchepermettant de déterminer les quasipériodes d'un mot infini à partir deses facteurs carrés et de ses facteurs spéciaux. Nous montrons ensuiteque la famille des mots périodiques, ainsi que celle des mots standardsturmiens, peuvent être caractérisées en termes de quasipériodicitémulti-échelles.

A lot of research work have focused on how to design, program and verify functional concerns for critical systems. However, critical interactive systems did not benefit from the same attention and efforts. The first part of this thesis is an attempt to analyze the causes that led to this situation. A set of requirements for a new approach are detailed. The rest of the thesis is an attempt at finding solutions that fulfill these requirements.First, a model of architecture for interactive systems is proposed. This model uses basics elements called interactors, and tries to allow the expression of two orthogonal concerns about them: the notion of abstraction level and the notion of architectural composition of systems. Then, most of this thesis is dedicated to the presentation of a language called LIDL (LIDL Interaction Description Language), which aims at enabling a formal description of interactors. Static aspects of interactors are specified using interfaces, while dynamic aspects of interactors are specified using interactions. Semantics for LIDL are based on a set of six basic interactions and a way to compose them. Like Lustre, LIDL semantics are based on synchronous data flows: each interaction represents a data flow. Flows include a notion of activation, which denotes the presence or absence of data, in an attempt to allow the description of flow-based and event-based interaction systems. The formalization of LIDL semantics aims at providing a starting point for the application of techniques enabling verification of properties of LIDL interactive systems. Finally, these concepts are put to use on a case study. The compliance of this approach with the requirements is examined., La spécification, la programmation et la vérification de systèmes critiques ont fait l’objet d’importants efforts de recherche. Le domaine des systèmes interactifs, et plus particulièrement celui des applications logicielles interactives critiques, n’a pas du tout bénéficié des mêmes efforts. Or, paradoxalement, l'accidentologie aéronautique fait clairement apparaître que le bon fonctionnement de ces applications est mis en cause de manière récurrente dans l'ensemble des accidents ou incidents recensés.La thèse analyse d'abord les causes de ce paradoxe et de cet état de fait. Cette analyse conduit à formuler et détailler un ensemble d’exigences pour une nouvelle approche de spécification et conception de ces applications. La thèse propose ensuite, en s'inscrivant dans la recherche de réponses satisfaisantes à ces exigences, les bases d'un langage permettant de décrire la composition et le comportement attendu de ces applications. Pour ce faire, un modèle d’architecture de systèmes interactifs est avancé. Il se fonde sur des composants de base, les interacteurs, et décrit, les concernant, les notions d'abstraction et de composition de systèmes. Le langage LIDL (LIDL Interaction Description Language), proposition centrale de la thèse, permet de décrire formellement les interacteurs de ce modèle. Leur composante statique est décrite sous la forme d’interfaces. Leurs composantes dynamiques sont décrites sous la forme d’interactions. Une description LIDL se construit sur un ensemble réduit d’interactions de base ainsi que sur quelques constructeurs du langage permettant de les composer. LIDL est un langage à flot de données synchrones qui décrivent les interactions. Les flots intègrent une donnée d’activation, qui dénote la présence ou l’absence de valeur du flot. La compilation de descriptions LIDL permet de produire des machine d'états se prêtant bien aux techniques de vérification formelle. L’adéquation de l’approche et du langage proposés avec les exigences identifiées au départ est finalement examinée à travers leur mise en œuvre sur un cas d'étude.

Why naïve semantics cannot be formalized and why this is (almost) of no consequence for ontology engineering. The project of representing the semantics of human concepts using formal languages is not new, but it currently knows a renewed interest with computational ontologies. The main objective of these representation systems, which constitute one essential component of the semantic Web, is to provide machines with “ awareness” of the meaning of the data being processed. Formal languages have always been criticized and their use in ontology engineering is no exception. Various authors denounce this attempt to subject our naive semantics to logical formalisms, which are too strict and too mechanical to capture its expressiveness and adaptability, and propose alternative approaches and models, supposedly closer to “ natural” humanconceptualization and representation mechanisms. The purpose of the present article is to demonstrate that those criticisms are mostly ill-founded, and in any case irrelevant, in the sense that they assume the subordination of ontologies to epistemic requirements (to model faithfully a referent) rather than operational requirements (to be efficient and fulfil needs). They become inappropriate from the moment that one considers that the function of ontologies is not (i) to represent faithfully the furniture and the constituent structures of the reality (realism) or how the mind represents that reality (conceptualism), but (ii) to improve the capacity of categorization, access to information and manipulation of data and documents, and (iii) to standardize practices of categorization and encoding. Based on this conception, a new epistemological approach to computational ontologies can be proposed : instrumentalism., Le projet de représenter la sémantique des termes et concepts humains à l’aide de langages formels ne date pas d’hier, mais il connait aujourd’hui un regain d’intérêt avec le développement des ontologies computationnelles. Fer de lance du Web sémantique, la principale ambition de ces systèmes de représentation est de permettre aux machines d’accéder au «sens » des données qu’elles manipulent. Les langages formels ont toujours eu leurs détracteurs et l’usage qui en est fait en ingénierie ontologique ne fait pas exception. Différents auteurs dénoncent le projet de soumettre notre sémantique naïve à des formalismes logiques, trop rigides et trop mécaniques pour en capter la mobilité et l’adaptabilité, et proposent de leur substituer des approches et modèles alternatifs, censés être plus proches des mécanismes de conceptualisation et de représentation «naturels » de l’humain. L’objet de cet article est de montrer que ces critiques sont pour la plupart infondées, et en tout cas hors sujet, en ce qu’elles présupposent la subordination des ontologies à une exigence épistémique (modéliser de manière fidèle un référent) plutôt qu’opérationnelle (fonctionner et rendre service). Elles perdent leur raison d’être dès lors que l’on considère que la fonction des ontologies n’est pas (i) de représenter de manière fidèle le mobilier et les structures constitutives de la réalité (réalisme) ou la manière dont l’esprit se représente cette réalité (conceptualisme), mais (ii) d’augmenter les capacités de catégorisation, d’accès à l’information et de manipulation de données et documents, et (iii) de normaliser les pratiques de catégorisation et d’encodage. Considérer les ontologies computationnelles dans la perspective de l’augmentation cognitive et de l’instrumentation des pratiques exige un nouveau cadre épistémologique pour leur conception. Nous en décrivons ici les principes de base et proposons de qualifier cette nouvelle approche d’instrumentaliste., Declerck Gunnar, Charlet Jean. Pourquoi notre sémantique naïve n’est pas formalisable et pourquoi c’est (presque) sans conséquence sur l’ingénierie ontologique. In: Intellectica. Revue de l'Association pour la Recherche Cognitive, n°61, 2014/1. Philosophie du Web et Ingénierie des Connaissances. pp. 143-188.

Colorings of the discrete plane (i.e., tilings) are a geometrical model which is intimately linked with computability theory. We show in this manuscript how many recent results in tiling theory can be unified through the concept of basis and antibasis: A property P is a basis if any tiling space contains a point with property P. We then discuss the various ways to encode computation in tilings. We introduce a new encoding that gave a sparse grid, and explain how to characterize Turing degrees of tilings using this grid. Finally we discuss tilings for the point of view of model theory. We characterize various important classes of tilings by logical fragments of monadic second order theory, Les travaux présentés ici s'intéressent aux coloriages du plan discret. Ce modèle d'inspiration géométrique est intrinsèquement lié aux modèles de calcul, et son étude se décline ici suivant deux axes complémentaires: calculabilité et combinatoire. Nous montrons en particulier ici comment de nombreux résultats récents s'expriment naturellement à travers le concept de bases, propriétés vérifiées par au moins un point de tout ensemble de coloriages, et d'antibases, contre-exemples à ce concept. Nous examinons ensuite les différents codages du calcul par des jeux de tuiles et exhibons en particulier un nouveau codage épars, permettant de caractériser les degrés Turing des ensembles de coloriages. Enfin nous revenons aux origines en étudiant les pavages du point de vue de la logique. Nous caractérisons ainsi les grandes familles d'ensembles de coloriages par des fragments de la logique monadique du second ordre.

Formal languages are sequences of symbols in some discrete set called alphabet. They are often specified by formulas in some logic, by rational expressions or else by discrete automata of various types. Current theory is mostly qualitative, in the sense that its objects are sequences over a discrete, non-metric, time, that acceptation of a sequence over an automaton depends on whether an accepting state is visited or not, and that, for language comparison, one will most often consider inclusion than quantitative measures. This thesis contributes to the study of these often neglected aspects by presenting fundamental results in three new quantitative problem classes about formal languages. In the first chapter, we study a class of scheduling problems which combines structural aspects related to dependencies between tasks with dynamical aspects of online scheduling. We show that some task request streams in this class of problems, however admissible in the sense that they do not require more raw resource utilization than available machines can provide, cannot be scheduled with bounded latency. However, we develop a scheduling policy which can guarantee a bounded backlog accumulation for all admissible streams even without knowledge of the stream content prior to execution. We show that if the streams actually are sub-critical, then the same policy also guarantees a bounded latency. In quantitative verification, states and transitions of a system can be endowed with costs, which can be used to associate average costs to infinite behaviors. In this second part, we propose to define omega-languages thanks to Boolean queries concerning average costs. Specifications dealing with averages, such as "average message loss is under some threshold" are not omega-regular, but can be expressed in our model. Hence we study expressive power and Borel complexity of such specifications. We show that in order to ensure closure by intersection, multi-dimensional costs have to be considered. In the general case, we show that accepting conditions can be defined on the set of accumulation points of the sequence of the average costs of the prefixes of a run. We accurately characterize such sets. Last, we also propose a class of multi-threshold mean-payoff languages, in which extremal values of coordinates of points of the accumulation set are compared to constants. We show this class is closed under Boolean operations and analyzable. In the last chapter, we define two measures for a timed language: the volume of its sub-languages of words having a fixed number of discrete events, and entropy, which is the asymptotic logarithmic growth of volumes. These measures can be used to compare languages quantitatively and entropy can be seen as information content of a typical event of a typical word of in a language. For languages accepted by deterministic timed automata, we give an exact formula for the volume. Next we characterize entropy, thanks to functional analysis techniques, as the logarithm of the spectral radius of some positive integral operator. We give several methods to compute entropy: a symbolical one for the special case of "one clock and a half" automata, and two numerical ones: one using functional analysis, the other using discretization techniques. Last we establish an interpretation of this entropy in information theory by showing its relation with Kolmogorov complexity., Les langages formels sont des séquences sur un ensemble discret de symboles appelé alphabet. On les spécifie souvent par des formules dans une certaine logique, par des expressions rationnelles ou bien par des automates discrets de types variés. La théorie actuelle est principalement qualitative, dans le sens où ses objets sont des séquence sur un temps discret, non-métrique, dans le sens où l'acceptation d'une séquence sur un automate dépend du fait que l'on visite ou non un état accepteur, et enfin dans le sens où la comparaison de langages est plus souvent considérée en termes d'inclusion, plutôt qu'en termes de mesures quantitatives. Cette thèse contribue à l'étude de ces aspects souvent négligés en présentant des résultats fondamentaux dans trois nouvelles classes de problèmes quantitatifs sur les langages formels. Dans la première partie, nous étudions une classe de problèmes d'ordonnancement qui combine les aspects structurels associés aux dépendances entre tâches avec les aspects dynamiques liés au fait qu'un flux de requêtes arrive en continu pendant l'exécution. Nous montrons que, dans cette classe de problèmes, certains flux, pourtant admissibles dans le sens que les requêtes ne représentent pas plus de travail que ce que les machines peuvent traiter, ne peuvent pas être ordonnancé avec une latence bornée. Cependant nous développons une politique d'ordonnancement que peut garantir une accumulation de retard bornée pour tout flux de requêtes admissible, même sans le connaître à l'avance. Nous montrons que si les flux sont sous-critiques, alors cette même politique peut garantir une latence bornée. En vérification quantitative, les états et transitions d'un système peuvent être associés à des coûts, et ceux-ci utilisés pour associer des coûts moyens aux comportements infinis. Dans cette seconde partie, nous proposons de définir des omega-langages par des requêtes booléennes sur les coûts moyens. Des spécifications concernant des moyennes, tels que " le taux de perte moyen de messages est inférieur à un certain seuil " ne sont pas omega-régulières, mais exprimables dans notre modèle. Ainsi, nous étudions l'expressivité et la complexité de Borel de telles spécifications. Nous montrons que pour la clôture par intersection, il est nécessaire de considérer des coûts multi-dimensionnels. Nous mettons en évidence que dans le cas général, les conditions d'acceptation portent sur l'ensemble des points d'accumulation de la séquence des coûts moyens des préfixes d'une exécution, et nous donnons une caractérisation précise de tels ensembles. Nous proposons une classe de langages de coût moyen à seuils multiples, comparant les coordonnées minimales et minimales des points de cet ensemble à des constantes. Nous montrons enfin que cette classe est close par opérations booléennes et analysable. Enfin, dans le dernier volet, nous définissons deux mesures pour un langage temporisé : le volume de ses sous-langages de mots à nombre d'événements fixe et l'entropie (vitesse de croissance), mesure asymptotique pour un nombre non borné d'événements. Ces mesures peuvent être utilisées pour la comparaison quantitative de langages, et l'entropie peut être vue comme la quantité d'information par événement dans un mot typique du langage temporisé. Pour les langages acceptés par des automates temporisés déterministes, nous donnons une formule exacte pour le volume. Ensuite, nous caractérisons l'entropie, en utilisant des méthodes d'analyse fonctionnelle, en tant que logarithme du rayon spectral d'un opérateur intégral positif. Nous établissons plusieurs méthodes pour calculer l'entropie : une symbolique pour les automates que nos appelons " à une horloge et demie ", et deux numériques : une utilisant les techniques d'analyse fonctionnelle, l'autre basée sur la discrétisation. Nous donnons une interprétation de l'entropie en théorie de l'information en termes de complexité de Kolmogorov.

These works are parts of the framework of computational linguistic. We focus on the syntax/semantic interface based on generative grammars.The first part treats of syntax analysis. We introduce Generative Grammars, which are a theoretical approach of syntax, and, then, Stabler minimalist grammars which are a formalism based on generative theory. We analyse the merge operation and we define equivalence for merge and an abstract modelling of lexicon.The aim of the second part is now the syntax/semantic interface. We introduce a new logic formalism based on mixed logic (both commutative and non-commutative connectors). This formalism is equivalent to GM without SMC. We propose a normalisation (a non canonical one) for mixed logic which checks the sub-formula property. Then, these properties are both checked for Lambek calculus with product.Syntactic analysis is performed by proof. On this proof, we synchronise a semantic calculus, using Curry-Howard isomorphism. Terms are based on lambda mu-calculus, and include DRT properties (Discourse Representative Theory).The last part treats some linguistic phenomena. We focus on the cliticisation in french and propose a categorial minimalist grammar for french., 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.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. À 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.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. 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.À 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).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.

(A : B :: C : D, where A, B, C and D are strings of symbols). A temptative formalisation dealing with prefixes, suffixes and parallel infixes, relevant for the description of some morphological and syntactical phenomena. Definition of languages of analogical strings. Discussion of their adequation to the description of natural languages. Proposal for a general engine based on the principle of recursive conservation of analogies between two domains. Application in natural language processing to the specific problems of machine translation and structural analysis., Les analogies auxquelles nous nous intéressons mettent quatre chaînes de symboles en proportion, par exemple, fable : fabuleux :: miracle : miraculeux ou abc : aabbcc :: a^n.b^n.c^n : a^n+1.b^n+1.c^n+1. Une étude historique de l'analogie en linguistique nous a permis de dégager les deux articulations (conformité et rapport) et les notions constitutives (similarité et contiguïté) de ce type d'analogie. De postulats généraux nous avons tiré une caractérisation formelle (encore partielle) rendant compte de la commutation entre chaînes de symboles. Une application directe est la conjugaison automatique par analogie. Nous avons proposé de définir certains langages formels à l'aide de ce type d'analogie. La grammaticalité, c'est-à-dire l'appartenance à un langage, est testée par égalité avec certaines chaînes attestées après réduction selon des modèles analogiques, eux aussi attestés. L'absence de non-terminaux fait de ce type de grammaires des grammaires par l'exemple. Nous examinons la possible place de tels langages dans le débat sur l'adéquation des langages formels à la description des langues. En forçant la conservation des analogies entre deux langages de chaînes analogiques, on obtient une méthode générale applicable à divers problèmes du traitement automatique des langues, par exemple, l'analyse structurale ou la traduction automatique de phrases.

This study deals with computer representations of musical knowledge on the basis of two real-scale experiments. The first experiment focusses on knowledge acquisition in ethnography: an expert (the musician), an analyst (the musicologist) and a machine are interacting in a learning situation. Improvisation schemata through which musicians express themselves are identified and formalized with production rules in a formalism derived from generative grammars and pattern languages. A deterministic algorithm is introduced for assessing the membership of arbitrary strings to the langage defined by a given (context-sensitive) grammar. A technique for the inductive inference of regular languages is presented, enabling automatic knowledge acquisition of syntactic and lexical knowledge. The second experiment is part of the design of a computer environment for musical composition. Here the problem is time representation in a discrete structure of “time objects”, more generally the synchronization of parallel processes. A method is outlined for the determination of a structure with incomplete data about the synchronization of its objects. The concept of “sound object” is then formally introduced. An efficient algorithm is proposed for the time-setting of objects in a structure, given the constraints arising from their metric and topological properties., Cette étude traite de la représentation informatique de connaissances en musique, abordée à partir de deux expériences en grandeur réelle. La première est une méthode d'acquisition de connaissances en ethnographie mettant en interaction un expert (le musicien), un analyste (le musicologue) et une machine dans une situation d'apprentissage. Les schémas d'improvisation des musiciens sont identifiés et exprimés à l'aide de règles de production dans un formalisme dérivé des grammaires génératives et des langages de formes. Un algorithme déterministe de test d'appartenance de chaînes arbitraires au langage défini par une grammaire (sensible au contexte) est présenté, ainsi qu'une technique d'inférence inductive de langages réguliers permettant l'acquisition automatique de connaissances lexicales et syntaxiques. La seconde expérience s'insère dans l'élaboration d'un environnement de composition musicale assistée par ordinateur. Le problème est ici la représentation du temps dans une structure discrète d'“objets temporels”, et plus généralement la synchronisation de processus parallèles. Une méthode est proposée pour la détermination d'une structure à partir de données incomplètes sur la synchronisation des objets. La notion d'“objet sonore” est ensuite explicitée formellement. Un algorithme efficace permet l'instanciation des objets sonores affectés à une structure en tenant compte des contraintes liées à leurs propriétés métriques et topologiques.