skip to main content
Lingue:
Cerca la mia strategia di ricerca: Mostra risultati con: Mostra risultati con:

Succinctness as a source of complexity in logical formalisms

Gottlob, Georg ; Leone, Nicola ; Veith, Helmut

Annals of pure and applied logic, 1999, Vol.97 (1), p.231-260 [Rivista Peer Reviewed]

Fulltext disponibile

Citazioni Citato da
  • Titolo:
    Succinctness as a source of complexity in logical formalisms
  • Autore: Gottlob, Georg ; Leone, Nicola ; Veith, Helmut
  • Editore: Elsevier B.V
  • Diritti: 1999
  • Note di contenuto: The often observed complexity gap between the expressiveness of a logical formalism and its exponentially harder expression complexity is proven for all logical formalisms which satisfy natural closure conditions. The expression complexity of the prefix classes of second-order logic can thus be located in the corresponding classes of the weak exponential hierarchies; further results about expression complexity in database theory, logic programming, nonmonotonic reasoning, first-order logic with Henkin quantifiers and default logic are concluded. The proof method illustrates the significance of quantifier-free interpretations in descriptive complexity theory.
  • Fa parte di: Annals of pure and applied logic, 1999, Vol.97 (1), p.231-260
  • Soggetti: Expression complexity ; Quantifier-free reductions ; Descriptive complexity theory ; Second order logic ; Succinct problems ; Query languages
  • Lingua: Inglese
  • Tipo: Articolo
  • Identificativo: ISSN: 0168-0072
    DOI: 10.1016/S0168-0072(98)00057-8
  • Fonte: ScienceDirect Open Access Titles
    Elsevier:ScienceDirect:Open Access

Ricerca in corso nelle risorse remote ...