# Algorithmic Witness Search

## Overview

RU is a certificate engine for universality and obstructions in constrained nonnegative propagation. Host structures supply finite inputs. Outputs are audited certificates or finite obstruction witnesses.

## Standardized host instance format

The folder `sources/host_instances/` contains standardized host instances used by the tools.

Schema:

- `sources/host_instance_schema.json`

Examples:

- `sources/host_instances/fibonacci_contraction_instance.json`
- `sources/host_instances/fibonacci_og4_idle_instance.json`
- `sources/host_instances/fibonacci_og1_period2_instance.json`
- `sources/host_instances/ising_og3_instance.json`
- `sources/host_instances/ising_og2_projection_instance.json`
- `sources/host_instances/toric_og3_instance.json`

## Doeblin witness search

Tool:

- `tools/doeblin_search.py`

Input:

- a host instance
- a maximum length Lmax

Output:

- an explicit word (edge ids and template symbols) whose product matrix is strictly positive, if one exists up to Lmax

If none is found up to Lmax, that is a candidate OG3 signal for the chosen search depth.

## Doeblin word avoidability and recurrence bound

Tool:

- `tools/doeblin_avoidance.py`

Output:

- A finite avoidance cycle witness if the word is avoidable (OG4)
- Otherwise UNAVOIDABLE with a finite bound B on the longest avoidance length

When UNAVOIDABLE holds, a recurrence modulus can be read as:

- within any run of length B + L, the length-L word must occur

## Candidate certificate generation

Tool:

- `tools/generate_certificate_from_instance.py`

Outputs are written under:

- `sources/generated/`

Generated objects are not the example audited certificates. They are reproducibility accelerators for exploring host reductions.
