verify_resolution_logic.py

#!/usr/bin/env python3
"""Check the implication and reversal orientation used by FPRD-T164/T165.

The source theorems are imported facts. This script checks only that the
published conclusions follow from those facts without reversing PEG and SCA.
"""

from __future__ import annotations

import json
from pathlib import Path


def main() -> None:
    # Imported from Kim-Park Theorem 4.19.
    facts = {
        "C_in_LIN": True,
        "C_in_PEG": True,
        "C_in_SCA": False,
        "L_equals_reverse_C": True,
        "L_in_LIN": True,
        "L_in_SCA": True,
        "L_in_PEG": False,
    }

    # Imported from FPRD-T91: every CFL, hence every LIN language, has a
    # deterministic visibly pushdown lift under action forgetting.
    C_has_visible_lift = facts["C_in_LIN"]
    L_has_visible_lift = facts["L_in_LIN"]
    assert C_has_visible_lift and L_has_visible_lift

    # The L lift is the counterexample to universal PEG membership.
    c02_counterexample = L_has_visible_lift and not facts["L_in_PEG"]
    assert c02_counterexample

    # FPRD-T161 identifies finite structural degree with SCA membership.
    delta_C_finite = facts["C_in_SCA"]
    delta_L_finite = facts["L_in_SCA"]
    assert not delta_C_finite
    assert delta_L_finite

    # LMR orientation: X is PEG exactly when reverse(X) is SCA.
    peg_C_from_reverse_sca = delta_L_finite
    peg_L_from_reverse_sca = delta_C_finite
    assert peg_C_from_reverse_sca == facts["C_in_PEG"]
    assert peg_L_from_reverse_sca == facts["L_in_PEG"]

    result = {
        "status": "pass",
        "scope": "logical composition and reversal orientation only",
        "does_not_verify": [
            "FPRD-T91's imported Alur-Madhusudan construction",
            "Kim-Park Theorem 4.19",
            "the Kim-Park Lean artifact",
            "the underlying cell-probe lower bound",
        ],
        "imported_fact_count": len(facts),
        "visible_lifts_checked": 2,
        "peg_sca_orientation_checks": 2,
        "fprd_c02": "resolved negatively",
        "transport_hard_projection": "C",
        "peg_hard_projection": "L=C^R",
        "delta_str_C": "infinity",
        "delta_str_L": "finite",
    }
    output = Path(__file__).with_name("checker-output.json")
    output.write_text(json.dumps(result, indent=2) + "\n", encoding="utf-8")
    print(json.dumps(result, indent=2))


if __name__ == "__main__":
    main()