Languages represented by Boolean formulas

DOI10.1016/S0020-0190(97)00134-8zbMath1337.68139MaRDI QIDQ290253

Helmut Veith

Publication date: 1 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitypropositional logicdescriptive complexity theorysuccinct problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

Related Items (7)

Sequential Relational Decomposition ⋮ On the Structure of Solution-Graphs for Boolean Formulas ⋮ Model-checking hierarchical structures ⋮ CNF and DNF succinct graph encodings ⋮ Bounded-depth succinct encodings and the structure they imply on graphs ⋮ Succinctness as a source of complexity in logical formalisms ⋮ On the complexity of data disjunctions.

Uses Software

• Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinct circuit representations and leaf language classes are basically the same concept
• Methods for proving completeness via logical reductions
• The complexity of combinatorial problems with succinct input representation
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Succinct representation, leaf languages, and projection reductions
• Succinct representations of graphs
• Second order logic and the weak exponential hierarchies
• Languages that Capture Complexity Classes
• The computational complexity of graph problems with succinct multigraph representation
• A note on succinct representations of graphs

This page was built for publication: Languages represented by Boolean formulas