Cette thèse s’intéresse à la sémantique dénotationnelle (en théorie desmodèles et en théorie des jeux) de quatre langages de programmation logique: - LP, le plus restrictif de tous, - DLP, une extension de LP aux disjonctions, - LPN, une extension de LP aux négations, et - DLPN, qui inclut les deux.Ce manuscrit apporte trois contributions principales:(1) Un cadre abstrait pour la sémantique de la programmation logique yest défini, et toutes les approches sémantiques que nous étudions par lasuite prennent place dans ce cadre.Nous définissons la notion générale d'espace de valeurs de vérité commeune structure algébrique spécifique, satisfaisant un certain ensembled'axiomes. Les booléens forment l'exemple canonique d'un tel espace,mais nous devons étudier des cas plus généraux si nous voulonsconsidérer la "négation par l'échec". Pour cela, nous définissons etétudions une famille infinie d'espaces, paramétrée par un ordinal.(2) Une sémantique des jeux pour LP a été définie en 1986, et son étudea été approfondie en 1998. Elle a ensuite été étendue au cas desprogrammes LPN en 2005.Ici nous développons en détails une sémantique pour les programmes DLP.Nous prouvons qu'elle est correcte et complète par rapport aux modèlesminimaux de Minker.(3) Nous définissons un opérateur sémantique qui, étant donnée une sémantique abstraite d'un langage non disjonctif, la transforme en une sémantique disjonctive associée.La correction de cette transformation découle du fait qu'elle conserveles équivalences de sémantiques.Nous en présentons ensuite quelques applications qui permettent, entre autres, d'obtenir la première sémantique des jeux pour DLPN. / In this thesis, we study denotational semantics (model-theoretic andgame-theoretic) of four logic programming languages:- LP which is the most restrictive one;- DLP which extends LP by allowing disjunctions;- LPN which extends LP by allowing negations; and- DLPN which allows both.The three main contributions of this dissertation can be summarized as follows:(1) An abstract framework for logic programming semantics is definedand all semantic approaches that we study are placed within this framework.We define the general notion of a truth value space as an appropriate algebraicstructure that satisfies a set of axioms.The booleans form the canonical example of such a space, but we need toconsider much more general ones when dealing with negation-as-failure. Forthis we define and study an infinite family of spaces, parametrized over anordinal number.(2) A game semantics for LP was defined in 1986 and further studied in 1998.Then in 2005 it was extended for the case of LPN programs.Here a game semantics for DLP programs is developed in full detail; we provethat it is sound and complete with respect to the standard, minimal modelssemantics of Minker.(3) We define a semantic operator which transforms any given abstractsemantics of a non-disjunctive language to a semantics of the"corresponding" disjunctive one. We exhibit the correctness of thistransformation by proving that it preserves equivalences of semantics,and we present some applications of it, obtaining new game semantics forDLPN, among others.

The aim of this thesis is to develop theories and formal methods to endow a computing machinery with capabilities to identify, represent, reason and evaluate complex activities that are directed by an individual’s needs, goals, motives, preferences and environment, information which can be inconsistent and incomplete. Current methods for formalising and reasoning about human activity are typically limited to basic actions, e.g., walking, sitting, sleeping, etc., excluding elements of an activity. This research proposes a new formal activity-centric model that captures complex human activity based on a systemic activity structure that is understood as a purposeful, social, mediated, hierarchically organized and continuously developing interaction between people and word. This research has also resulted in a common-sense reasoning method based on argumentation, in order to provide defeasible explanations of the activity that an individual performs based on the activity-centric model of human activity. Reasoning about an activity is based on the novel notion of an argument under semantics-based inferences that is developed in this research, which allows the building of structured arguments and inferring consistent conclusions. Structured arguments are used for explaining complex activities in a bottom-up manner, by introducing the notion of fragments of activity. Based on these fragments, consistent argumentation based interpretations of activity can be generated, which adhere to the activity-centric model of complex human activity. For resembling the kind of deductive analysis that a clinician performs in the assessment of activities, two quantitative measurements for evaluating performance and capacity are introduced and formalized. By analysing these qualifiers using different argumentation semantics, information useful for different purposes can be generated. e.g., such as detecting risk in older adults for falling down, or more specific information about activity performance and activity completion. Both types of information can form the base for an intelligent machinery to provide tailored recommendation to an individual. The contributions were implemented in different proof-of-concept systems, designed for evaluating complex activities and improving individual’s health in daily life. These systems were empirically evaluated with the purpose of evaluating theories and methodologies with potential users. The results have the potential to be utilized in domains such as ambient assisted living, assistive technology, activity assessment and self-management systems for improving health.

