Dans le cadre de trois projets européens, notre équipe a mis au point un modèle de données et un langage de requête pour bibliothèques numériques supportant l'identification, la structuration, les métadonnées, la réutilisation, et la découverte des ressources numériques. Le modèle proposé est inspiré par le Web et il est formalisé comme une théorie du premier ordre, dont certains modèles correspondent à la notion de bibliothèque numérique. En outre, une traduction complète du modèle en RDF et du langage de requêtes en SPARQL a également été proposée pour démontrer son adéquation à des applications pratiques. Le choix de RDF est dû au fait qu’il est un langage de représentation généralement accepté dans le cadre des bibliothèques numériques et du Web sémantique. L’objectif de cette thèse était double: concevoir et mettre en œuvre une forme simplifiée de système de gestion de bibliothèques numériques, d’une part, et contribuer à l’enrichissement du modèle, d’autre part. Pour atteindre cet objectif nous avons développé un prototype d’un système de bibliothèque numérique utilisant un stockage RDF pour faciliter la gestion interne des métadonnées. Le prototype permet aux utilisateurs de gérer et d’interroger les métadonnées des ressources numériques ou non-numériques dans le système en utilisant des URIs pour identifier les ressources, un ensemble de prédicats pour la description de ressources, et des requêtes conjonctives simples pour la découverte de connaissances dans le système. Le prototype est mis en œuvre en utilisant les technologies Java et l’environnement de Google Web Toolkit dont l'architecture du système se compose d'une couche de stockage, d’une couche de métier logique, d’une couche de service, et d’une interface utilisateur. Pendant la thèse, le prototype a été construit, testé et débogué localement, puis déployé sur Google App Engine. Dans l’avenir, il peut être étendu pour devenir un système complet de gestion de bibliothèques numériques. Par ailleurs, la thèse présente également notre contribution à la génération de contenu par réutilisation de ressources. Il s’agit d’un travail théorique dont le but est d’enrichir le modèle en lui ajoutant un service important, à savoir la possibilité de création de nouvelles ressources à partir de celles stockées dans le système. L’incorporation de ce service dans le système sera effectuée ultérieurement. / In the context of three European projects, our research team has developed a data model and query language for digital libraries supporting identification, structuring, metadata, and discovery and reuse of digital resources. The model is inspired by the Web and it is formalized as a first-order theory, certain models of which correspond to the notion of digital library. In addition, a full translation of the model to RDF and of the query language to SPARQL has been proposed to demonstrate the feasibility of the model and its suitability for practical applications. The choice of RDF is due to the fact that it is a generally accepted representation language in the context of digital libraries and the Semantic Web. One of the major aims of the thesis was to design and actually implement a simplified form of a digital library management system based on the theoretical model. To obtain this, we have developed a prototype based on RDF and SPARQL, which uses a RDF store to facilitate internal management of metadata. The prototype allows users to manage and query metadata of digital or non-digital resources in the system, using URIs as resource identifiers, a set of predicates to model descriptions of resources, and simple conjunctive queries to discover knowledge in the system. The prototype is implemented by using Java technologies and the Google Web Toolkit framework whose system architecture consists of a storage layer, a business logic layer, a service layer and a user interface. During the thesis work, the prototype was built, tested, and debugged locally and then deployed on Google App Engine. In the future, it will be expanded to become a full fledged digital library management system. Moreover, the thesis also presents our contribution to content generation by reuse. This is mostly theoretical work whose purpose is to enrich the model and query language by providing an important community service. The incorporation of this service in the implemented system is left to future work.

[pt] Atualmente, a maioria dos programas para computadores é obtida através da WEB. Como muitas vezes a procedência são fontes desconhecidas, é preciso se certificar de que o código se comporta como o esperado. A solução ideal seria verificar o código contra uma especificação de políticas de segurança ,contudo, isso pode consumir muito tempo.Uma outra alternativa é fazer com que o próprio código prove ser seguro. O conceito de proof-carryng code (PCC)é baseado nessa idéia : um programa carrega consigo uma prova de sua conformidade com certas políticas de segurança. Ou seja ,ele carrega uma prova a respeito de propriedades do próprio código. Portanto, os mesmos métodos froamsi usados para a verificação de programs podem se utilizados para esta tecnolgia. Considerando este fato,neste trabalho é estudado como cálculo de Hoare, em método formal para realizar a verificação de programas, aplicado a códigos-fonte escritos em uma linguagem de programação imperativa, pode ser útil á tecnica de PCC. Conseqüentemente, são pesquisados métodos para a geração de provas de correção de programas utilizando o método citado, para tornar possível a geração de provas de segurança para PCC utilizando o cálculo de Hoare. / [en] Nowdays most computer programs are obtained from the WEB. Since their source is usually unknown, it is necessary to be sure that the code of the program behaves as expected.The ideal solution would be verify the code against a specification of safety policies.However, this can take too much time.Another approach is making the code itself prove that it is safe. The concept os proof-carryng code (PCC) is based on this idea: a program carries a proof of its conformity with certain safety policies. That is , it carries a proof cencerning properties related to the code itself. Therefore, the same formal methods employed in formal verification of programs can be used in this tecnology. Due to this fact, in this work it is studied how Hoare logic applied to source codes written in an imperative programming language, which is a formal methods are researched to generate proofs of program correctness using the method explained, so that it can be possible to generate PCC safety programs with Hoare logic.

