Constraint logic programming (CLP) techniques can be used in protein side-chain placement, an important sub-task in comparative modelling. In a simple formulation values for domain variables represent rotamer side-chain conformations, and constraints represent atomic clashes. These constraints can be visualised using a "rotamer contact map", and observations made with this visualisation tool have been used to develop a strategy that overcomes limitations present in CLP caused by over-constrained residues. Null rotamers provide a mechanism that can automatically identify over-constrained residues. The use of null rotamers makes possible an iterative modelling strategy where, at each iteration, a CLP program is generated automatically; each program representing successively tighter packing constraints corresponding to larger atomic radii. Different CLP enumeration heuristics have been evaluated for use with this side-chain placement method, and it has been tested with several different rotamer libraries; a backbone-dependent rotamer library, when used with first-fail enumeration heuristics, was shown to be the most successful. Side-chain conformations predicted by this CLP method compare favourably against those predicted using other side-chain placement methods. The CLP method has been applied to two modelling problems. The first involved building models of class II MHC molecules in order to increase the utility of a peptide threading program. This program uses an allele's known or modelled 3D structure with a heuristic scoring function to predict peptides that are likely to bind to it - thus using CLP to model class II MHC alleles increases the program's utility. The second application used the CLP method to build structures of ribosome inactivating proteins (RIPs). These models were built using CLP together with comparative modelling approaches, and a model of bouganin, a recently identified wild RIF protein, has been built to help design engineered therapeutic proteins.

Made available in DSpace on 2014-06-12T15:52:36Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Devido á grande demanda por softwares cada vez mais robustos, complexos e flexíveis, e, sobretudo, pelo curtíssimo tempo de entrega exigido, a engenharia de software tem procurado novos meios de desenvolvimento que supram satisfatoriamente essas demandas. Uma forma de galgar esses novos patamares de produtividade provém do uso de uma metodologia baseada em agentes que se comunicam e com isso, ao invés dos programas serem estritamente programados, o comportamento destes sistemas de software emerge da interação de agentes, robôs, ou subsistemas aut onomos, independentes, além de declarativamente especificados. Isto provê a habilidade para automaticamente configurá -los, otimizá-los, monitorá-los, adaptá-los, diagnosticá-los, repará-los e protegê-los dentro do ambiente. Contudo, um grande problema das linguagens declarativas é a falta de mecanismos que permitem a melhor estruturação de dados, facilitando portanto, o reuso. Portanto, esta dissertação explica o desenvolvimento de nova linguagem lógica declarativa para programar sistemas de raciocínio automático de uma forma modularizada: C2HR∨. A linguagem base escolhida para a extensão com componentes lógicos foi CHR. Os motivos para essa escolha são definidos ao longo da dissertação. Duas abordagens, portanto, são apresentadas: a primeira, conhecida como CHRat, foi desenvolvida numa parceria juntamente com o grupo de pesquisas CONTRAINTES do INRIA/Rocquencourt-Paris, onde o programador ´e o responsável direto por definir os componentes CHR, permitindo o seu reuso por outros componentes; a segunda aplicação, CHRtp, visa atender prioritariamente requisitos de completude e, por isso, se baseia em procedimentos lógicos de inferência como: o raciocínio para frente, o raciocínio para trás, e a resolução/factoring. A dissertação mostra também alguns exemplos práticos, onde uso de componentes facilita radicalmente sua implementação. As contribuições almejadas com essa dissertação são: a definição de uma família bem formalizada de provadores de teoremas automáticos, que podem trabalhar com sentenças especificadas em lógica horn ou em lógica de primeira ordem, a extensão de CHR como uma linguagem modular de propósito geral, a melhor estruturação de bases conhecimentos e até o uso em conjunto de bases heterogêneas, a definição de uma linguagem para a fácil e direta estruturação de dados por meio de componentes, dentre outras

While there are efforts to establish a single international accounting standard, there are strong current and future needs to handle heterogeneous accounting methods and systems. We advocate a context-based approach to dealing with multiple accounting standards and equational ontological conflicts. In this paper we first define what we mean by equational ontological conflicts and then describe a new approach, using Constraint Logic Programming and abductive reasoning, to reconcile such conflicts among disparate information systems. In particular, we focus on the use of Constraint Handling Rules as a simultaneous symbolic equation solver, which is a powerful way to combine, invert and simplify multiple conversion functions that translate between different contexts. Finally, we demonstrate a sample application using our prototype implementation that demonstrates the viability of our approach. / Singapore-MIT Alliance (SMA)

<p>Model checking is a formal verification method where one tries to prove or disprove properties of a formal system. Typical systems one might want to prove properties within are network protocols and digital circuits. Typical properties to check for are safety (nothing bad ever happens) and liveness (something good eventually happens).</p><p>This thesis describes an implementation of a sound and complete model checker for Computation Tree Logic (CTL) using Constraint Logic Programming over Finite Domains (CLP(FD)). The implementation described uses tabled resolution to remember earlier computations, is parameterised by choices of computation strategies and can with slight modification support different constraint domains. Soundness under negation is maintained through a restricted form of constructive negation.</p><p>The computation process amounts to a fixpoint search, where a fixpoint is reached when no more extension operations has any effect. As results show, the choice of strategies does influence the efficiency of the computation. Soundness and completeness are of course independent of the choice of strategies. Strategies include how to choose the extension operation for the next step and whether to perform global or local rule instantiations, resulting in bottom-up or top-down computations respectively.</p>

