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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Counting Defects: Semilinear Reachability and Resource Bounds for Langton's Ant

Ke Hao
Zenodo (CERN European Organization for Nuclear Research)
semigroups and automata theory
preprint

Counting Defects: Semilinear Reachability and Resource Bounds for Langton's Ant

Ke Hao
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
semigroups and automata theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Counting Defects: Semilinear Reachability and Resource Bounds for Langton's Ant — Ke Hao · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS