Succinctness as a source of complexity in logical formalisms Export

@article{GLV99, abstract = {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.}, author = {Gottlob, G. and Leone, N. and Veith, H.}, citeulike-article-id = {2723757}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0168-0072(98)00057-8}, citeulike-linkout-1 = {http://www.ingentaconnect.com/content/els/01680072/1999/00000097/00000001/art00057}, doi = {10.1016/S0168-0072(98)00057-8}, issn = {0168-0072}, journal = {Annals of Pure and Applied Logic}, keywords = {and, combined, complexity, computational, data, descriptive, expression}, month = {March}, pages = {231--260}, posted-at = {2008-04-27 12:38:34}, priority = {0}, publisher = {Elsevier}, title = {Succinctness as a source of complexity in logical formalisms}, url = {http://dx.doi.org/10.1016/S0168-0072(98)00057-8}, year = {1999} }

TY - JOUR ID - GLV99 L3 - citeulike-article-id:2723757 N2 - 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. JF - Annals of Pure and Applied Logic SN - 0168-0072 EP - 260 TI - Succinctness as a source of complexity in logical formalisms PB - Elsevier SP - 231 KW - and KW - combined KW - complexity KW - computational KW - data KW - descriptive KW - expression AU - Gottlob, G AU - Leone, N AU - Veith, H PY - 1999/03// UR - http://dx.doi.org/10.1016/S0168-0072(98)00057-8 ER -