Languages represented by Boolean formulas
From MaRDI portal
Publication:290253
DOI10.1016/S0020-0190(97)00134-8zbMATH Open1337.68139MaRDI QIDQ290253FDOQ290253
Publication date: 1 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Languages that Capture Complexity Classes
- 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
- Title not available (Why is that?)
- Second order logic and the weak exponential hierarchies
- The computational complexity of graph problems with succinct multigraph representation
- Title not available (Why is that?)
- A note on succinct representations of graphs
- Succinct circuit representations and leaf language classes are basically the same concept
Cited In (9)
- On the complexity of data disjunctions.
- Bounded-depth succinct encodings and the structure they imply on graphs
- Model-checking hierarchical structures
- Succinctness as a source of complexity in logical formalisms
- Boolean grammars
- Formulas, regular languages and Boolean circuits
- Sequential Relational Decomposition
- CNF and DNF succinct graph encodings
- On the Structure of Solution-Graphs for Boolean Formulas
Uses Software
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)
