Complexity of the problem of being equivalent to Horn formulas. II

DOI10.1007/S10469-023-09700-7MaRDI QIDQ6160501zbMATH OpenOpenAlexFDO

Authors N. T. Kogabaev

Publication date 10 May 2023

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

Full work available at URL https://doi.org/10.1007/s10469-023-09700-7

zbMATH Keywords

\(m\)-reducibility\({\sum }_1^0\)-setHorn formula

Mathematics Subject Classification ID

Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Complexity of the problem of being equivalent to Horn formulas
• scientific article; zbMATH DE number 4085614
• Existence of simple propositional formulas
• The complexity of equivalence, entailment, and minimization in existential positive logic
• On the complexity of the maximum satisfiability problem for Horn formulas

Cites work

• 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
• Complexity of the problem of being equivalent to Horn formulas
• scientific article; zbMATH DE number 1285622 (Why is no real title available?)
• scientific article; zbMATH DE number 3316934 (Why is no real title available?)
• scientific article; zbMATH DE number 3353278 (Why is no real title available?)
• 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
• Reduced products, Horn sentences, and decision problems
• The first order properties of products of algebraic systems
• The reduction method. I:
• The reduction method. II
• Undecidability of some simple formalized theories

Cited in

(5)

• On solving the equality problem in theories defined by Horn clauses
• Complexity of the problem of being equivalent to Horn formulas
• Copy complexity of Horn formulas with respect to unit read-once resolution
• scientific article; zbMATH DE number 1453038 (Why is no real title available?)
• Complexity of the problem of -representation for sentences

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

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