Nous nous intéressons aux approches formelles pour le développement de systèmes réactifs critiques. Le langage synchrone Lustre pour la spécification de tels systèmes a subit des évolutions majeurs au cours des dernières années en intégrant dans sa sémantique à base flots de données synchrones des constructions de plus haut-niveau appelées automates de modes (dans le langage Scade 6). Ceux-ci mettent en œuvre l’activation de modes de calculs en fonction des états et des transitions de l’automate, et reposent pour cela sur la sémantique des horloges du langage Lustre. En particulier, nous étudiions la prise en compte des horloges et des automates de modes dans l’outil de génération de tests GATeL dédié à l’origine au langage Lustre mono-horloge (flots de données purs). GATeL génère automatiquement des séquences de tests pour un modèle à partir d’un objectif de test décrit en Lustre à travers une exploration en arrière des dépendances entre flots et selon des teniques de résolution de contraintes. Nous présentons ces différents domaines et la mise en oeuvre des modifications apportées à l’outil pour prendre en compte les automates de modes. Enfin, nous définissons des critères de couverture structurelle pour les automates de modes et montrons alors comment, en les traduisant de manière automatique sous forme d’objectifs de tests, GATeL permet de générer des séquences couvrant ces critères. / Lustre is a synchronous dataflow-oriented language for the specification of reactive systems. Since its definition, it has been extended to support mode automata, a formalism in which computation modes are activated according to an extended state-machine. The semantics of mode-automata is heavily based on an appropriate use of the clock sampling features of Lustre. We present the modifications made in GATeL, an automatic test sequences generator originally designed for a mono-rate subset of Lustre. GATeL performs a lazy goal-oriented test sequences generation, based on constraint logic programming. We modify it so that it can handle the temporal constraints of clocks internally and efficiently generate tests sequences from state-maines specifications. We also present some existing structural test criteria for state-machines and adapt them to the specific case of mode-automata.

Model checking is a formal verification method where one tries to prove or disprove properties of a formal system. Typical systems one might want to prove properties within are network protocols and digital circuits. Typical properties to check for are safety (nothing bad ever happens) and liveness (something good eventually happens). This thesis describes an implementation of a sound and complete model checker for Computation Tree Logic (CTL) using Constraint Logic Programming over Finite Domains (CLP(FD)). The implementation described uses tabled resolution to remember earlier computations, is parameterised by choices of computation strategies and can with slight modification support different constraint domains. Soundness under negation is maintained through a restricted form of constructive negation. The computation process amounts to a fixpoint search, where a fixpoint is reached when no more extension operations has any effect. As results show, the choice of strategies does influence the efficiency of the computation. Soundness and completeness are of course independent of the choice of strategies. Strategies include how to choose the extension operation for the next step and whether to perform global or local rule instantiations, resulting in bottom-up or top-down computations respectively.

This paper describes automated examination scheduling for the Faculty of Information Technology of Brno University of Technology. It specifies a list of restrictions that must by satisfied. Furthermore, this limitations are classified due to their influence on a quality of the final version of the examination schedule. There are two types of restrictions; soft and hard. The task is to find such a solution that satisfies all hard constraints and breaks the minimum of soft constraints using techniques described in this paper.

Temporal Action Logic is a well established logical formalism for reasoning about action and change that has long been used as a formal specification language. Its first-order characterization and explicit time representation makes it a suitable target for automated theorem proving and the application of temporal constraint solvers. We introduce a translation from a subset of Temporal Action Logic to constraint logic programs that takes advantage of these characteristics to make the logic applicable, not just as a formal specification language, but in solving practical reasoning problems. Extensions are introduced that enable the generation of action sequences, thus paving the road for interesting applications in deductive planning. The use of qualitative temporal constraints makes it possible to follow a least commitment strategy and construct partially ordered plans. Furthermore, the logical language and logic program translation is extended with the notion of composite actions that can be used to formulate and execute scripted plans with conditional actions, non-deterministic choices, and loops. The resulting planner and reasoner is integrated with a graphical user interface in our autonomous helicopter research system and applied to logistics problems. Solution plans are synthesized together with monitoring constraints that trigger the generation of recovery actions in cases of execution failures.

