The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary

DOI10.1002/malq.19670130104zbMath0162.31601OpenAlexW2077925882WikidataQ55966490 ScholiaQ55966490MaRDI QIDQ5545955

Melven R. Krom

Publication date: 1967

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19670130104

zbMATH Keywords

recursion theory, constructive mathematics

Related Items

The computational complexity of propositional STRIPS planning ⋮ Tractability-preserving transformations of global cost functions ⋮ The decision problem for formulas in prenex conjunctive normal form with binary disjunctions ⋮ Detecting induced minors in AT-free graphs ⋮ The clique problem with multiple-choice constraints under a cycle-free dependency graph ⋮ The complete set of minimal simple graphs that support unsatisfiable 2-CNFs ⋮ Fairness in temporal slot assignment ⋮ Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring ⋮ Exact enumeration of satisfiable 2-SAT formulae ⋮ The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size ⋮ A multistage view on 2-satisfiability ⋮ Digraph width measures in parameterized algorithmics ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ Prefix classes of Krom formulas ⋮ Copy complexity of Horn formulas with respect to unit read-once resolution ⋮ Capturing complexity classes by fragments of second-order logic ⋮ Argumentation frameworks as constraint satisfaction problems ⋮ Linear-Time Algorithm for Quantum 2SAT ⋮ The complexity of tropical graph homomorphisms ⋮ Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen ⋮ Complete rings of sets and sentential logic ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ How we designed winning algorithms for abstract argumentation and which insight we attained ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ Level-planarity: transitivity vs. even crossings ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ Conservative reduction classes of Krom formulas