Languages represented by Boolean formulas

DOI10.1016/S0020-0190(97)00134-8MaRDI QIDQ290253zbMATHFDO

Authors Helmut Veith

Publication date 1 June 2016

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

zbMATH Keywords

computational complexitydescriptive complexity theorypropositional logicsuccinct problems

Mathematics Subject Classification ID

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

Recommendations

• The complexity of combinatorial problems with succinct input representation
• Mathematical Foundations of Computer Science 2003
• scientific article; zbMATH DE number 1705165
• scientific article; zbMATH DE number 496040
• scientific article; zbMATH DE number 3978379

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 4213461 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 219271 (Why is no real title available?)
• A note on succinct representations of graphs
• Languages that Capture Complexity Classes
• Methods for proving completeness via logical reductions
• Second order logic and the weak exponential hierarchies
• Succinct circuit representations and leaf language classes are basically the same concept
• Succinct representation, leaf languages, and projection reductions
• Succinct representations of graphs
• The complexity of combinatorial problems with succinct input representation
• The computational complexity of graph problems with succinct multigraph representation
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems

Cited in

(10)

• The Boolean formula value problem as formal language
• Succinctness as a source of complexity in logical formalisms
• On the structure of solution-graphs for Boolean formulas
• Model-checking hierarchical structures
• Formulas, regular languages and Boolean circuits
• Boolean grammars
• Bounded-depth succinct encodings and the structure they imply on graphs
• On the complexity of data disjunctions.
• CNF and DNF succinct graph encodings
• Normalization Issues in Mathematical Representations

Describes a project that uses

Uses Software

• Datalog

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

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