Unification with constants modulo the theory ACUI of an associative (A), commutative (C) and idempotent (I) binary function symbol with a unit (U) corresponds to solving a very simple type of set equations. It is well-known that solvability of systems of such equations can be decided in polynomial time by reducing it to satisfiability of propositional Horn formulae. Here we introduce a modified version of this problem by no longer requiring all equations to be completely solved, but allowing for a certain number of violations of the equations. We introduce three different ways of counting the number of violations, and investigate the complexity of the respective decision problem, i.e., the problem of deciding whether there is an assignment that solves the system with at most l violations for a given threshold value l. / Submitted to 30th International Workshop on Unification

Unification in description logics (DLs) has been introduced as a novel inference service that can be used to detect redundancies in ontologies, by finding different concepts that may potentially stand for the same intuitive notion. It was first investigated in detail for the DL FL₀, where unification can be reduced to solving certain language equations. In order to increase the recall of this method for finding redundancies, we introduce and investigate the notion of approximate unification, which basically finds pairs of concepts that “almost” unify. The meaning of “almost” is formalized using distance measures between concepts. We show that approximate unification in FL₀ can be reduced to approximately solving language equations, and devise algorithms for solving the latter problem for two particular distance measures.

Recently introduced approaches for relaxed query answering, approximately defining concepts, and approximately solving unification problems in Description Logics have in common that they are based on the use of concept comparison measures together with a threshold construction. In this paper, we will briefly review these approaches, and then show how weighted automata working on infinite trees can be used to construct computable concept comparison measures for FL₀ that are equivalence invariant w.r.t. general TBoxes. This is a first step towards employing such measures in the mentioned approximation approaches. / Accepted to LATA 2017

Unification in Description Logics (DLs) has been proposed as an inference service that can, for example, be used to detect redundancies in ontologies. For the DL EL, which is used to define several large biomedical ontologies, unification is NP-complete. However, the unification algorithms for EL developed until recently could not deal with ontologies containing general concept inclusions (GCIs). In a series of recent papers we have made some progress towards addressing this problem, but the ontologies the developed unification algorithms can deal with need to satisfy a certain cycle restriction. In the present paper, we follow a different approach. Instead of restricting the input ontologies, we generalize the notion of unifiers to so-called hybrid unifiers. Whereas classical unifiers can be viewed as acyclic TBoxes, hybrid unifiers are cyclic TBoxes, which are interpreted together with the ontology of the input using a hybrid semantics that combines fixpoint and descriptive semantics. We show that hybrid unification in EL is NP-complete and introduce a goal-oriented algorithm for computing hybrid unifiers.

Unification in Description Logics (DLs) has been proposed as an inference service that can, for example, be used to detect redundancies in ontologies. The inexpressive Description Logic EL is of particular interest in this context since, on the one hand, several large biomedical ontologies are defined using EL. On the other hand, unification in EL has recently been shown to be NP-complete, and thus of significantly lower complexity than unification in other DLs of similarly restricted expressive power. However, the unification algorithms for EL developed so far cannot deal with general concept inclusion axioms (GCIs). This paper makes a considerable step towards addressing this problem, but the GCIs our new unification algorithm can deal with still need to satisfy a certain cycle restriction.

Unification in Description Logics has been proposed as an inference service that can, for example, be used to detect redundancies in ontologies. For the Description Logic EL, which is used to define several large biomedical ontologies, unification is NP-complete. An NP unification algorithm for EL based on a translation into propositional satisfiability (SAT) has recently been presented. In this report, we extend this SAT encoding in two directions: on the one hand, we add general concept inclusion axioms, and on the other hand, we add role hierarchies (H) and transitive roles (R+). For the translation to be complete, however, the ontology needs to satisfy a certain cycle restriction. The SAT translation depends on a new rewriting-based characterization of subsumption w.r.t. ELHR+-ontologies.

Unification in Description Logics (DLs) has been proposed as an inference service that can, for example, be used to detect redundancies in ontologies. For the DL EL, which is used to define several large biomedical ontologies, unification is NP-complete. A goal-oriented NP unification algorithm for EL that uses nondeterministic rules to transform a given unification problem into solved form has recently been presented. In this report, we extend this goal-oriented algorithm in two directions: on the one hand, we add general concept inclusion axioms (GCIs), and on the other hand, we add role hierarchies (H) and transitive roles (R+). For the algorithm to be complete, however, the ontology consisting of the GCIs and role axioms needs to satisfy a certain cycle restriction.

Unification has been introduced in Description Logic (DL) as a means to detect redundancies in ontologies. In particular, it was shown that testing unifiability in the DL EL is an NP-complete problem, and this result has been extended in several directions. Surprisingly, it turned out that the complexity increases to PSpace if one disallows the use of the top concept in concept descriptions. Motivated by features of the medical ontology SNOMED CT, we extend this result to a setting where the top concept is disallowed, but there is a background ontology consisting of restricted forms of concept and role inclusion axioms. We are able to show that the presence of such axioms does not increase the complexity of unification without top, i.e., testing for unifiability remains a PSpace-complete problem.

