Recognition of \(q\)-Horn formulae in linear time
type: Item
instance of: scholarly article
title: Recognition of \(q\)-Horn formulae in linear time
zbMATH Open document ID: 0821.68109
DOI: 10.1016/0166-218X(94)90033-7
author: Endre Boros
author: Peter L. Hammer
author: Xiaorong Sun
published in: Discrete Applied Mathematics
publication date: 1995-09-10T00:00:00Z
Mathematics Subject Classification ID: 68T27
zbMATH DE Number: 683676
zbMATH Keywords: \(q\)-Horn Boolean expressions
zbMATH Keywords: disjunctive normal form
Wikidata QID: Q59560996
MaRDI profile type: Publication
cites work: Recognizing disguised NR(1) instances of the satisfiability problem
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Polynomial-time inference of all valid implications for Horn and related formulae
cites work: A Complexity Index for Satisfiability Problems
cites work: On renamable Horn and generalized Horn functions
cites work: Extended Horn sets in propositional logic
cites work: The complexity of theorem-proving procedures
cites work: Linear-time algorithms for testing the satisfiability of propositional horn formulae
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: Algorithms for testing the satisfiability of propositional formulae
cites work: Horn logic, search and satisfiability. A collection of papers in memory of Robert G. Jeroslow
cites work: Branch-and-cut solution of inference problems in propositional logic
cites work: Complete problems for deterministic polynomial time
cites work: Renaming a Set of Clauses as a Horn Set
cites work: Depth-First Search and Linear Graph Algorithms
cites work: A simplified NP-complete satisfiability problem
cites work: Question-asking strategies for Horn clause systems
full work available at URL: 0166-218x(94)90033-7
OpenAlex ID: W1974563688
description: scientific article; zbMATH DE number 683676