Answer set programming (ASP) is a declarative programming paradigm oriented towards difficult combinatorial search problems. Syntactically, ASP programs look like Prolog programs, but solutions are represented in ASP by sets of atoms, and not by substitutions, as in Prolog. Answer set systems, such as Smodels, Smodelscc, and DLV, compute answer sets of a given program in the sense of the answer set (stable model) semantics. This is different from the functionality of Prolog systems, which determine when a given query is true relative to a given logic program. ASP has been applied to many areas of science and technology, from the design of a decision support system for the Space Shuttle to graph-theoretic problems arising in zoology and linguistics. The "native" answer set systems mentioned above are based on specialized search procedures. Usually these procedures are described fairly informally with the use of pseudocode. We propose an alternative approach to describing algorithms of answer set solvers. In this approach we specify what "states of computation" are, and which transitions between states are allowed. In this way, we define a directed graph such that every execution of a procedure corresponds to a path in this graph. This allows us to model algorithms of answer set solvers by a mathematically simple and elegant object, graph, rather than a collection of pseudocode statements. We use this abstract framework to describe and prove the correctness of the answer set solver Smodels, and also of Smodelscc, which enhances the former using learning and backjumping techniques. Answer sets of a tight program can be found by running a SAT solver on the program's completion, because for such a program answer sets are in a one-to-one correspondence with models of completion. SAT is one of the most widely studied problems in computational logic, and many efficient SAT procedures were developed over the last decade. Using SAT solvers for computing answer sets allows us to take advantage of the advances in the SAT area. For a nontight program it is still the case that each answer set corresponds to a model of program's completion but not vice versa. We show how to modify the search method typically used in SAT solvers to allow testing models of completion and employ learning to utilize testing information to guide the search. We develop a new SAT-based answer set solver, called Cmodels, based on this idea. We develop an abstract graph based framework for describing SAT-based answer set solvers and use it to represent the Cmodels algorithm and to demonstrate its correctness. Such representations allow us to better understand similarities and differences between native and SAT-based answer set solvers. We formally compare the Smodels algorithm with a variant of the Cmodels algorithm without learning. Abstract frameworks for describing native and SAT-based answer set solvers facilitate the development of new systems. We propose and implement the answer set solver called SUP that can be seen as a combination of computational ideas behind Cmodels and Smodels. Like Cmodels, solver SUP operates by computing a sequence of models of completion of the given program, but it does not form the completion. Instead, SUP runs the Atleast algorithm, one of the main building blocks of the Smodels procedure. Both systems Cmodels and SUP, developed in this dissertation, proved to be competitive answer set programming systems. / text

The first Part of the thesis explains from first principles the concept of "logic programming" and its practical application in the programming language Prolog. Prolog is a simple but powerful language which encourages rapid, error-free programming and clear, readable, concise programs. The basic computational mechanism is a pattern matching process ("unification") operating on general record structures ("terms" of logic). IThe ideas are illustrated by describing in detail one sizable Prolog program which implements a simple compiler. The advantages and practicability of using Prolog for "real" compiler implementation are discussed. The second Part of the thesis describes techniques for implementing Prolog efficiently. In particular it is shown how to compile the patterns involved in the matching process into instructions of a low-level language. This idea has actually been implemented in a compiler (written in Prolog) from Prolog to DECsystem-10 assembly language. However the principles involved are explained more abstractly in terms of a "Prolog Machine". The code generated is comparable in speed with that produced by existing DEC10 Lisp compilers. Comparison is possible since pure Lisp can be viewed as a (rather restricted) subset of Prolog. It is argued that structured data objects, such as lists and trees, can be manipulated by pattern matching using a "structure 'sharing" representation as efficiently as by conventional selector and constructor functions operating on linked records in "heap" storage. Moreover the pattern matching formulation actually helps the implementor to produce a better implementation.

Some upstream open reading frames (uORFs) regulate gene expression (i.e. they are functional) and can play key roles in keeping organisms healthy. However, how uORFs are involved in gene regulation is not het fully understood. In order to get a complete view of how uORFs are involved in gene regulation, it is expected that a large number of functional uORFs are needed. Unfortunately , lab experiments to verify that uORFs are functional are expensive. In this thesis, for the first time, the use of inductive logic programming (ILP) is explored for the task of learning which uORFs regulate gene expression in the yeast Saccharomyces cerevisiae. This work is directed to help select sets of candidate functional uORFs for experimental studies. With limited background knowledge, ILP can generate hypotheses which make the search for novel functional uORFs 17 times more efficient than random sampling. Adding mRNA secondary structure to the background knowledge results in hypotheses with significantly increased performance. This work is the first machine learning work to study both uORFs and mRNA secondary structures in the context of gene regulation. Using a novel combination of knowledge about biological conservation, gene ontology annotations and genes' response to different conditions results in hypotheses that are simple, informative, have an estimated sensitivity of 81% and provide provisional insights into biological characteristics of functional uORFs. The hypotheses predict 299 further genes to have 450 novel functional uORFs. A comparison with a related study suggests that 8 of these predicted functional uORFs (from 8 genes) are strong candidates for experimental studies.