Le présent travail aborde le thème de la complexité sémantique dans le langage naturel, et il propose une hypothèse basée sur certaines caractéristiques des phrases du langage naturel qui déterminent la difficulté pour l'interpretation humaine.Nous visons à introduire un cadre théorique général de la complexité sémantique de la phrase, dans lequel la difficulté d'élaboration est liée à l'interaction entre deux composants: la Mémoire, qui est responsable du rangement des représentations d'événements extraites par des corpus, et l'Unification, qui est responsable de la combinaison de ces unités dans des structures plus complexes. Nous proposons que la complexité sémantique depend de la difficulté de construire une représentation sémantique de l'événement ou de la situation exprimée par une phrase, qui peut être récupérée directement de la mémoire sémantique ou construit dynamiquement en satisfaisant les contraintes contenus dans les constructions.Pour tester nos intuitions, nous avons construit un Distributional Semantic Model pour calculer le coût de composition de l'unification des phrases. Les tests sur des bases de données psycholinguistiques ont révélé que le modèle est capable d'expliquer des phénomènes sémantiques comme la mise à jour context-sensitive des attentes sur les arguments et les métonymies logiques. / The present work deals with the problem of the semantic complexity in natural language, proposing an hypothesis based on some features of natural language sentences that determine their difficulty for human understanding. We aim at introducing a general framework for semantic complexity, in which the processing difficulty depends on the interaction between two components: a Memory component, which is responsible for the storage of corpus-extracted event representations, and a Unification component, which is responsible for combining the units stored in Memory into more complex structures. We propose that semantic complexity depends on the difficulty of building a semantic representation of the event or the situation conveyed by a sentence, that can be either retrieved directly from the semantic memory or built dynamically by solving the constraints included in the stored representations.In order to test our intuitions, we built a Distributional Semantic Model to compute a compositional cost for the sentence unification process. Our tests on several psycholinguistic datasets showed that our model is able to account for semantic phenomena such as the context-sensitive update of argument expectations and of logical metonymies.

Though sovereign debts are often viewed as risk-free assets, some extreme events may lead to the repudiation of these debts. A large literature has been devoted to the motivations of repayment and to the causes of default. The impact of wars, which may lead to the repudiation of sovereign debt, on sovereign bond prices has also been analyzed. However, the impact of other types of seldom occurring but dramatic events, which may lead to the repudiation of debts, on bond prices has been overlooked. My current research aims to analyze three of them: the repudiation of debts because of their alleged "odiousness", the introduction of common debt after a state's unification and the debt partition following the break-up of a country. Since the events under consideration don't happen frequently, the dissertation will rely on four historical examples: Cuba, Russia, Italy and Belgium. The time period considered is the 19th century. Based on a historical analysis and the set-up of an original database, this project determines the effects of these events on sovereign debt valorization, using an econometric approach.<p><p>The first part of the research estimates the risk premium required by investors to hold debts which could be denounced as odious. Bondholders could require a premium to compensate for the higher default risk due to the odious character of the debts. The paper quantifies the risk premium required by investors to hold debts which could be denounced as odious and it analyses the relation between the value of the government bond and extreme "odious debt" events. In order to identify if such a premium exists, I focus on a Cuban case study. Based on an original database of Cuban bonds, the paper reveals the existence of a risk premium of at least 200 basis points which penalises bonds issued by dictatorial regimes. The bond market "odious" shocks are provided by a Structural VAR analysis. In a second case study, my research analyses the Tsarist bonds of 1906 and the premium to hold despotic regime debt. The paper shows that the market required a premium despite the attempts made by the Russian government to present the loan as clean.<p><p>The second and third parts of my research look at the effects of state succession on the sovereign bonds market. They analyze respectively the two subsets of state succession: state unification and "country break-up". The second part of the dissertation provides an empirical study of sovereign debt integration and analyses the evolution of sovereign bond prices when several countries merge to become a "unified country" or when the probability of such an event exists. Based on an original database made of pre-unification and post-unification Italian bonds, the paper shows the impact of Italy's unification on the bonds. The analysis puts forward that prior to the unification in 1862, the bonds issued by the future parts of the kingdom reacted in an idiosyncratic way. Around the sovereign debt integration, the paper highlights a large risk increase for low-yield bonds. Using a break point analysis and a Dynamic Factor Model, the paper proves that until the late 1860's the financial market did not believe in Italy's Unification. The third part of my research analyzes the financial impact on state bonds of a country which faces a risk to break up. This paper provides an empirical analysis of the evolution of sovereign debt prices when a state breaks up, or when it faces such an event. Based on an original database of Dutch and Belgian bonds, this research shows the impact of Belgian independence in 1830 on the Belgium bonds. This article analyses two risk premiums which may affect the sovereign debt of a state: the first one is linked to the country break-up (or the probability that one may occur) and the second one is due to the instability experienced by the new country. This analysis puts forward a "country break-up" risk premium of 142 basis points. The role of the debt underwriter has also been highlighted in the case of Belgian independence. Financial markets required no "new country" risk premium for Belgian bonds which were underwritten by Rothschild, but the risk premium remained for the Belgian authorities. This was likely due to the role of Rothschild as underwriter whose reputation persuaded the market that the risk is low, but who charged a premium to the Belgian government for their services.<p> / Doctorat en Sciences économiques et de gestion / info:eu-repo/semantics/nonPublished