OmegaHyper: Explicit-State HyperLTL Model Checking on an omega-Automaton Diet

HyperLTL extends LTL with quantification over traces. AUtoHyper is the de facto explicit-state model checker for HyperLTL, complete for an arbitrary quantifier prefix: it eliminates quantifiers through products of the formula's omega-automaton with the systems, complementing on quantifier alternations. However, it suffers from state explosion, as it fully materializes input systems and intermediate automata. We present OmegaHyper, an overhaul of AutoHyper that keeps its algorithm but decomposes and reduces the size of the processed automata, and integrates the Kofola omega-automaton complementation tool. We compare OmegaHyper with existing explicit-state and symbolic HyperLTL model checkers, on 120 benchmarks from their published suites. OmegaHyper improves the performance of explicit-state HyperLTL model checking by up to orders of magnitude; bounded symbolic tools still reach further on violated instances with short counterexamples, as expected.

Authors

Publication Details

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

OmegaHyper: Explicit-State HyperLTL Model Checking on an omega-Automaton Diet

Hugo Pacheco
arXiv (Cornell University)
Formal Methods in Verification
preprint

OmegaHyper: Explicit-State HyperLTL Model Checking on an omega-Automaton Diet

Hugo Pacheco
preprint en

Abstract

HyperLTL extends LTL with quantification over traces. AUtoHyper is the de facto explicit-state model checker for HyperLTL, complete for an arbitrary quantifier prefix: it eliminates quantifiers through products of the formula's omega-automaton with the systems, complementing on quantifier alternations. However, it suffers from state explosion, as it fully materializes input systems and intermediate automata. We present OmegaHyper, an overhaul of AutoHyper that keeps its algorithm but decomposes and reduces the size of the processed automata, and integrates the Kofola omega-automaton complementation tool. We compare OmegaHyper with existing explicit-state and symbolic HyperLTL model checkers, on 120 benchmarks from their published suites. OmegaHyper improves the performance of explicit-state HyperLTL model checking by up to orders of magnitude; bounded symbolic tools still reach further on violated instances with short counterexamples, as expected.

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