Complexity of the problem of being equivalent to Horn formulas

DOI10.1007/S10469-022-09665-ZMaRDI QIDQ2145867zbMATH OpenOpenAlexWikidataFDO

Authors 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

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)

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

Cites work

• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 3467029 (Why is no real title available?)
• scientific article; zbMATH DE number 1285622 (Why is no real title available?)
• scientific article; zbMATH DE number 3353278 (Why is no real title available?)
• 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
• Degree spectra and computable dimensions in algebraic structures
• Logical approach to control theory and applications
• Logical-optimization approach to pursuit problems for a group of targets
• On sentences which are true of direct unions of algebras
• Problem of the number of non-self-equivalent constructivizations
• Reduced products, Horn sentences, and decision problems
• The reduction method. I:
• The reduction method. II

Cited in

(6)

• scientific article; zbMATH DE number 1453038 (Why is no real title available?)
• 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
• On solving the equality problem in theories defined by Horn clauses
• Complexity of the problem of being equivalent to Horn formulas. II

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)