State-based Test AutomAtIon via Computational Equivalence

State-based testing has long promised systematic coverage of software behavior, yet its practical realization has remained inefficient, ad hoc, and poorly aligned with modern development practices. This paper presents a breakthrough in test design methodology by redefining the notion of "state" around computation equivalence rather than system internals. We introduce the concept of test states-artificial constructs that isolate distinct computations-and show how these can be generated directly from natural language requirements using a novel graph-based algorithm guided by large language models. This approach generalizes equivalence partitioning and enables the application of a linear 0-switch test selection criterion, ensuring comprehensive coverage of computational behaviors with minimal test cases. Our method integrates seamlessly with state-based testing, yielding a fully automated, scalable, and interpretable test design process. Experimental results across three tricky applications demonstrate that this technique outperforms both requirements-only and traditional state-transition testing, achieving near-complete defect detection with dramatically reduced effort. By using AI to interpret requirements and drive the algorithm that generates test states, this work overcomes longstanding limitations of state-based testing and lays a new foundation for detecting computation errors.