Succinctness as a source of complexity in logical formalisms

DOI10.1016/S0168-0072(98)00057-8MaRDI QIDQ1302307zbMATH OpenFDO

Authors Georg Gottlob, N. Leone, Helmut Veith

Publication date 22 September 1999

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

Full work available at URL https://doi.org/10.1016/S0168-0072(98)00057-8

zbMATH Keywords

databasedefault logicdescriptive complexity theoryexpression complexityfirst-order logic with Henkin quantifierslogic programmingnonmonotonic reasoningquantifier-free interpretationsquery languagesquntifier-free reductionssecond-order logicsuccinct problemsweak exponential hierarchies

Mathematics Subject Classification ID

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

Recommendations

• Computational complexity and the expressive power of logics
• Expressing versus proving: relating forms of complexity in logic
• scientific article; zbMATH DE number 1342206
• The Kolmogorov expression complexity of logics

Cites work

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

Cited in

(9)

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

Describes a project that uses

Uses Software

• Datalog

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1302307)