Complexity of the problem of being equivalent to Horn formulas

DOI10.1007/S10469-022-09665-ZOpenAlexW4225100976WikidataQ113904586 ScholiaQ113904586MaRDI QIDQ2145867FDOQ2145867

N. T. Kogabaev

Publication date: 15 June 2022

Published in: Algebra and Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10469-022-09665-z

Recommendations

• Complexity of the problem of being equivalent to Horn formulas. II
• Existence of simple propositional formulas
• The complexity of equivalence, entailment, and minimization in existential positive logic
• scientific article; zbMATH DE number 4085614
• A hierarchy of propositional Horn formuls

zbMATH Keywords

Horn formula\(m\)-reducibility \(\Sigma_1^0\) set

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Group theory and generalizations (20-XX)

Cites Work

• Title not available (Why is that?)
• On sentences which are true of direct unions of algebras
• Problem of the number of non-self-equivalent constructivizations
• The reduction method. I:
• Title not available (Why is that?)
• Degree spectra and computable dimensions in algebraic structures
• Logical approach to control theory and applications
• A method for the synthesis of deducibility conditions for Horn and some other formulas
• Automation methods for logical derivation and their application in the control of dynamic and intelligent systems
• The reduction method. II
• Reduced products, Horn sentences, and decision problems
• Title not available (Why is that?)
• Logical-optimization approach to pursuit problems for a group of targets
• Title not available (Why is that?)

Cited In (6)

• Title not available (Why is that?)
• On the complexity of equational problems in CNF
• Copy complexity of Horn formulas with respect to unit read-once resolution
• Complexity of the problem of \(\forall \)-representation for sentences
• Complexity of the problem of being equivalent to Horn formulas. II
• On solving the equality problem in theories defined by Horn clauses

This page was built for publication: Complexity of the problem of being equivalent to Horn formulas

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