13 SMT-LIB Fragments

The SMT-LIB standard defines a set of logics (fragments) that describe which theories and quantifier forms are used. JuGeo's FragmentClassifier inspects each verification condition (VC) and assigns it to one of the following 13 fragments. The fragment determines which solver tactics and strategies are applicable.

Fragment Full Name Python Domain Default Solver
QF_LIA Quantifier-free linear integer arithmetic Integer bounds, loop counters Z3
QF_LRA Quantifier-free linear real arithmetic Float refinements, rate constraints Z3
QF_BV Quantifier-free bitvectors Bitwise operations, overflow checks Z3
QF_AUFLIA QF arrays + uninterpreted functions + LIA List/dict read-write reasoning Z3
QF_S Quantifier-free strings String refinements, regex constraints Z3 (str theory)
QF_NIA Quantifier-free nonlinear integer arithmetic Polynomial constraints, hash functions Z3 (nlsat)
QF_NRA Quantifier-free nonlinear real arithmetic Numeric stability, ML weight bounds CVC5
UFLIA Uninterpreted functions + LIA (with quantifiers) Abstracted function calls Z3
AUFBVLIA Arrays + UF + BV + LIA Memory-mapped numeric data Z3
QF_DT Quantifier-free datatypes Algebraic types, enums, tagged unions Z3
QF_UFLIA QF UF + LIA Abstract function models with bounds Z3
ALL All theories (full SMT-LIB) Complex multi-theory judgments Z3 (portfolio)
UNKNOWN Fragment not classifiable Opaque functions, H∞ candidates None — escalated to FORMAL evidence
⚠️

