Bounded Structural Model Finding with Symbolic Data Constraints

Artur Boronat · 2026

Read Bounded Structural Model Finding with Symbolic Data Constraints by Artur Boronat (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22093.txt.

Introduction

Boronat presents the Maude Model Finder, a tool for checking software designs. Bounded model finding usually means translating designs into SAT or SMT problems. That route creates a semantic gap and leans on external tools. MMF instead reuses symbolic reachability to build object setups from class declarations and constraints. SMT checks only prune states and settle entailment tests. Boronat gives a calculus that splits object creation from reference assignment. He proves the bounded search terminates and stays sound and complete within its bounds.

Catalog record

CREATORArtur Boronat
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62647
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.22093

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Bounded Structural Model Finding with Symbolic Data Constraints Artur Boronat Abstract Bounded model finding is a key technique for validating software designs, usually obtained by translating high-level specifications into SAT/SMT problems. Although effective, such translations introduce a semantic gap and a dependency on external tools. We present the Maude Model Finder (MMF), a native approach that brings bounded model finding to the Maude rewriting logic framework. MMF provides a schema-parametric engine that repurposes symbolic reachability for structural solving, generating finite object configurations from class declarations and graph and data constraints without bespoke generators. Technically, MMF explores a constrained symbolic rewriting system over runtime states modulo an equational theory; SMT is used only to prune states by constraint satisfiability and to discharge entailment checks for subsumption and folding. We contribute a bounded, obligation-driven calculus that separates object creation from reference assignment and supports symmetry reduction by folding via Maude’s ACU matching. We establish termination, soundness, and completeness of the bounded construction within the declared bounds, and justify folding via a coverage-preserving subsumption test. We focus on the calculus and its properties, illustrating it on running examples supported by a Maude prototype. 1 Introduction Maude is a high-performance specification and analysis environment based on rewriting logic and membership equational logic [ 6 , 7 ] . Its mainstream analysis capabilities target dynamic properties, including reachability search and LTL model checking for finite-state systems [ 3 ] , and symbolic analysis for richer state spaces, including symbolic reachability and rewriting modulo SMT [ 15 , 2 ] . These strengths make Maude an attractive semantic platform, but they do not directly support a complementary task that is central in modelling language engineering: bounded (structural) model finding. Bounded model finding aims to generate finite object graphs within declared bounds that satisfy (i) class and role 1 1 1 A role is a typed reference between classes with a declared multiplicity range. multiplicities, and (ii) structural and data constraints. Such bounded instances are essential to debug metamodels and Object Constraint Language (OCL) constraints, validate design assumptions, and obtain concrete witnesses and counterexamples. Tools such as Alloy and the USE validator provide this capability through SAT/SMT-based instance generation [ 11 , 13 ] . In Maude, while one can execute specifications and explore behaviours, there is no out-of-the-box, schema-parametric mechanism dedicated to bounded structural instance generation for object configurations. In our earlier work on model subtyping with OCL constraints and safe reuse, bounded witnesses were obtained via the USE validator, using its Kodkod-based back end to check satisfiability of OCL constraints [ 4 , 5 ] . This paper internalises bounded witness and counterexample generation within Maude. We present the Maude Model Finder (MMF), a schema-parametric bounded model finding approach for Maude object configurations. MMF formulates bounded model construction as exploration of a constrained symbolic rewriting system over runtime states modulo oriented equations E and algebraic axioms B (such as associativity, commutativity, and identity). SMT is used only as a background solver to prune states by constraint satisfiability and to discharge entailment checks needed for subsumption and folding [ 2 ] . Concretely, we contribute: (1) a bounded, obligation-driven construction calculus that separates object allocation from reference assignment and incrementally accumulates symbolic data constraints; (2) redundancy reduction via folding, combining matching modulo ACU, shape indexing, and SMT-backed entailment; and (3) meta-theoretic guarantees for the bounded calculus, including termination, soundness, and completeness within the declared bounds, and soundness of folding with respect to semantic coverage. We focus on the calculus and its properties, illustrating it on running examples supported by a Maude prototype. The paper is organised as follows. Section 2 presents the MMF specification style through a running example. Sections 3 and 4 introduce the semantic foundations and the symbolic construction calculus. Section 5 describes the reachability engine and its reduction pipeline, and Section 6 summarises the correctness results with full proofs in Appendix 0.A . Section 7 reports a proof-of-concept evaluation, followed by related work and conclusions. 2 Specification with the Maude Model Finder (MMF) We illustrate MMF on a small organizational schema with classes, references, bounds, and symbolic data constraints. An MMF specification describes a bounded family of admissible object graphs in three parts: (i) a schema declaring classes and roles, (ii) a scope fixing finite class and role bounds, and (iii) constraints , split into structural predicates over graphs and data invariants. MMF generates models by constrained symbolic rewriting over runtime states \langle\,C\,\|\,\phi\,\rangle , where C is an object-graph configuration (matched modulo ACU axioms) and \phi is an accumulated Boolean constraint over symbolic attribute variables. Exploration proceeds in two phases: an object allocation phase creates objects to meet class bounds, followed by a reference assignment phase that enumerates admissible role values within role bounds. Branches are pruned as soon as either (i) a monotonic structural error pattern is detected in the partial graph, or (ii) the constraint becomes SMT-unsatisfiable; non-monotonic global constraints are checked only on completed candidates (normal forms). Schema and bounds. The running example has companies, employees, and projects: a Company has a mandatory CEO and a set of projects; an Employee may have a manager; a Project has a non-empty set of members. The schema is written in Maude’s object-oriented style (Listing ); role multiplicities are reflected by carrier sorts (e.g., Oid , Maybe{Oid} , Set{Oid} , NeSet{Oid} ), while the effective branching space is fixed by explicit bounds. Listing declares a finite scope via a constant boundsDecl : classB fixes class cardinalities and roleB constrains, per role, the admissible target class and multiplicity range. Schema for the CEO example. ⬇ 1 omod ORG - PROJ - SCHEMA is 2 protecting MMF . 3 class Company | ceo : Oid , projects : Set { Oid } . 4 class Project | members : NeSet { Oid } . 5 class Employee | manager : Maybe { Oid } . 6 endom Example bounds for the CEO running example. ⬇ 1 eq boundsDecl = 2 classB ( Company , 1, 1) ; 3 classB ( Employee , 2, 2) ; 4 classB ( Project , 0, 2) ; 5 roleB ( Company , ceo , Employee , 1, 1) ; 6 roleB ( Company , projects , Project , 0, 2) ; 7 roleB ( Employee , manager , Employee , 0, 1) ; 8 roleB ( Project , members , Employee , 1, 2) . Structural constraints. MMF supports two structural error predicates. First, specErrorPredGraphPartial is evaluated on partial graphs to enable early pruning. It includes intrinsic well-formedness checks (e.g., unique object identifiers, no dangling edges, and adherence to upper bounds) and can be extended with user-defined monotonic error patterns; once triggered, such errors cannot be repaired by further refinement. Second, specErrorPredGraph is evaluated only on completed candidates (normal forms), to express non-monotonic constraints that need the full graph. In this example, we forbid a manager for the CEO and require the management relation to be acyclic (Listing ). Both predicates return a value of sort TruthPred , whose sole constructor is tt . TruthPred is a dedicated sort distinct from Maude’s Bool : error predicates are structurally matched against tt to detect violations, whereas Bool is reserved for

Read the complete text