Les dispositifs matériels mobiles proposent des capacités de mesure à l'aide de capteurs soit embarqués, soit connectés. Ils ont vocation à être de plus en plus utilisés dans des processus de prises de mesures. Ils présentent un caractère critique dans le sens où ces informations doivent être fiables, car potentiellement utilisées dans un contexte exigeant. Malgré une grande demande, peu d'applications proposent d'assister les utilisateurs lors de relevés exploitant ces capacités. Idéalement, ces applications devraient proposer des méthodes de visualisation, de calcul, des procédures de mesure et des fonctions de communications permettant la prise en charge de capteurs connectés ou encore la génération de rapports. La rareté de ces applications se justifie par les connaissances nécessaires pour permettre la définition de procédures de mesure correctes. Ces éléments sont apportés par la métrologie et la théorie de la mesure et sont rarement présents dans les équipes de développement logiciel. De plus, chaque utilisateur effectue des activités de mesure spécifiques au domaine de son champ d'activités, ce qui implique le développement d'applications spécifiques de qualité pouvant être certifiées par des experts. Ce postulat apporte la question de recherche à laquelle les travaux présentés répondent: Comment proposer une approche pour la conception d’applications adaptées à des procédures de mesures spécifiques. Les procédures de mesure pouvant être configurées par un utilisateur final La réponse développée est une "plateforme" de conception d'applications d'assistance à la mesure. Elle permet d'assurer la conformité des procédures de mesures sans l'intervention d'expert de la métrologie. Pour cela elle est construite en utilisant des concepts issus de la métrologie, de l'Ingénierie Dirigée par les Modèles et de la logique du premier ordre. Une étude du domaine de la métrologie permet de mettre en évidence la nécessité d'une expertise des procédures de mesure impliquées dans les applications. Cette expertise comprend des termes et des règles assurant l'intégrité et la cohérence d'une procédure de mesure. Un modèle conceptuel du domaine de la métrologie est proposé. Ce modèle conceptuel est ensuite intégré au processus de développement d'une application. Cette intégration se fait par un encodage de ce modèle conceptuel sous la forme d'un schéma des connaissances de la métrologie en logique du premier ordre. Il permet, la vérification du respect des contraintes inhérentes à la métrologie dans une procédure de mesure. Cette vérification est réalisée en confrontant les procédures de mesures au schéma sous forme de requêtes. Ces requêtes sont décrites à l'aide d'un langage proposé par le schéma. Les applications d'assistance à la mesure nécessitent d'exposer à l'utilisateur un processus de mesure impliquant relevés et affichages de mesures étape par étape. Cela implique de pouvoir décrire un processus de mesure et d'en définir les interfaces et le schéma d'évolution. Pour cela, un éditeur d'application est proposé. Cet éditeur propose un langage spécifique dédié à la description d'applications d'assistance à la mesure. Ce langage est construit à partir des concepts, formalismes et outils proposés par l'environnement de métamodélisation Diagrammatic Predicate Framework (DPF). Le langage comporte des contraintes syntaxiques prévenant les erreurs de construction au niveau logiciel tout en réduisant l'écart sémantique entre l'architecte logiciel l'utilisant et un potentiel expert de la métrologie. [...] / Mobile devices offer measuring capabilities using embedded or connected sensors. They are more and more used in measuring processes. They are critical because the performed measurements must be reliable because possibly used in rigorous context. Despite a real demand, there are relatively few applications assisting users with their measuring processes that use those sensors. Such assistant should propose methods to visualise and to compute measuring procedures while using communication functions to handle connected sensors or to generate reports. Such rarity of applications arises because of the knowledges required to define correct measuring procedures. Those knowledges are brought by metrology and measurement theory and are rarely found in software development teams. Moreover, every user has specific measuring activities depending on his field of work. That implies many quality applications developments which could request expert certification. These premises bring the research question the presented works answer : What approach enables the conception of applications suitable to specific measurement procedures considering that the measurement procedures could be configured by the final user. The presented works propose a platform for the development of measuring assistant applications. The platform ensure the conformity of measuring processes without involving metrology experts. It is built upon metrology, model driven engineering and first order logic concepts. A study of metrology enables to show the need of applications measuring process expert evaluation. This evaluation encompasses terms and rules that ensure the process integrity and coherence. A conceptual model of the metrology domain is proposed. That model is then employed in the development process of applications. It is encoded into a first order logic knowledge scheme of the metrology concepts. That scheme enables to verify that metrology constraints holds in a given measuring process. The verification is performed by confronting measuring processes to the knowledge scheme in the form of requests. Those requests are described with a request language proposed by the scheme. Measuring assistant applications require to propose to the user a measuring process that sequences measuring activities. This implies to describe a measuring process, and also to define interactive interfaces and sequencing mechanism. An application editor is proposed. That editor uses a domain specific language dedicated to the description of measuring assistant applications. The language is built upon concepts, formalisms and tools proposed by the metamodeling environment : Diagrammatic Predicat Framework (DPF). The language encompasses syntactical constraints that prevent construction errors on the software level while reducing the semantical gap between the software architect using it and a potential metrology expert. Then, mobile platforms need to execute a behaviour conforming to the editor described one. An implementation modelling language is proposed. This language enables to describe measuring procedures as sequences of activities. Activities imply to measure, compute and present values. Quantities are all abstracted by numerical values. This eases their computation and the use of sensors. The implementation model is made up of software agents. A mobile application is also proposed. The application is built upon a framework of agents, an agent network composer and a runtime system. The application is able to consider an implementation model and to build the corresponding agent network in order to propose a behaviour matching the end users needs. This enables to answer to any user needs, considering he can access to the implementation model, without requiring to download several applications.