QF_NRA and QF_NIA. Nonlinear arithmetic is decidable in principle (Tarski's theorem for reals, Presburger for integers), but practically hard. JuGeo routes QF_NRA to CVC5 by default and sets a tighter time budget. If the solver times out, the judgment is classified as UNKNOWN trust and the fragment is logged for manual inspection.

5 Routing Strategies

The routing layer can apply one of five strategies to decide how to handle each VC. Strategies differ in how aggressively they attempt multiple solvers and how they balance latency against completeness.

FRAGMENT_FIRST
Fragment-First

Route to the solver known to perform best on the classified fragment. The default. Fast and reliable for well-typed formulas.

PORTFOLIO
Portfolio

Run Z3 and CVC5 in parallel on a thread pool; return the first conclusive result. Higher resource use; best completeness.

INCREMENTAL
Incremental

Reuse solver state from previous VCs via push/pop. Reduces overhead for large modules with many related VCs.

FALLBACK_CHAIN
Fallback Chain

Try Z3; if UNKNOWN, try CVC5; if still UNKNOWN, escalate to FORMAL evidence channel. Maximises coverage at higher latency.

BUDGET_AWARE
Budget-Aware

Respect a per-VC time and cost budget. Skips expensive fragments if budget is exhausted; reports BUDGET_EXCEEDED rather than UNKNOWN.

Z3Session, Z3Formula, and FragmentClassifier

The three core classes in jugeo.solver are Z3Session, Z3Formula, and FragmentClassifier. They form a thin, idiomatic Python wrapper around the z3-solver library that integrates with JuGeo's trust and evidence machinery.

python
from jugeo.solver import Z3Session, Z3Formula, FragmentClassifier
import z3

# FragmentClassifier: inspect a formula before solving
formula = z3.And(z3.Int("x") > 0, z3.Int("x") < 100)
clf = FragmentClassifier()
fragment = clf.classify(formula)
print(fragment)          # SMTFragment.QF_LIA
print(fragment.solver)   # "z3"
print(fragment.tactics)  # ["linarith", "arith"]

# Z3Session: managed solver session with JuGeo integration
session = Z3Session(
    timeout_ms=5000,
    strategy="FRAGMENT_FIRST",
    incremental=True,
)
session.push()
session.assert_formula(formula)
result = session.check()
print(result.status)     # "UNSAT" | "SAT" | "UNKNOWN"
print(result.trust)      # TrustLevel.SOLVER if UNSAT
print(result.model)      # z3.ModelRef if SAT (counterexample)
session.pop()

# Z3Formula: wraps a z3 expression with metadata
zf = Z3Formula(
    expr=formula,
    fragment=fragment,
    source_judgment=judgment,
    label="price_bound_check",
)
print(zf.fragment)       # SMTFragment.QF_LIA
print(zf.label)          # "price_bound_check"

Jurisdiction Management

In a multi-solver setup, each solver operates within a jurisdiction: the set of fragments and formula shapes it is authorised to handle. JuGeo tracks jurisdictions to prevent a weaker solver from returning inconclusive results on formulas that a stronger solver could decide.

Jurisdiction boundaries are enforced by the SolverJurisdiction class. When a formula is submitted to a session, the session checks that the formula's fragment falls within the session's jurisdiction. If not, the formula is escalated to the appropriate solver automatically.

python
from jugeo.solver import SolverJurisdiction, SolverRouter, SMTFragment

# Define custom jurisdiction
jur = SolverJurisdiction(
    solver_name="z3",
    fragments=[SMTFragment.QF_LIA, SMTFragment.QF_LRA, SMTFragment.QF_BV],
    timeout_ms=10_000,
    fallback="cvc5",
)

# Router: dispatches VCs to sessions based on jurisdiction
router = SolverRouter(
    strategy="FALLBACK_CHAIN",
    jurisdictions=[jur],
)

# Route a single formula
result = router.route_and_solve(formula, label="vc_001")
print(result.solver_used)    # "z3" or "cvc5"
print(result.fragment)       # the detected fragment
print(result.escalated)      # True if escalated to fallback solver
print(result.duration_ms)    # actual solving time

# Batch routing (parallel where strategy allows)
vcs = [Z3Formula(expr=f, label=f"vc_{i}") for i, f in enumerate(formulas)]
batch_result = router.route_batch(vcs)
print(f"Verified: {batch_result.verified_count}")
print(f"Unknown : {batch_result.unknown_count}")
print(f"SAT     : {batch_result.sat_count}")  # counterexamples found

Python Examples

End-to-end: from judgment to solver result:

python
import jugeo
from jugeo.solver import SolverRouter, RoutingStrategy

# Build site and run the encoding pipeline
site = jugeo.build_site("mymod")
report = jugeo.analyze_module("mymod", property="pure")

# Access the solver results for each judgment
for j in report.judgments:
    vc = j.verification_condition
    if vc is None:
        print(f"  {j.coordinate}: no VC (trivial or FORMAL)")
        continue
    fragment = vc.fragment
    result = vc.solver_result
    print(f"  {j.coordinate}  [{fragment.name}] -> {result.status}")
    if result.status == "SAT":
        print(f"    Counterexample: {result.model_as_python_values()}")

# Configure and run the router directly
router = SolverRouter(strategy=RoutingStrategy.PORTFOLIO)
jugeo.set_solver_router(router)

# Re-run with portfolio strategy
report2 = jugeo.analyze_module("mymod", property="no_exceptions")
print(f"Closed: {report2.closed_count} / {report2.total_count}")

Inspecting fragment classification details:

python
from jugeo.solver import FragmentClassifier, SMTFragment
import z3

clf = FragmentClassifier(verbose=True)

# A mixed-theory formula: integers + uninterpreted function
x = z3.Int("x")
f = z3.Function("f", z3.IntSort(), z3.IntSort())
formula = z3.And(x > 0, f(x) == x + 1, f(f(x)) < 100)

fragment = clf.classify(formula)
print(fragment)                   # SMTFragment.UFLIA
print(clf.classification_trace)  # step-by-step reasoning

# Check whether a formula is in a decidable fragment
print(clf.is_decidable(formula))  # True for UFLIA
print(clf.complexity_estimate(formula))  # "pspace" | "np" | "polynomial"

# Get the recommended tactics for a fragment
tactics = clf.recommended_tactics(SMTFragment.QF_AUFLIA)
print(tactics)  # ["arrays", "arith", "qfauflia"]