A Graph-Based Model for Automatic Test Case Generation from Textual Requirements with Hierarchical Coverage

The automation of software test case generation from natural language requirements remains a critical challenge in software engineering.  While large language models (LLMs) demonstrate impressive generation capabilities, they suffer from high discrepancy rates (up to 57% for direct generation), hallucinated test steps, and lack formal verification mechanisms for safety-critical constraints.  This paper presents a novel algorithmic framework that addresses these limitations through five principal contributions.  First, we introduce the Neuro-Symbolic Requirements Graph (NSRG) model $GNS = (V, E, w, \Gamma, \Psi)$, which integrates transformer-derived semantic dependencies with Linear Temporal Logic (LTL) constraints ($\Psi$) and control flow subgraphs ($\Gamma$).  Second, we derive the Extended Minimum Coverage Theorem establishing theoretical lower bounds for hierarchical coverage.  Third, we propose the Hybrid Semantic-Temporal Coverage (HSTC) metric utilizing Determinantal Point Processes (DPP) to systematically optimize test suite diversity.  Fourth, we develop the MCTS-Guided Neuro-Symbolic Traversal (MCTS-NST) algorithm based on Monte Carlo Tree Search.  Fifth, we implement Dynamic HNSW Indexing reducing graph construction complexity from $\mathcal{O}(|V|^2)$ to $\mathcal{O}(|V|\log |V|)$.  Experimental evaluation on four benchmark datasets (3,581 requirements) demonstrates: 96.8% precision, 98.4% recall, 99.1% LTL satisfaction rate for negative requirements, and 0.94% discrepancy rate.  The framework achieves practitioner acceptance scores of 4.85/5.