We consider ontology-based query answering in a setting where some of the data are numerical and of a probabilistic nature, such as data obtained from uncertain sensor readings. The uncertainty for such numerical values can be more precisely represented by continuous probability distributions than by discrete probabilities for numerical facts concerning exact values. For this reason, we extend existing approaches using discrete probability distributions over facts by continuous probability distributions over numerical values. We determine the exact (data and combined) complexity of query answering in extensions of the well-known description logics EL and ALC with numerical comparison operators in this probabilistic setting. / This is an extended version of the article in: Proceedings of the 11th International Symposium on Frontiers of Combining Systems. This version has been revised based on the comments of the reviewers.

To represent and reason about contextualized knowledge often two-dimensional Description Logics (DLs) are employed, where one DL is used to describe contexts (or possible worlds) and the other DL is used to describe the objects, i.e. the relational structure of the specific contexts. Previous approaches for DLs of context that combined pairs of DLs resulted in undecidability in those cases where so-called rigid roles are admitted, i.e. if parts of the relational structure are the same in all contexts. In this paper, we present a novel combination of pairs of DLs and show that reasoning stays decidable even in the presence of rigid roles. We give complexity results for various combinations of DLs involving ALC, SHOQ, and EL.

Fuzzy Description Logics (FDLs) combine classical Description Logics with the semantics of Fuzzy Logics in order to represent and reason with vague knowledge. Most FDLs using truth values from the interval [0; 1] have been shown to be undecidable in the presence of a negation constructor and general concept inclusions. One exception are those FDLs whose semantics is based on the infinitely valued Gödel t-norm (G). We extend previous decidability results for the FDL G-ALC to deal with complex role inclusions, nominals, inverse roles, and qualified number restrictions. Our novel approach is based on a combination of the known crispification technique for finitely valued FDLs and an automata-based procedure for reasoning in G-ALC.

Formulae of linear temporal logic (LTL) can be used to specify (wanted or unwanted) properties of a dynamical system. In model checking, the system’s behaviour is described by a transition system, and one needs to check whether all possible traces of this transition system satisfy the formula. In runtime verification, one observes the actual system behaviour, which at any point in time yields a finite prefix of a trace. The task is then to check whether all continuations of this prefix to a trace satisfy (violate) the formula. More precisely, one wants to construct a monitor, i.e., a finite automaton that receives the finite prefix as input and then gives the right answer based on the state currently reached. In this paper, we extend the known approaches to LTL runtime verification in two directions. First, instead of propositional LTL we use the more expressive temporal logic ALC-LTL, which can use axioms of the Description Logic (DL) ALC instead of propositional variables to describe properties of single states of the system. Second, instead of assuming that the observed system behaviour provides us with complete information about the states of the system, we assume that states are described in an incomplete way by ALC-knowledge bases. We show that also in this setting monitors can effectively be constructed. The (double-exponential) size of the constructed monitors is in fact optimal, and not higher than in the propositional case. As an auxiliary result, we show how to construct Büchi automata for ALC-LTL-formulae, which yields alternative proofs for the known upper bounds of deciding satisfiability in ALC-LTL.

Recently, a lot of research has combined description logics (DLs) of the DL-Lite family with temporal formalisms. Such logics are proposed to be used for situation recognition and temporalized ontology-based data access. In this report, we consider DL-Lite-LTL, in which axioms formulated in a member of the DL-Lite family are combined using the operators of propositional linear-time temporal logic (LTL). We consider the satisfiability problem of this logic in the presence of so-called rigid symbols whose interpretation does not change over time. In contrast to more expressive temporalized DLs, the computational complexity of this problem is the same as for LTL, even w.r.t. rigid symbols.

Very recently, the tableau-based algorithm for deciding consistency of general fuzzy DL ontologies over the product t-norm was shown to be incorrect, due to a very weak blocking condition. In this report we take the first steps towards a correct algorithm by modifying the blocking condition, such that the (finite) structure obtained through the algorithm uniquely describes an infinite system of quadratic constraints. We show that this procedure terminates, and is sound and complete in the sense that the input is consistent iff the corresponding infinite system of constraints is satisfiable.

Ontology-based data access (OBDA) generalizes query answering in databases towards deduction since (i) the fact base is not assumed to contain complete knowledge (i.e., there is no closed world assumption), and (ii) the interpretation of the predicates occurring in the queries is constrained by axioms of an ontology. OBDA has been investigated in detail for the case where the ontology is expressed by an appropriate Description Logic (DL) and the queries are conjunctive queries. Motivated by situation awareness applications, we investigate an extension of OBDA to the temporal case. As query language we consider an extension of the well-known propositional temporal logic LTL where conjunctive queries can occur in place of propositional variables, and as ontology language we use the prototypical expressive DL ALC. For the resulting instance of temporalized OBDA, we investigate both data complexity and combined complexity of the query entailment problem.

