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
logica de primeira-ordem estendida com o operador de menor ponto xo captura a clsse
P e que a logica de segunda-ordem estendida com o operador de fecho transitivo captura
a classe PSPACE. Nesta dissertaÃÃo, analisaremos inicialmente a expressividade de algumas
logicas modais com relacÃo ao problema de decisÃo REACH e veremos que e possvel
expressa-lo com as logicas temporais CTL e CTL. Analisaremos tambem o uso combinado
de logicas de ordem superior com o operador de menor ponto xo e obteremos como
resultado que cada nvel dessa hierarquia captura cada nvel da hierarquia determinstica
em tempo exponencial. Como corolario, provamos que a hierarquia de HOi(LFP) nÃo
colapsa, ou seja, HOi(LFP) HOi+1(LFP) / 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)
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:4606 |
| Date | 13 August 2010 |
| Creators | Cibele Matos Freire |
| Contributors | Ana Teresa de Castro Martins, Carlos Eduardo Fisch de Brito, Mario Roberto Folhadela Benevides, JoÃo Fernando Lima AlcÃntara |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds