An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF

DOI10.3233/SAT-220006MaRDI QIDQ6113549zbMATH OpenOpenAlexFDO

Authors E. Ya. Dantsin, Alexander Wolpert

Publication date 11 July 2023

Published in Journal on Satisfiability, Boolean Modeling and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/sat-220006

zbMATH Keywords

distance on CNF formulasisomorphism invariantsper-instance algorithm selection

Mathematics Subject Classification ID

Classical propositional logic (03B05) Computational aspects of satisfiability (68R07) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Isomorphic formulae in classical propositional logic
• Theory and Applications of Satisfiability Testing
• STACS 2004
• Distances and uncertainty measures on the propositional formulas of an n-valued logic
• scientific article; zbMATH DE number 1948177
• Theory and Applications of Satisfiability Testing
• Mathematical Foundations of Computer Science 2005
• Axiomatizing distance logics
• On properties of functions representable in the form of a 2-CNF
• Minimal distance of propositional models

Cites work

• A course in metric geometry
• A faster algorithm for propositional model counting parameterized by incidence treewidth
• A perspective on certain polynomial-time solvable classes of satisfiability
• Approximation algorithms for treewidth
• Graph isomorphism in quasipolynomial time (extended abstract)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• Parameterized algorithms
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• Practical graph isomorphism. II.

Cited in

(1)

• Some computational aspects of DISTANCE SAT

This page was built for publication: An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF

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