Les acides linoléiques conjugués (ALC) sont des isomères positionnels et géométriques de l'acide linoléique 18:2 9c,12c, représentés par deux isomères principaux : l'acide ruménique ou 9c,11t, et l'isomère 10t,12c. L'acide ruménique est naturellement retrouvé dans les produits laitiers ; mais les tables de composition des aliments souffrent actuellement d'un manque de données concernant cet acide gras particulier. Les ALC, et notamment l'acide ruménique, semblent présenter des propriétés biologiques intéressantes pour la santé humaine, notamment lors de l'athérogenèse. Cependant, ces études utilisent des mélanges d'ALC. Le rôle respectif de chaque isomère est encore mal connu. Le premier volet de notre travail constituait déterminer les teneurs en acide ruménique de matières grasses laitières de plusieurs régions de France, sur plusieurs saisons, et d'étudier les variations de ces teneurs lors du passage du lait, à la crème, puis au beurre. Nos résultats montrent que les taux d'acide ruménique dans la matière grasse laitière varie avec la région et la saison étudiées. Ces différences pourraient être principalement imputables aux teneurs en acides gras poly-insaturés, et notamment en acide linoléique, de l'alimentation des bovins. Aucune variation n'est remarquée lors de la fabrication du beurre ; l'écrémage du lait, la maturation de la crème et le barattage ne semblent pas modifier les taux d'acide ruménique de la matière grasse laitière. Le deuxième volet de notre étude avait pour but de différencier le rôle de chacun des deux principaux isomères, et de focaliser sur les propriétés propres de l'acide ruménique, chez le hamster nourri avec un régime athérogène. Il ressort de nos travaux que l'acide ruménique exercerait un effet bénéfique supérieur à celui de l'isomère 10t,12c, sur une souche de hamster lors d'athérogenèse très précoce. Cependant cet effet bénéfique ne se fait plus sentir chez une autre espèce plus sensible à cette maladie, lors de stade plus avancé. En conclusion, l'exploration des propriétés biologiques de l'acide ruménique en regard de l'athérogenèse demande des travaux supplémentaires sur un modèle animal mieux adapté.

Le multicast fiable est certainement la solution la plus efficace pour<br />la distribution de contenu a un très grand nombre (potentiellement des<br />millions) de récepteurs. Dans cette perspective les protocoles ALC et<br />FLUTE, standardisés à l'IETF (RMT WG), ont été adoptés dans 3GPP/MBMS<br />et dans le DVB-H IP-Datacast dans les contextes des réseaux<br />cellulaires 3G.<br /><br />Ce travail se concentre sur le multicast fiable et a comme requis<br />principal le passage à l'échelle massif en terme de nombre de client.<br />Ce travail se base sur les solutions proposées a l'IETF RMT WG. Ces<br />protocoles de multicast fiable sont construit autour de plusieurs<br />briques de base que nous avons étudié en détail:<br /><br />- La brique Forward Error Correction (FEC) :<br /><br /> Nous examinons la classe de codes grands blocs<br /> Low Density Parity Check (LDPC). Nous concevons des dérivées<br /> de ces codes, et les analysons en détail. Nous en concluons que les<br /> codes LDPC et leur implémentation ont des performances très<br /> prometteuses, surtout si ils sont utilisées avec des fichiers de taille<br /> importante.<br /><br />- La brique contrôle de congestion :<br /><br /> Nous examinons le comportement dans la phase de démarrage de<br /> trois protocoles de contrôle de congestion RLC, FLID-SL, WEBRC.<br /> Nous démontrons que la phase de démarrage a un grand impact sur<br /> les performances de téléchargement.<br /><br /><br />Cette thèse a aussi plusieurs contributions au niveau applicatif:<br /><br />- Extensions de FLUTE :<br /><br /> Nous proposons un mécanisme permettant d'agréger plusieurs<br /> fichiers dans le protocole FLUTE. Ceci améliore les performance de<br /> transmission.<br /><br />- Streaming vidéo :<br /><br /> Nous proposons SVSoA, une solution de streaming basé sur ALC.<br /> Cette approche bénéficie de tout les avantages de ALC en terme de<br /> passage à l'échelle, contrôle de congestion et corrections d'erreurs

In Canada, patients who occupy hospital beds but do not require that intensity of care are called Alternate Level of Care (ALC) patients. ALC has numerous negative implications on patient health and the health care system. Early identification of patients who are at risk of becoming ALC could help decision-makers better manage the situation and alleviate this problem. This thesis evaluates the use of various ML algorithms in predicting ALC at two different time points in the patient’s trajectory. Moreover, it identifies the most important predictors of ALC in each time point and provides insights on how adding more information, at the expense of time for decision-making, would improve the predictive accuracy. / Thesis / Master of Science (MSc)