This research establishes the feasibility and potential utility of a software mechanism which employs artificial intelligence techniques to enhance the capabilities of standard discrete event simulators. As background, current methods of integrating artificial intelligence with simulation and relevant research are briefly reviewed.

Inductive logic programming is a discipline investigating invention of clausal theories from observed examples such that for given evidence and background knowledge we are finding a hypothesis covering all positive examples and excluding all negative ones. In this thesis we extend an existing work on template consistency to general consistency. We present a three-phase algorithm DeMeR decomposing the original problem into smaller subtasks, merging all subsolutions together yielding a complete solution and finally refining the result in order to get a compact final hypothesis. Furthermore, we focus on a method how each individual subtask is solved and we introduce a generate-and-test method based on the probabilistic history-driven approach for this purpose. We analyze each stage of the proposed algorithms and demonstrate its impact on a runtime and a hypothesis structure. In particular, we show that the first phase of the algorithm concentrates on solving the problem quickly at the cost of longer solutions whereas the other phases refine these solutions into an admissible form. Finally, we prove that our technique outperforms other algorithms by comparing its results for identifying common structures in random graphs to existing systems.

To learn a probabilistic logic program is to find a set of probabilistic rules that best fits some data, in order to explain how attributes relate to one another and to predict the occurrence of new instantiations of these attributes. In this work, we focus on acyclic programs, because in this case the meaning of the program is quite transparent and easy to grasp. We propose that the learning process for a probabilistic acyclic logic program should be guided by a scoring function imported from the literature on Bayesian network learning. We suggest novel techniques that lead to orders of magnitude improvements in the current state-of-art represented by the ProbLog package. In addition, we present novel techniques for learning the structure of acyclic probabilistic logic programs. / O aprendizado de um programa lógico probabilístico consiste em encontrar um conjunto de regras lógico-probabilísticas que melhor se adequem aos dados, a fim de explicar de que forma estão relacionados os atributos observados e predizer a ocorrência de novas instanciações destes atributos. Neste trabalho focamos em programas acíclicos, cujo significado é bastante claro e fácil de interpretar. Propõe-se que o processo de aprendizado de programas lógicos probabilísticos acíclicos deve ser guiado por funções de avaliação importadas da literatura de aprendizado de redes Bayesianas. Neste trabalho s~ao sugeridas novas técnicas para aprendizado de parâmetros que contribuem para uma melhora significativa na eficiência computacional do estado da arte representado pelo pacote ProbLog. Além disto, apresentamos novas técnicas para aprendizado da estrutura de programas lógicos probabilísticos acíclicos.