An abstract knowledge representation of cognitive robots - as used for reasoning and planning - typically relies on symbols denoting objects of the world and states of affairs. The process of creating and maintaining the correct connection between a symbol denoting an object and its corresponding perceptual image (called percept), both referring to the same physical object, is called symbol anchoring. Most current cognitive systems implement an ad hoc solution which may work for the specific, intended application under certain conditions. Conversely, we suggest a formal and general approach to the symbol anchoring problem, which enhances previous approaches in terms of flexibility, applicability and expressiveness, and which completely automates the process of determining and maintaining all plausible hypotheses of correspondences between object symbols and perceptual images of physical objects. Based on the first-order logical Fluent Calculus, our approach inherits its rich expressiveness with respect to knowledge representation and reasoning. Implementing all required symbol anchoring functionalities, our approach also complies with fundamental concepts of phenomenalism, representationalism and the sense-data theory of philosophy of cognition.

Tous les problèmes définissables en logique du second ordre monadique peuvent être résolus en temps polynomial dans les classes de graphes qui ont une largeur de clique bornée. La largeur de clique est un paramètre de graphe défini de manière algébrique, c'est-à-dire, à partir d'opérations de composition de graphes. La largeur de rang, définie de manière combinatoire, est une notion équivalente à la largeur de clique des graphes non orientés. Nous donnons une caractérisation algébrique de la largeur de rang et nous montrons qu'elle est linéairement bornée par la largeur arborescente. Nous proposons également une notion de largeur de rang pour les graphes orientés et une relation de vertex-minor pour les graphes orientés. Nous montrons que les graphes orientés qui ont une largeur de rang bornée sont caractérisés par une liste finie de graphes orientés à exclure comme vertex-minor. Beaucoup de classes de graphes n'ont pas une largeur de rang bornée, par exemple, les graphes planaires. Nous nous intéressons aux systèmes d'étiquetage dans ces classes de graphes. Un système d'étiquetage pour une propriété P dans un graphe G, consiste à assigner une étiquette, aussi petite que possible, à chaque sommet de telle sorte que l'on puisse vérifier si G satisfait P en n'utilisant que les étiquettes des sommets. Nous montrons que si P est une propriété définissable en logique du premier ordre alors, certaines classes de graphes de largeur de clique localement bornée admettent un système d'étiquetage pour P avec des étiquettes de taille logarithmique. Parmi ces classes on peut citer les classes de graphes de degré borné, les graphes planaires et plus généralement les classes de graphes qui excluent un apex comme mineur et, les graphes d'intervalle unitaire. Si x et y sont deux sommets, X un ensemble de sommets et F un ensemble d'arêtes, nous notons Conn(x,y,X,F) la propriété qui vérifie dans un graphe donné si x et y sont connectés par un chemin, qui ne passe par aucun sommet de X si aucune arête de F. Cette propriété n'est pas définissable en logique du premier ordre. Nous montrons qu'elle admet un système d'étiquetage avec des étiquettes de taille logarithmique dans les graphes planaires. Nous montrons enfin que Conn(x,y,X,0) admet également un système d'étiquetage avec des étiquettes de taille logarithmique dans des classes de graphes qui sont définies comme des combinaisons de graphes qui ont une petite largeur de clique et telles que le graphe d'intersection de ces derniers est planaire et est de degré borné. / Every property definable in onadic second order logic can be checked in polynomial-time on graph classes of bounded clique-width. Clique-width is a graph parameter defined in an algebraical way, i.e., with operations ``concatenating graphs'' and that generalize concatenation of words.Rank-width, defined in a combinatorial way, is equivalent to the clique-width of undirected graphs. We give an algebraic characterization of rank-width and we show that rank-width is linearly bounded in term of tree-width. We also propose a notion of ``rank-width'' of directed graphs and a vertex-minor inclusion for directed graphs. We show that directed graphs of bounded ``rank-width'' are characterized by a finite list of finite directed graphs to exclude as vertex-minor. Many graph classes do not have bounded rank-width, e.g., planar graphs. We are interested in labeling schemes on these graph classes. A labeling scheme for a property P in a graph G consists in assigning a label, as short as possible, to each vertex of G and such that we can verify if G satisfies P by just looking at the labels. We show that every property definable in first order logic admit labeling schemes with labels of logarithmic size on certain graph classes that have bounded local clique-width. Bounded degree graph classes, minor closed classes of graphs that exclude an apex graph as a minor have bounded local clique-width. If x and y are two vertices and X is a subset of the set of vertices and Y is a subset of the set of edges, we let Conn(x,y,X,Y) be the graph property x and y are connected by a path that avoids the vertices in X and the edges in Y. This property is not definable by a first order formula. We show that it admits a labeling scheme with labels of logarithmic size on planar graphs. We also show that Conn(x,y,X,0) admits short labeling schemes with labels of logarithmic size on graph classes that are ``planar gluings'' of graphs of small clique-width and with limited overlaps.

