FERREIRA, Francicleber Martins. Expressividade e complexidade em lógicas preferenciais, híbridas e de grau limitado. 2012. 130 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2012. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-20T11:58:10Z No. of bitstreams: 1 2012_tese_fmferreira.pdf: 772301 bytes, checksum: b1e1a404221e38ffb8e0712513749a4c (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-25T11:47:07Z (GMT) No. of bitstreams: 1 2012_tese_fmferreira.pdf: 772301 bytes, checksum: b1e1a404221e38ffb8e0712513749a4c (MD5) / Made available in DSpace on 2016-07-25T11:47:07Z (GMT). No. of bitstreams: 1 2012_tese_fmferreira.pdf: 772301 bytes, checksum: b1e1a404221e38ffb8e0712513749a4c (MD5) Previous issue date: 2012 / We investigate the model theory of Preferential Logics, Hybrid Logic and fragments of Second-Order Logic with respect to finite models. The semantics of these logics differ from the semantics of classical logics either by using relations between models or by restricting the cardinality of the models considered. This work has three main parts. In the first part of this work we study the model theory of preferential logics. Preferential logics arise in the context of nonmonotonic reasoning in Artificial Intelligence. The main characteristic of those logics is the existence of a relation between models. It allows the definition of a nonmonotonic consequence relation by considering the minimal models of a set of sentences. Using the approach of Abstract Model Theory we generalize some expressiveness results to classes of preferential logics. We show that whenever a class of minimal models of a finite set of sentences is axiomatizable, without considering the preference relation, then it is finitely axiomatizable. We also show that when such class of minimal models implicitly defines a symbol, then the finite axiomatization can be put in a very specic form, namely, the initial set of sentences plus a explicit definition for the symbol. In the second part of this work, we investigate the finite model theory of Hybrid Logic. Hybrid Logics are extensions of modal logics with hybrid terms which refer to single states in a Kripke model. We study the complexity of the model- and frame-checking problems for Hybrid Logic. We show that for each graph problem in the Polynomial Hierarchy and each natural number n there is a formula which expresses this problem for graphs of cardinality n. We also show that the size of such formulas is bounded by a polynomial in n. We show that one can disregard the global modalities if one consider only connected graphs with loops. We define fragments which correspond to each degree of the Polynomial Hierarchy. This leads to an alternative proof of the NP-hardness of the model-checking problem for an specic fragment of Full Hybrid Logic. In the last part of this work, we explore the descriptive complexity of the logic obtained by restricting second-order quantication to relations of bounded degree. Based on previous work from Schwentick et al. and Grandjean and Olive, we introduce the Bounded-Degree Second-Order Logic and show that it captures the class ALIN of classes of unary structures accepted by a alternating random access machine in linear time and bounded number of alternations. We also extend this logic with the transitive closure operator on high-order relations on bounded-degree relations. We show that the Bounded-Degree Second-Order Logic with Transitive Closure Operator captures linear number of registers in a nondeterministic random access machine provided that registers store values bounded by a linear function in the cardinality of the input structure. / Nós investigamos a teoria dos modelos de Lógicas Preferenciais, Lógica Híbrida e fragmentos da Lógica de Segunda-Ordem com relação a modelos finitos. A semânticas dessas lógicas diferem da abordagem clássica pelo uso de relações entre modelos ou por restringir a cardinalidade dos modelos a cardinais finitos. Este trabalho tem três partes. Na primeira parte deste trabalho nós estudamos a teoria dos modelos de lógicas preferenciais. Lógicas preferenciais surgem no contexto do raciocínio não-monotônico em Inteligência Artificial. A principal característica dessas lógicas é a existência de uma relação entre modelos. Isso permite a definição de uma relação de consequência não monotônica considerando-se os modelos minimais de um conjunto de sentenças. Usando a abordagem da Teoria dos Modelos Abstrata, nós generalizamos alguns resultados de expressividade para classes de lógicas preferenciais. Nós mostramos que sempre que uma classe de modelos minimais de um conjunto finito de sentenças é axiomatizável, então tal classe é finitamente axiomatizável. Nós mostramos que se tal classe define implicitamente um símbolo do vocabulário, existe uma axiomatização finita de uma forma particular, a saber, o conjunto finito de sentenças inicial mais uma definição explícita para o símbolo definido. Na segunda parte desse trabalho, nós investigamos a teoria dos modelos finitos da Lógica Híbrida. Lógicas Híbridas são extensões da lógica modal através de termos híbridos que se referem a estados individuais em um modelo de Kripke. Nós estudamos a complexidade computacional dos problemas de model- e frame- checking para a Lógica Híbrida. Nós mostramos que para cada problema de grafos na Hierarquia Polinomial e cada número n, existe uma fórmula que exprime esse problema para grafos de cardinalidade n. Nós mostramos que o tamanho das fórmulas é limitado por um polinômio em n. Nós mostramos que podemos abrir mão das modalidades globais se nos limitarmos a grafos conexos com loops. Nós definimos fragmentos da Lógica Híbrida que correspondem a cada nível da Hierarquia Polinomial. Isso nos leva a uma prova alternativa da NP-dificuldade do problema de model-checking para um fragmento específico de da Lógica Híbrida. Na última parte desse trabalho, nós exploramos a complexidade descritiva da lógica obtida ao restringirmos a quantificação de segunda-ordem a relações de grau limitado. Baseados em trabalhos anteriores de Schwentick et al. e de Grandjean e Olive, nós introduzimos a Lógica de Segunda-Ordem de Grau Limitado e mostramos que ela captura a classe ALIN de classes de estruturas unárias aceitas por uma máquina de acesso randômico em tempo linear e um número fixo de alternâncias dependente apenas do problema. Nós estendemos essa lógica com o operador de fecho transitivo sobre relações de ordem superior sobre relações de grau limitado. Nós mostramos que a Lógica de Segunda- Ordem de Grau Limitado com Fecho Transitivo captura quantidade linear de registradores em uma máquina de acesso randômico não-determinística onde os valores armazenados em cada registrador durante a computação são limitados por uma função linear na cardinalidade da estrutura de entrada.

FROTA, Débora Farias. Uma Lógica de Descrição Default. 2011. 79 f. : Dissertação (mestrado) - Universidade Federal do Ceará. Centro de Ciências, Coordenação do Programa de Pós-Graduação em Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-20T19:27:19Z No. of bitstreams: 1 2011_dis_dffrota.pdf: 945021 bytes, checksum: 9adb958d87b14104dcd8db9fc4c4bd6f (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-20T19:28:34Z (GMT) No. of bitstreams: 1 2011_dis_dffrota.pdf: 945021 bytes, checksum: 9adb958d87b14104dcd8db9fc4c4bd6f (MD5) / Made available in DSpace on 2016-06-20T19:28:34Z (GMT). No. of bitstreams: 1 2011_dis_dffrota.pdf: 945021 bytes, checksum: 9adb958d87b14104dcd8db9fc4c4bd6f (MD5) Previous issue date: 2011 / Knowledge formalization and reasoning automatization are central within Arti cial Intelligence. First Order Logic has been traditionally used for such purposes. However, it is better suited to deal with complete knowledge in ideal circumstances. In real situations, in which the knowledge is partial, First Order Logic is not su cient. Nonmonotonic logics have been proposed to better cope with practical reasoning. A successful formalization of nonmonotonic reasoning is the Reiter's default logic which extends classical logic with default rules. Unfortunately, default logic is undecidable. In this work, we propose a description default logic expressible enough to formalize practical reasoning in knowledge bases. It has as its monotonic basis the ALC Description Logic. We add some restrictions to the application of defaults in order to obtain nice properties such as coherence and the elimination of anomalous extensions. We present the main algorithms used to build an extension with a step by step complexity analysis. / A formalização do conhecimento e a automatização do raciocínio são assuntos centrais de pesquisa da Inteligência Arti cial. A Lógica de Primeira Ordem tem sido tradicionalmente utilizada para tais propósitos. No entanto, ela é mais adequada para lidar com conhecimento completo em circunstâncias ideais. Em situações reais, nas quais o conhecimento é parcial, a Lógica de Primeira Ordem não é su ciente. Lógicas não-monotônicas têm sido propostas para melhor lidar com o raciocínio prático. Uma formalização do raciocínio não-monotônico bem-sucedida é a Lógica Default de Reiter que estende a Lógica de Primeira Ordem com regras default. Infelizmente, a Lógica Default é indecidível. Nesta dissertação, propomos uma Lógica de Descrição Default expressiva o su ciente para formalizar o raciocínio prático sobre bases de conhecimento. Ela tem como base monotônica a Lógica de Descrição ALC. Adicionamos algumas restrições à aplicação dos defaults a m de obter propriedades interessantes, tais como a coerência e a eliminação de extensões anômalas. Apresentamos os principais algoritmos usados para construir uma extensão com um passo-a-passo e suas análise de complexidade.

Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-14T19:46:59Z No. of bitstreams: 1 2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-14T19:48:16Z (GMT) No. of bitstreams: 1 2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5) / Made available in DSpace on 2016-06-14T19:48:16Z (GMT). No. of bitstreams: 1 2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5) Previous issue date: 2010 / In Descriptive Complexity, we investigate the use of logics to characterize computational classes os problems through complexity. Since 1974, when Fagin proved that the class NP is captured by existential second-order logic, considered the rst result in this area, other relations between logics and complexity classes have been established. Wellknown results usually involve rst-order logic and its extensions, and complexity classes in polynomial time or space. Some examples are that the rst-order logic extended by the least xed-point operator captures the class P and the second-order logic extended by the transitive closure operator captures the class PSPACE. In this dissertation, we will initially analyze the expressive power of some modal logics with respect to the decision problem REACH and see that is possible to express it with temporal logics CTL and CTL . We will also analyze the combined use of higher-order logics extended by the least xed-point operator and obtain as result that each level of this hierarchy captures each level of the deterministic exponential time hierarchy. As a corollary, we will prove that the hierarchy of HOi(LFP), for i 2, does not collapse, that is, HOi(LFP) HOi+1(LFP) / Em Complexidade Descritiva investigamos o uso de logicas para caracterizar classes problemas pelo vies da complexidade. Desde 1974, quando Fagin provou que NP e capturado pela logica existencial de segunda-ordem, considerado o primeiro resultado da area, outras relac~oes entre logicas e classes de complexidade foram estabelecidas. Os resultados mais conhecidos normalmemte envolvem logica de primeira-ordem e suas extens~oes, e classes de complexidade polinomiais em tempo ou espaco. Alguns exemplos são que a l ogica de primeira-ordem estendida com o operador de menor ponto xo captura a clsse P e que a l ogica de segunda-ordem estendida com o operador de fecho transitivo captura a classe PSPACE. Nesta dissertação, analisaremos inicialmente a expressividade de algumas l ogicas modais com rela cão ao problema de decisão REACH e veremos que e poss vel express a-lo com as l ogicas temporais CTL e CTL . Analisaremos tamb em o uso combinado de l ogicas de ordem superior com o operador de menor ponto xo e obteremos como resultado que cada n vel dessa hierarquia captura cada n vel da hierarquia determin stica em tempo exponencial. Como corol ario, provamos que a hierarquia de HOi(LFP) não colapsa, ou seja, HOi(LFP) HOi+1(LFP) / FREIRE, Cibele Matos. Complexidade descritiva das lógicas de ordem superior com menor ponto fixo e análise de expressividade de algumas lógicas modais. 2010. 54 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2010.