O Aprendizado de Máquina trata da questão de como desenvolver programas de computador capazes de aprender um conceito ou hipótese a partir de um conjunto de exemplos ou casos observados. Baseado no conjunto de treinamento o algoritmo de aprendizado induz a classificação de uma hipótese capaz de determinar corretamente a classe de novos exemplos ainda não rotulados. Linguagens de descrição são necessárias para escrever exemplos, conhecimento do domínio bem como as hipóteses aprendidas a partir dos exemplos. Em geral, essas linguagens podem ser divididas em dois tipos: linguagem baseada em atributo-valor ou proposicional e linguagem relacional. Algoritmos de aprendizado são classificados como proposicional ou relacional dependendo da liguagem de descrição que eles utilizam. Além disso, no aprendizado simbólico o objetivo é gerar a classificação de hipóteses que possam ser facilmente interpretadas pelos humanos. Algoritmos de aprendizado proposicional utilizam a representação atributo-valor, a qual é inadequada para representar objetos estruturados e relações entre esses objetos. Por outro lado, a Programação lógica Indutiva (PLI) é realizada com o desenvolvimento de técnicas e ferramentas para o aprendizado relacional. Sistemas de PLI são capazes de aprender levando em consideração conhecimento do domínio na forma de um programa lógico e também usar a linguagem de programas lógicos para descrever o conhecimento induzido. Neste trabalho foi implementado um módulo chamado Kaeru para converter dados no formato atributo-valor para o formato relacional utilizado pelo sistema de PLI Aleph. Uma série de experimentos foram realizados com quatro conjuntos de dados naturais e um conjunto de dados real no formato atributo valor. Utilizando o módulo conversor Kaeru esses dados foram convertidos para o formato relacional utilizado pelo Aleph e hipóteses de classificação foram induzidas utilizando aprendizado proposicional bem como aprendizado relacional. É mostrado também, que o aprendizado proposicional pode ser utilizado para incrementar o conhecimento do domínio utilizado pelos sistemas de aprendizado relacional para melhorar a qualidade das hipóteses induzidas. / Machine Learning addresses the question of how to build computer programs that learn a concept or hypotheses from a set of examples, objects or cases. Descriptive languages are necessary in machine learning to describe the set of examples, domain knowledge as well as the hypothesis learned from these examples. In general, these languages can be divided into two types: languages based on attribute values, or em propositional languages, and relational languages. Learning algorithms are often classified as propositional or relational taking into consideration the descriptive language they use. Typical propositional learning algorithms employ the attribute value representation, which is inadequate for problem-domains that require reasoning about the structure of objects in the domain and relations among such objects. On the other hand, Inductive Logig Programming (ILP) is concerned with the development of techniques and tools for relational learning. ILP systems are able to take into account domain knowledge in the form of a logic program and also use the language of logic programs for describing the induced knowledge or hypothesis. In this work we propose and implement a module, named kaeru, to convert data in the attribute-value format to the relational format used by the ILP system Aleph. We describe a series of experiments performed on four natural data sets and one real data set in the attribute value format. Using the kaeru module these data sets were converted to the relational format used by Aleph and classifying hipoteses were induced using propositional as well as relational learning. We also show that propositional knowledge can be used to increment the background knowledge used by relational learners in order to improve the induded hypotheses quality.

Este trabalho investiga Aprendizado Indutivo de Máquina como função das linguagens de descrição, utilizadas para expressar instancias, conceitos e teoria do domínio. A ampliação do poder de representação do aprendizado proporcional e abordada no contexto de indução construtiva, no domínio de funções booleanas, com a proposta de uma estratégia de composição de atributos denominada root-fringe. Avaliações experimentais dessa e de outras estratégias de construção de novos atributos foram conduzidas e os resultados analisados. Dois métodos de poda, para tratamento de ruídos, em aprendizado de arvores de decisão, foram avaliados num ambiente de indução construtiva e os resultados discutidos. Devido a limitação do aprendizado proposicional, foram investigadas formas de ampliação dos limites do aprendizado, através da ampliação do poder representacional das linguagens de descrição. Foi escolhida Programação Lógica Indutiva - PLI - que e um paradigma de aprendizado indutivo que usa restrições de Lógica de Primeira Ordem como linguagens de descrição. O aprendizado em PLI só é factível quando as linguagens utilizadas estão restritas e é fortemente controlado, caso contrário, o aprendizado em PLI se torna indecidível. A pesquisa em PLI se direcionou a formas de restrição das linguagens de descrição da teoria do domínio e de hipóteses. Três algoritmos que \"traduzem\" a teoria do domínio de sua forma intencional, para extensional, são apresentados. As implementações de dois deles são discutidas. As implementações realizadas deram origem a dois ambientes experimentais de aprendizado: o ambiente proposicional experimental, do qual fazem parte o ambiente experimental construtivo, e o ambiente experimental relacional. / This work investigates Inductive Machine Learning as a function of the description languages employed to express instances, concepts and domain theory. The enlargement of the representational power of propositional learning methods is approached via constructive induction, in the domain of boolean functions, through the proposal of a bias for composing attributes, namely, the bias root-fringe. Experimental evaluation of root-fringe, as well as other biases for constructing new attributes was conducted and the results analyzed. Two pruning methods for decision trees were evaluated in an environment of constructive induction and the results discussed. Due to the limitations of propositional learning, ways of enlarging the limits of the learning process were investigated through enlarging the representational power of the description languages. It was chosen Inductive Logic Programming - ILP - that is an inductive learning paradigm that uses restrictions of First Order Logic as description languages. Learning using ILP is only feasible when the languages are restricted and are strongly controlled; otherwise, learning in ILP becomes undecidible. Research work in ILP was directed towards restricting domain theory and hypotheses description languages. Three algorithms that \"translate\" the intentional expression of a domain theory into its extensional expression are presented. The implementations of two of them are discussed. The implementations gave rise to two experimental learning environments: the propositional environment, which includes the constructive environment, and the relational environment.