No

Ce mémoire est constitué de 3 parties.La NP-complétude de la satisfaction de combinaisons booléennes de contraintes de sous-arbres est démontrée dans l'article [Ven87] ; la partie I de ce mémoire étudie dans quelle mesure l'ajout de contraintes régulières laisse espérer conserver la complexité NP. Ce modèle étendu définit une nouvelle classe de langages dont l'expressivité est comparée à celle des Rigid Tree Automata [JKV11]. Puis un début de formalisation des t-dags est donné.Les patterns ont été étudiés, principalement du point de vue des contraintes sur les données qu'ils demandent. La partie II de ce mémoire les étudie plus finement, en mettant de côté les données. Les squelettes sont définis en tant qu'intermédiaire de calcul et le fait que leur syntaxe caractérise leur sémantique est démontré. Puis un lemme de pompage est donné dans un cas restreint, un autre dans le cas général est étudié et conjecturé. Ensuite des fragments de combinaisons booléennes de patterns sont comparés en expressivité pour terminer avec l'étude de la complexité des problèmes de model-checking, satisfaisabilité et DTD-satisfaisabilité sur les dits fragments.Le contenu de la partie III constitue l'article [FMS11], c'est la démonstration de la caractérisation des langages des automates fortement déterministes de niveau 2 par des systèmes d'équations récurrentes caténatives. Celle-ci utilise, entre autres, des techniques de réécriture, la notion d'inconnues non-réécrivables et les ordres noethériens. Cette caractérisation constitue le cas de base de la récurrence démontrée dans [Sén07]. / This thesis is in 3 parts.The NP-completeness of satisfiability of boolean combinations of subtree constraints is shown in the article [Ven87] ; in the part I of this thesis, we study whether adding regular contraints lets hope for keeping the same complexity. This extended model defines a new class of languages which is compared in expressivity to the Rigid Tree Automata [JKV11]. Then a begining of formalisation of the t-dags is developped.The patterns have been studied mainly from the point of view of the constraints they demand on the data. The part II of this thesis study them more finely, by putting aside the data. The skeletons are defined as calculus intermediate and the characterisation holding between their syntax and their semantics is shown. Then a pumping lemma is prooved in a restreict case, another one is conjectured in the most general case. Then fragments of boolean combinations of patterns are compared in expressivity, this parts ends with the study of complexity of model-checking, satisfiability and DTD-satisfiability on these fragments.The content of part III constitutes the article [FMS11], it is the demonstration of the characterisation of strongly-deterministic 2-level pushdown automata by recurrent catenative equation systems. This proof uses in particular, some rewriting techniques, unrewritable unknowns and noetherian orders. This characterisation provides the base case of the recurrence shown in [Sén07].

La performance énergétique est un pilier pour réduire l'utilisation d'énergie non renouvelable, en plus de l'utilisation des énergies renouvelables. En fait, les bâtiments sont au cœur de la politique des performances énergétiques de l'UE puisque 40% de la consommation finale d'énergie et 36% des émissions de gaz à effet de serre provient des bureaux, magasins et autres bâtiments. Les bâtiments peuvent être considérés comme des systèmes dynamiques et le transfert de la chaleur dans les bâtiments peut être représenté en utilisant des modèles dynamiques. De cette façon, le transfert de la chaleur dans les bâtiments peut être décrit par des réseaux thermiques obtenus en utilisant la théorie des graphes et de la thermodynamique, et peuvent être déduits de l'équation de la chaleur classique. Les réseaux thermiques peuvent être exprimés comme un système d'équations différentielles et algébriques (DAE) qui peut être transformé en représentation d'état et obtenir un fonction de transfert à partir de laquelle un modèle autorégressif avec des variables exogènes (ARX) peut être obtenu. Ces différentes structures de modèle peuvent être utilisées pour identifier les paramètres physiques des réseaux thermiques, ce qui implique que la méthode peut être utilisée pour identifier la performance intrinsèque des bâtiments et aider à la réduction de la consommation d'énergie dans les bâtiments.Cela peut faciliter l'évaluation de la performance énergétique des bâtiments dans un cadre reproductible qui permet la comparaison entre différentes solutions constructives.Les principales contributions originales de cette thèse sont: 1) les réseaux thermiques sont présentées à partir de la théorie des graphes et de la thermodynamique, sans considérer l'analogie thermique-électrique; 2) l'équation classique de la chaleur est reliée explicitement avec un système de DAE (réseau thermique) par les éléments finis; 3) différentes transformations pour déduire des modèles du transfert de la chaleur avec signification physique, à partir de l'équation de la chaleur classique, sont présentées toutes ensemble; 4) les transformations entre les modèles sont effectuées à partir des réseaux thermiques jusqu’aux modèles autorégressifs avec des variables exogènes (ARX) et vice-versa; et 5) un critère de sélection de l'ordre du modèle par une analyse de fréquence des mesures est proposé. / Energy efficiency is one of the two pillars to decrease the use of non-renewable energy besides the use of renewables energies. In fact, buildings are central to the EU's energy efficiency policy, as nearly 40% of the final energy consumption and 36% of greenhouse gas emissions take place in houses, offices, shops and other buildings. Buildings may be considered as dynamic systems and heat transfer in buildings may be represented using dynamic models. In this way, heat transfer in buildings may be described by thermal networks which may be stated considering graph theory and thermodynamics, and may be deduced from the classical heat equation. Thermal networks may be expressed as a system of linear differential algebraic equations (DAE) and the system of linear DAE may be transformed into a state-space representation from which an autoregressive model with exogenous (ARX) can be obtained. These different model structures may be used for identifying the physical parameters of thermal networks which implies that this methodology may be useful for identifying the intrinsic performance of buildings and tackling the reduction of non-renewable energy consumption in buildings. This may facilitate the assessment of energy efficiency of buildings within a reproducible framework which allows the comparison between different constructive solutions.The main original contributions of this dissertation are: 1) thermal networks are stated from graph theory and thermodynamics, leaving back the thermal-electrical analogy; 2) classical heat equation is connected explicitly to a system of DAE (thermal network) by using the finite elements; 3) the transformations for deducing heat transfer models with physical meaning from the classical heat equation are put altogether; 4) transformations between models may are done from thermal networks to autoregressive models with exogenous (ARX) and back; and 5) a criterion for selecting the order of the model by frequency analysis of measurements is proposed.