Metraipolis › archive › dc_329ce997efb8

Formal Verification of Romanov's Triplet Logic: A Verified Filter for Sliding-window 3-CNF with Application to Structured Formulas — arXiv:2608.18445

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.18445
License (as archived)
CC0-1.0
Archived
2026-10-18T13:45:06.470Z
SHA-256 of the archived text
e18f0f0bad6357fd469f2bccf9d871a264a507734fbcf1e481a2e007da9df2d8
Stable URL of this page
https://metraipolis.com/documento/dc_329ce997efb8

How to cite

Formal Verification of Romanov's Triplet Logic: A Verified Filter for Sliding-window 3-CNF with Application to Structured Formulas — arXiv:2608.18445 — arXiv (en), https://arxiv.org/abs/2608.18445 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_329ce997efb8 (Metraipolis archive dc_329ce997efb8, sha256 e18f0f0bad6357fd469f2bccf9d871a264a507734fbcf1e481a2e007da9df2d8)
BibTeX
@misc{dc329ce997efb8,
  title = {Formal Verification of Romanov's Triplet Logic: A Verified Filter for Sliding-window 3-CNF with Application to Structured Formulas — arXiv:2608.18445},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.18445},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_329ce997efb8; sha256 e18f0f0bad6357fd469f2bccf9d871a264a507734fbcf1e481a2e007da9df2d8},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.18445. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We present the first mechanised formalisation of Romanov's Triplet Logic (TLS) in the Rocq proof assistant. TLS is a combinatorial framework originally motivated by Boolean satisfiability, based on triplet structures and a filter that we call Simple Vertex Intersection (SVI). We formalise the core of TLS, including its translation from 3-CNF, the clearing procedure, and the SVI algorithm. For the well-formed sliding-window fragment, we prove explicit polynomial-time bounds for the filter stages and verify the translation and intersection operations. Our main contribution is a precise correctness boundary: for general formulas, SVI non-emptiness is necessary but not sufficient for satisfiability; for aligned structures, we prove a full bi-implication, extended to systems of structures. We also formalise the grouped-window translation and provide a formal counterexample to its completeness. We introduce VFR (Verified Filter for Romanov's triplet logic), an extracted OCaml prototype that implements a verified decision procedure for the sliding-window fragment and a sound filter for general 3-CNF, with a Python runtime and Docker packaging. Benchmarks corroborate the predicted behaviour, and the complete toolchain is available as a curated Zenodo artifact. The Rocq development comprises over 23,000 lines of code, with 424 proved lemmas and no unproved assumptions.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-20 in cs.AI).
Categorie arXiv: Logic in Computer Science (cs.LO) ; Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Programming Languages (cs.PL).
Pagina del lavoro: https://arxiv.org/abs/2608.18445 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T13:41:17.941Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-08-20?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).