@Article{cmc.2026.083232,
AUTHOR = {Zhendong Du, Kenji Hashimoto},
TITLE = {Topological Classification of State-Space Networks Generated by Formal Planning Rules},
JOURNAL = {Computers, Materials \& Continua},
VOLUME = {},
YEAR = {},
NUMBER = {},
PAGES = {{pages}},
URL = {http://www.techscience.com/cmc/online/detail/27809},
ISSN = {1546-2226},
ABSTRACT = {Network science has developed powerful tools for characterizing the topology of emergent networks—systems shaped by evolution, growth, and stochastic attachment—but the topology of constructed networks, graphs generated by the exhaustive application of formal rules, remains theoretically uncharacterized. This paper establishes that the Planning Domain Definition Language (PDDL), the standard formal language for classical planning, is a topological determinist: two binary properties of its operator semantics, reversibility and commutativity, partition the space of generable state-space graphs into exactly three topological archetypes—directed acyclic graph (DAG), Sparse-Cyclic, and Mesh—and this partition is deducible from the language specification without examining any network instance. We prove this as a classification theorem for the fully reversible and fully irreversible extremes of the operator spectrum, show that no fourth archetype exists within this class, and verify its consequences across 289 IPC benchmark problems spanning ten domains, without exception. Archetype membership is confirmed through two operator-derived signatures—the presence of directed cycles and the shape of the out-degree distribution—rather than any single network measurement. The verification reveals a benchmark monoculture, in which semantically distinct domains generate topologically identical structures, and a systematic decoupling of instance scale from topological complexity. Planner experiments confirm the operational stakes of this decoupling: across archetypes of comparable state-space size, optimal-search cost differs by orders of magnitude, with the archetype rather than the scale governing difficulty. Together these results establish PDDL as a natural laboratory for the study of constructed network topology—the first formal language for which the relationship between generative grammar and network topology has been proved complete—and demonstrate that when networks are stipulated rather than evolved, the grammar of the generating language is the fate of the topology.},
DOI = {10.32604/cmc.2026.083232}
}