Diese Arbeit untersucht ordnungsinvariante Formeln der Logik erster Stufe (FO) und einiger ihrer Erweiterungen, sowie andere eng verwandte Konzepte der endlichen Modelltheorie. Viele Resultate der endlichen Modelltheorie nehmen an, dass Strukturen mit einer Einbettung ihres Universums in ein Anfangsstück der natürlichen Zahlen ausgestattet sind. Dies erlaubt es, beliebige Relationen (z.B. die lineare Ordnung) und Operationen (z.B. Addition, Multiplikation) von den natürlichen Zahlen auf solche Strukturen zu übertragen. Die resultierenden Relationen auf den endlichen Strukturen werden als numerische Prädikate bezeichnet. Werden numerische Prädikate in Formeln verwendet, beschränkt man sich dabei häufig auf solche Formeln, deren Wahrheitswert auf endlichen Strukturen invariant unter Änderungen der Einbettung der Strukturen ist. Wenn das einzige verwendete numerische Prädikat eine lineare Ordnung ist, spricht man beispielsweise von ordnungsinvarianten Formeln. Die Resultate dieser Arbeit können in drei Teile unterteilt werden. Der erste Teil betrachtet die Lokalitätseigenschaften von FO-Formeln mit Modulo-Zählquantoren, die beliebige numerische Prädikate invariant nutzen. Der zweite Teil betrachtet FO-Sätze, die eine lineare Ordnung samt der zugehörigen Addition auf invariante Weise nutzen, auf endlichen Bäumen. Es wird gezeigt, dass diese dieselben regulären Baumsprachen definieren, wie FO-Sätze ohne numerische Prädikate mit bestimmten Kardinalitätsprädikaten. Für den Beweis wird eine algebraische Charakterisierung der in dieser Logik definierbaren Baumsprachen durch Operationen auf Bäumen entwickelt. Der dritte Teil der Arbeit beschäftigt sich mit der Ausdrucksstärke und der Prägnanz von FO und Erweiterungen von FO auf Klassen von Strukturen beschränkter Baumtiefe. / This thesis studies the concept of order-invariance of formulae of first-order logic (FO) and some of its extensions as well as other closely related concepts from finite model theory. Many results in finite model theory assume that structures are equipped with an embedding of their universe into an initial segment of the natural numbers. This allows to transfer arbitrary relations (e.g. linear order) and operations (e.g. addition, multiplication) on the natural numbers to structures. The arising relations on the structures are called numerical predicates. If formulae use these numerical predicates, it is often desirable to consider only such formulae whose truth value in finite structures is invariant under changes to the embeddings of the structures. If the numerical predicates include only a linear order, such formulae are called order-invariant. We study the effect of the invariant use of different kinds of numerical predicates on the expressive power of FO and extensions thereof. The results of this thesis can be divided into three parts. The first part considers the locality and non-locality properties of formulae of FO with modulo-counting quantifiers which may use arbitrary numerical predicates in an invariant way. The second part considers sentences of FO which may use a linear order and the corresponding addition in an invariant way and obtains a characterisation of the regular finite tree languages which can be defined by such sentences: these are the same tree languages which are definable by FO-sentences without numerical predicates with certain cardinality predicates. For the proof, we obtain a characterisation of the tree languages definable in this logic in terms of algebraic operations on trees. The third part compares the expressive power and the succinctness of different ex- tensions of FO on structures of bounded tree-depth.