Este trabalho a dedicado ao estudo da exploração de paralelismo OU na programação em lógica com restrições em ambientes distribuídos. A programação em lógica, cuja linguagem mais significativa 6 Prolog, tem como premissa a utilização da lógica de predicados como linguagem computacional. A programação em lógica com restrições (CLP) é uma extensão da programação em lógica, onde busca-se a eficiência e a possibilidade de executar novas classes de problemas. Variáveis em CLP podem pertencer a domínios específicos como, por exemplo, reais ou booleanos. O principal conceito introduzido é a restrição. Restrição a uma equação que representa uma certa informação sobre uma variável e a sua relação com outras variáveis. o uso de restrições foi proposto para diminuir o espaço de busca na execução dos programas. Apesar de mais eficientes que a programação em lógica clássica, para algumas aplicações reais o desempenho das linguagens CLP ainda é insatisfatório. Por isso, é necessário buscar alternativas novas como a execução em paralelo. A exploração de paralelismo implícito em programas em 1ógica já demonstrou resultados promissores. Vários modelos foram propostos e implementados utilizando as duas principais fontes de paralelismo — E e OU — de forma isolada ou combinada. O objetivo principal desse trabalho é apresentar o modelo pclp(FD) de exploração de paralelismo OU multi-sequêncial para um ambiente com memória distribuída. O modelo pclp(FD) caracteriza-se pela existência de vários trabalhadores, cada um deles possuindo uma maquina abstrata completa. O escalonamento de tarefas a realizado por uma política dinâmica e distribuída. Uma tarefa em pclp(FD) equivale a um ponto de escolha e a um contexto de execução. O contexto de execução a formado por porções da pilha do exportador. Para que o importador tenha acesso ao contexto de execução utiliza-se a cópia incremental, que a uma das varias técnicas possíveis. Cada trabalhador possui a sua própria copia privada das pilhas de execução. A cópia caracteriza-se pelo envio das pilhas de execução do exportador para uma área privada do importador. A cópia incremental é uma técnica mais otimizada que verifica a existência de partes comuns entre os trabalhadores, copiando apenas as panes novas. O algoritmo de cópia incremental proposto no modelo a feito sem nenhuma centralização de informação do estado das pilhas. O projeto e implementação de um prot6tipo para esse modelo, utilizando a linguagem clp(FD), que implementa CLP sobre domínios finitos, permitirá uma analise das vantagens e desvantagens do modelo proposto. Os resultados obtidos com a análise servirão de base para trabalhos futuros, visando aprimorar a implementação e o modelo. / This work is dedicated to the study of the exploration of OR parallelism in Constraint Logic Programming for distributed environment. Logic Programming, which the most meaningful language is Prolog, has as premise the use of the logic of predicates as computational language. Constraint Logic Programming or CLP is an extension of the logic programming, where efficiency and the possibility to execute new kinds of problems are searched. A variable in CLP can belong to specific domains as, for example, Real or Boolean. The main concept introduced is the constraint. Constraint is an equation that represents a certain information over a variable and its relation with others variables. The use of constraints was proposed to decrease search space in the program execution. Although it is more efficient than classic logic programming, for some real applications, the performance of CLP languages still is unsatisfactory. So, it is necessary to search alternatives as parallel execution. The exploration of implicit parallelism in programs in logic has already demonstrated promising results. Several models have been proposed and implemented using the two main sources of parallelism - AND and OR — in an isolated or combined form. The main objective of this work is to present the pclp(FD) model of exploration of multi-sequential OR parallelism for a distributed memory environment. The pclp(FD) model is characterized for the existence of some workers, each one of them possessing a complete abstract machine. Task scheduling is executed by one dynamic and distributed policy. A task in pclp(FD) is equivalent to a choice point and an execution context. Execution context is formed by portions of the stack of the exporter. So that importer has access to the execution context, it uses incremental copy, which is one of the several possible techniques. The copy is characterized for sending execution stacks of the exporter to a private area of the importer, that is, each worker possesses its private copy of the execution stacks. The incremental copy is a more optimized technique that verifies the existence of common parts between workers, copying only the new ones. The incremental copy algorithm proposed in the model executes without centralized information of the state of the stacks. A prototype project and implementation for this model, using the language clp(FD), that implements CLP over finite domains, will allow an analysis of advantages and disadvantages of the considered model. The results gotten with the analysis will serve of base for future works, aiming to improve the implementation and the model.

<p>Temporal Action Logic is a well established logical formalism for reasoning about action and change that has long been used as a formal specification language. Its first-order characterization and explicit time representation makes it a suitable target for automated theorem proving and the application of temporal constraint solvers. We introduce a translation from a subset of Temporal Action Logic to constraint logic programs that takes advantage of these characteristics to make the logic applicable, not just as a formal specification language, but in solving practical reasoning problems. Extensions are introduced that enable the generation of action sequences, thus paving the road for interesting applications in deductive planning. The use of qualitative temporal constraints makes it possible to follow a least commitment strategy and construct partially ordered plans. Furthermore, the logical language and logic program translation is extended with the notion of composite actions that can be used to formulate and execute scripted plans with conditional actions, non-deterministic choices, and loops. The resulting planner and reasoner is integrated with a graphical user interface in our autonomous helicopter research system and applied to logistics problems. Solution plans are synthesized together with monitoring constraints that trigger the generation of recovery actions in cases of execution failures.</p>