Mostrando 3 resultados de: 3
Filtros aplicados
Subtipo de publicación
Article(3)
Área temáticas
Lingüística(2)
Ciencias de la computación(1)
Inglés e inglés antiguo (anglosajón)(1)
Lengua(1)
Métodos informáticos especiales(1)
Origen
scopus(3)
Universal first-order logic is superfluous for NL, P, NP and CO NP
ArticleAbstract: In this work we continue the syntactic study of completeness that began with the works of Immerman aPalabras claves:Complexity classes, descriptive complexity, First order projections, NP completeness, Problems and reductionsAutores:Bonet B., Nerio BorgesFuentes:scopusUniversal first-order logic is superfluous in the second level of the polynomial-time hierarchy
ArticleAbstract: In this paper we prove that ∀FO, the universal fragment of first-order logic, is superfluous in Σ2pPalabras claves:Computational complexity, descriptive complexity, Graph Theory, MATHEMATICAL LOGICAutores:Nerio Borges, Pin E.Fuentes:scopusSyntactic characterizations of completeness using duals and operators
ArticleAbstract: This article extends the work laid down by Medina and Immerman for the syntactic characterization ofPalabras claves:Canonical forms, completeness, descriptive complexity, Dual operator, Syntactic operatorsAutores:Bonet B., Nerio BorgesFuentes:scopus