In dieser Arbeit wird das dynamische Auswertungsproblem über dynamische Datenbanken betrachtet, bei denen Tupel hinzugefügt oder gelöscht werden können. Die Aufgabe besteht darin einen dynamischen Algorithmus zu konstruieren, welcher unmittelbar nachdem die Datenbank aktualisiert wurde, die Datenstruktur, die das Resultat repräsentiert, aktualisiert. Die Datenstruktur soll in konstanter Zeit aktualisiert werden und das Folgende unterstützen: * Teste in konstanter Zeit ob ein Tupel zur Ausgabemenge gehört, * gebe die Anzahl der Tupel in der Ausgabemenge in konstanter Zeit aus, * zähle die Tupel aus der Ausgabemenge mit konstanter Taktung auf und * zähle den Unterschied zwischen der neuen und der alten Ausgabemenge mit konstanter Taktung auf. Im ersten Teil werden konjunktive Anfragen und Vereinigungen konjunktiver Anfragen auf relationalen Datenbanken betrachtet. Die Idee der q-hierarchischen Anfragen (und t-hierarchische Anfragen für das Testen) wird eingeführt und es wird gezeigt, dass das Resultat für jede q-hierarchische Anfrage auf dynamischen Datenbanken effizient in dem oben beschriebenen Szenario ausgewertet werden können. Konjunktive Anfragen mit Aggregaten werden weiterhin betrachtet. Es wird gezeigt, dass das Lernen von polynomiellen Regressionsfunktionen in konstanter Zeit vorbereitet werden kann, falls die Trainingsdaten aus dem Anfrageergebnis kommen. Mit logarithmischer Update-Zeit kann folgende Routine unterstützt werden: Bei Eingabe einer Zahl j, gebe das j-te Tupel aus der Aufzählung aus. Im zweiten Teil werden Anfragen, die Formeln der Logik erster Stufe (FO) und deren Erweiterung mit Modulo-Zähl Quantoren (FO+MOD) sind, betrachtet, und es wird gezeigt, dass diese effizient unter Aktualisierungen ausgewertet können, wobei die dynamische Datenbank die Gradschranke nicht überschreitet, und bei der Auswertung die Zähl-, Test-, Aufzähl- und die Unterschied-Routine unterstützt werden. / This thesis investigates the query evaluation problem for fixed queries over fully dynamic databases, where tuples can be inserted or deleted. The task is to design a dynamic algorithm that immediately reports the new result of a fixed query after every database update. In particular, the goal is to construct a data structure that allows to support the following scenario. After every database update, the data structure can be updated in constant time such that afterwards we are able * to test within constant time for a given tuple whether or not it belongs to the query result, * to output the number of tuples in the query result, * to enumerate all tuples in the new query result with constant delay and * to enumerate the difference between the old and the new query result with constant delay. In the first part, conjunctive queries and unions of conjunctive queries on arbitrary relational databases are considered. The notion of q-hierarchical conjunctive queries (and t-hierarchical conjunctive queries for testing) is introduced and it is shown that the result of each such query on a dynamic database can be maintained efficiently in the sense described above. Moreover, this notion is extended to aggregate queries. It is shown that the preparation of learning a polynomial regression function can be done in constant time if the training data are taken (and maintained under updates) from the query result of a q-hierarchical query. With logarithmic update time the following routine is supported: upon input of a natural number j, output the j-th tuple that will be enumerated. In the second part, queries in first-order logic (FO) and its extension with modulo-counting quantifiers (FO+MOD) are considered, and it is shown that they can be efficiently evaluated under updates, provided that the dynamic database does not exceed a certain degree bound, and the counting, testing, enumeration and difference routines is supported.

