Metraipolis › archive › dc_e6d4a4477ea6

Model Checking HyperRecHML is Decidable — arXiv:2610.21379

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.21379
License (as archived)
CC0-1.0
Archived
2026-10-16T10:40:27.836Z
SHA-256 of the archived text
f1d8af1595f86e12f9d1ab98af990636802c3e87a25cea1840c95be150bbaf49
Stable URL of this page
https://metraipolis.com/documento/dc_e6d4a4477ea6

How to cite

Model Checking HyperRecHML is Decidable — arXiv:2610.21379 — arXiv (en), https://arxiv.org/abs/2610.21379 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e6d4a4477ea6 (Metraipolis archive dc_e6d4a4477ea6, sha256 f1d8af1595f86e12f9d1ab98af990636802c3e87a25cea1840c95be150bbaf49)
BibTeX
@misc{dce6d4a4477ea6,
  title = {Model Checking HyperRecHML is Decidable — arXiv:2610.21379},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.21379},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e6d4a4477ea6; sha256 f1d8af1595f86e12f9d1ab98af990636802c3e87a25cea1840c95be150bbaf49},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.21379. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Temporal hyperlogics combine explicit quantification over traces with temporal requirements evaluated over the quantified traces. HyperRecHML is a temporal hyperlogic which allows for arbitrary mixing of trace quantification and the use of fixed points for expressing temporal requirements, which makes it very expressive in comparison to other first-order hyperlogics. HyperRecHML has already been successfully applied in runtime verification, but the decidability of its model checking problem remains open. We answer this question positively by providing two main contributions. Firstly, a normalization procedure that allows to reduce arbitrary HyperRecHML formulas to a normal form with restricted nesting of trace quantification and fixed points. Secondly, we provide an automata-based model checking algorithm for formulas of this normal form. The complexity of our algorithm is comparable to similar ones for other hyperlogics, despite the extra expressive power.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.LO, nuovi lavori del giorno).
Categorie arXiv: Logic in Computer Science (cs.LO) ; Formal Languages and Automata Theory (cs.FL).
Pagina del lavoro: https://arxiv.org/abs/2610.21379 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:53:32.665Z dalla pagina https://arxiv.org/list/cs.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).