Spelling suggestions: "subject:"operadores dde ponto fio"" "subject:"operadores dde ponto fix""
1 |
Complexidade descritiva das lógicas de ordem superior com menor ponto fixo e análise de expressividade de algumas lógicas modais / Descriptive complexity of the logic of higher order with lower fixed point and analysis of expression of some modal logicsFreire, Cibele Matos January 2010 (has links)
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 em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2010. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T12:35:52Z
No. of bitstreams: 1
2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-15T12:43:24Z (GMT) No. of bitstreams: 1
2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5) / Made available in DSpace on 2016-07-15T12:43:24Z (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 l ogicas para caracterizar classes problemas pelo vi es da complexidade. Desde 1974, quando Fagin provou que NP e capturado pela l ogica existencial de segunda-ordem, considerado o primeiro resultado da area, outras rela c~oes entre l ogicas e classes de complexidade foram estabelecidas. Os resultados mais conhecidos normalmemte envolvem l ogica de primeira-ordem e suas extens~oes, e classes de complexidade polinomiais em tempo ou espa co. 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).
|
2 |
Complexidade descritiva das lÃgicas de ordem superior com menor ponto fixo e anÃlise de expressividade de algumas lÃgicas modais / Descriptive complexity of the logic of higher order with lower fixed point and analysis of expression of some modal logicsCibele Matos Freire 13 August 2010 (has links)
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)
|
3 |
Complexidade descritiva das lógicas de ordem superior com menor ponto fixo e análise de expressividade de algumas lógicas modais / Descriptive complexity of the logic of higher order with lower fixed point and analysis of expression of some modal logicsFreire, Cibele Matos January 2010 (has links)
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.
|
Page generated in 0.0893 seconds