Succinctness as a source of complexity in logical formalisms

DOI10.1016/S0168-0072(98)00057-8zbMath0933.03048MaRDI QIDQ1302307

Nicola Leone, Georg Gottlob, Helmut Veith

Publication date: 22 September 1999

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

databasedefault logicsecond-order logicnonmonotonic reasoningquery languageslogic programmingdescriptive complexity theorysuccinct problemsexpression complexityfirst-order logic with Henkin quantifiersquantifier-free interpretationsquntifier-free reductionsweak exponential hierarchies

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Second- and higher-order model theory (03C85) Descriptive complexity and finite models (68Q19)

Related Items (9)

Privacy Preservation Using Multi-context Systems and Default Logic ⋮ Solving abduction by computing joint explanations. Logic programming formalization, applications to P2P data integration, and complexity results ⋮ Truth definitions in finite models ⋮ Model-checking hierarchical structures ⋮ Complexity results for answer set programming with bounded predicate arities and implications ⋮ Complexity of super-coherence problems in ASP ⋮ Semantics and complexity of recursive aggregates in answer set programming ⋮ Abstraction for non-ground answer set programs ⋮ On the complexity of data disjunctions.

Uses Software

• Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of the leaf language classes
• Languages represented by Boolean formulas
• The strong exponential hierarchy collapses
• Succinct circuit representations and leaf language classes are basically the same concept
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Structure in complexity theory. Proceedings of the Conference held at the University of California, Berkeley, California, June 2-5, 1986
• Henkin quantifiers and complete problems
• The complexity of combinatorial problems with succinct input representation
• The method of forced enumeration for nondeterministic automata
• A logic for default reasoning
• Why not negation by fixpoint?
• The polynomial-time hierarchy
• Succinct representation, leaf languages, and projection reductions
• Expressive power and complexity of partial models for disjunctive deductive databases
• Computation times of NP sets of different densities
• Abduction from logic programs: Semantics and complexity
• Succinct representations of graphs
• Second order logic and the weak exponential hierarchies
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation
• Alternation
• Complete Problems Involving Boolean Labelled Structures and Projection Transactions
• Complexity Results for Nonmonotonic Logics
• Relativization of questions about log space computability
• Relativized logspace and generalized quantifiers over finite ordered structures
• The complexity of logic-based abduction
• A note on succinct representations of graphs
• On the Computational Complexity of Algorithms

This page was built for publication: Succinctness as a source of complexity in logical formalisms