Normalformen drücken semantische Eigenschaften einer Logik durch syntaktische Restriktionen aus. Sie ermöglichen es Algorithmen, Grenzen der Ausdrucksstärke einer Logik auszunutzen. Ein Beispiel ist die Lokalität der Logik erster Stufe (FO), die impliziert, dass Graph-Eigenschaften wie Erreichbarkeit oder Zusammenhang nicht FO-definierbar sind. Gaifman-Normalformen drücken die Bedeutung einer FO-Formel als Boolesche Kombination lokaler Eigenschaften aus. Sie haben eine wichtige Rolle in Model-Checking Algorithmen für Klassen dünn besetzter Graphen, deren Laufzeit durch die Größe der auszuwertenden Formel parametrisiert ist. Es ist jedoch bekannt, dass Gaifman-Normalformen im Allgemeinen nur mit nicht-elementarem Aufwand konstruiert werden können. Dies führt zu einer enormen Parameterabhängigkeit der genannten Algorithmen. Ähnliche nicht-elementare untere Schranken sind auch für Feferman-Vaught-Zerlegungen und für die Erhaltungssätze von Lyndon, Łoś und Tarski bekannt. Diese Arbeit untersucht die Komplexität der genannten Normalformen auf Klassen von Strukturen beschränkten Grades, für welche die nicht-elementaren unteren Schranken nicht gelten. Für diese Einschränkung werden Algorithmen mit elementarer Laufzeit für die Konstruktion von Gaifman-Normalformen, Feferman-Vaught-Zerlegungen, und für die Erhaltungssätze von Lyndon, Łoś und Tarski entwickelt, die in den ersten beiden Fällen worst-case optimal sind. Wichtig hierfür sind Hanf-Normalformen. Es wird gezeigt, dass eine Erweiterung von FO durch unäre Zählquantoren genau dann Hanf-Normalformen erlaubt, wenn alle Zählquantoren ultimativ periodisch sind, und wie Hanf-Normalformen in diesen Fällen in elementarer und worst-case optimaler Zeit konstruiert werden können. Dies führt zu Model-Checking Algorithmen für solche Erweiterungen von FO sowie zu Verallgemeinerungen der Algorithmen für Feferman-Vaught-Zerlegungen und die Erhaltungssätze von Lyndon, Łoś und Tarski. / Normal forms express semantic properties of logics by means of syntactical restrictions. They allow algorithms to benefit from restrictions of the expressive power of a logic. An example is the locality of first-order logic (FO), which implies that properties like reachability or connectivity cannot be defined in FO. Gaifman's local normal form expresses the satisfaction conditions of an FO-formula by a Boolean combination of local statements. Gaifman normal form serves as a first step in fixed-parameter model-checking algorithms, parameterised by the size of the formula, on sparse graph classes. However, it is known that in general, there are non-elementary lower bounds for the costs involved in transforming a formula into Gaifman normal form. This leads to an enormous parameter-dependency of the aforementioned algorithms. Similar non-elementary lower bounds also hold for Feferman-Vaught decompositions and for the preservation theorems by Lyndon, Łoś, and Tarski. This thesis investigates the complexity of these normal forms when restricting attention to classes of structures of bounded degree, for which the non-elementary lower bounds are known to fail. Under this restriction, the thesis provides algorithms with elementary and even worst-case optimal running time for the construction of Gaifman normal form and Feferman-Vaught decompositions. For the preservation theorems, algorithmic versions with elementary running time and non-matching lower bounds are provided. Crucial for these results is the notion of Hanf normal form. It is shown that an extension of FO by unary counting quantifiers allows Hanf normal forms if, and only if, all quantifiers are ultimately periodic, and furthermore, how Hanf normal form can be computed in elementary and worst-case optimal time in these cases. This leads to model-checking algorithms for such extensions of FO and also allows generalisations of the constructions for Feferman-Vaught decompositions and preservation theorems.