Counting Defects: Semilinear Reachability and Resource Bounds for Langton's Ant
Complete-field realization and a complete bounded-defect schema cover yield effective all-coordinate semilinear synthesis for Langton's ant. Established Presburger counting and flat-run methods support exact initial-supply and defect spectra, a supply dichotomy, a sharp three-parameter fold-consumer classification, small positive witnesses and unary-budget NP membership. A restricted polynomial-size quantifier-free backend encodes physical read/write parity and shared factor counts; an FP^NP minimum-cost upper bound complements the general semilinear compiler.
Authors
- Ke Hao (ORCID: https://orcid.org/0009-0001-2818-4986)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-26
- DOI
- https://doi.org/10.5281/zenodo.23665498
- Primary Topic
- semigroups and automata theory
- Type
- preprint