Selective Chaining of Parameterised Boolean Equation Systems

Parameterised Boolean Equations Systems (PBESs) are used to verify properties of formal industrial models. We introduce a technique called selective chaining to simplify these PBESs by unfolding specific predicate variable instances when the unfolding results in a PBES that is likely to be simpler. For determining the latter we propose a set of heuristics. We show the formal correctness of the chaining operator and provide theoretical upper bounds using relevancy graphs on the size of the verification problem after chaining. Lastly, we study the effectiveness of our heuristics, showing that selective chaining can reduce memory usage and yield significant speed-ups solving PBESs that encode model checking problems for complex industrial systems.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.16815
Primary Topic
Formal Methods in Verification
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Selective Chaining of Parameterised Boolean Equation Systems

Tim A. C. Willemse, Jore Booy
arXiv (Cornell University)
Formal Methods in Verification
preprint

Selective Chaining of Parameterised Boolean Equation Systems

Tim A. C. Willemse, Jore Booy
preprint en

Abstract

Parameterised Boolean Equations Systems (PBESs) are used to verify properties of formal industrial models. We introduce a technique called selective chaining to simplify these PBESs by unfolding specific predicate variable instances when the unfolding results in a PBES that is likely to be simpler. For determining the latter we propose a set of heuristics. We show the formal correctness of the chaining operator and provide theoretical upper bounds using relevancy graphs on the size of the verification problem after chaining. Lastly, we study the effectiveness of our heuristics, showing that selective chaining can reduce memory usage and yield significant speed-ups solving PBESs that encode model checking problems for complex industrial systems.

arXiv (Cornell University)
Formal Methods in Verification
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