The Complexity of Data-Free Nfer

Sean Kauffman; Kim Guldstrand Larsen; Martin Zimmermann

doi:10.1007/978-3-031-74234-7_11

The Complexity of Data-Free Nfer

Sean Kauffman^*, Kim Guldstrand Larsen, Martin Zimmermann

^*Kontaktforfatter

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › peer review

Abstract

Nfer is a Runtime Verification language for the analysis of event traces that applies rules to create hierarchies of time intervals. This work examines the complexity of the evaluation and satisfiability problems for the data-free fragment of nfer. The evaluation problem asks whether a given interval is generated by applying rules to a known input, while the satisfiability problem asks if an input exists that will generate a given interval. By excluding data from the language, we obtain polynomial-time algorithms for the evaluation problem and for satisfiability when only considering inclusive rules. Furthermore, we show decidability for the satisfiability problem for cycle-free specifications and undecidability for satisfiability of full data-free nfer.

Originalsprog	Engelsk
Titel	Runtime Verification - 24th International Conference, RV 2024, Proceedings
Redaktører	Erika Ábrahám, Houssam Abbas
Antal sider	18
Forlag	Springer Science+Business Media
Publikationsdato	2025
Sider	174-191
ISBN (Trykt)	9783031742330
DOI	https://doi.org/10.1007/978-3-031-74234-7_11
Status	Udgivet - 2025
Begivenhed	24th International Conference on Runtime Verification, RV 2024 - Instanbul, Tyrkiet Varighed: 15 okt. 2024 → 17 okt. 2024

Konference

Konference	24th International Conference on Runtime Verification, RV 2024
Land/Område	Tyrkiet
By	Instanbul
Periode	15/10/2024 → 17/10/2024

Navn	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind	15191 LNCS
ISSN	0302-9743

Bibliografisk note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

Adgang til dokumentet

10.1007/978-3-031-74234-7_11

AUB Link

Søg efter materialet i Aalborg Universitetsbiblioteks søgemaskine

Andre filer og links

Link to publication in Scopus

Citationsformater

Kauffman, Sean ; Guldstrand Larsen, Kim ; Zimmermann, Martin. / The Complexity of Data-Free Nfer. Runtime Verification - 24th International Conference, RV 2024, Proceedings. red. / Erika Ábrahám ; Houssam Abbas. Springer Science+Business Media, 2025. s. 174-191 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 15191 LNCS).

@inproceedings{03d06aa42a9a4eeb82fde91b7fe00917,

title = "The Complexity of Data-Free Nfer",

abstract = "Nfer is a Runtime Verification language for the analysis of event traces that applies rules to create hierarchies of time intervals. This work examines the complexity of the evaluation and satisfiability problems for the data-free fragment of nfer. The evaluation problem asks whether a given interval is generated by applying rules to a known input, while the satisfiability problem asks if an input exists that will generate a given interval. By excluding data from the language, we obtain polynomial-time algorithms for the evaluation problem and for satisfiability when only considering inclusive rules. Furthermore, we show decidability for the satisfiability problem for cycle-free specifications and undecidability for satisfiability of full data-free nfer.",

keywords = "Complexity, Interval Logic, Runtime Verification",

author = "Sean Kauffman and {Guldstrand Larsen}, Kim and Martin Zimmermann",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 24th International Conference on Runtime Verification, RV 2024 ; Conference date: 15-10-2024 Through 17-10-2024",

year = "2025",

doi = "10.1007/978-3-031-74234-7_11",

language = "English",

isbn = "9783031742330",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science+Business Media",

pages = "174--191",

editor = "Erika {\'A}brah{\'a}m and Houssam Abbas",

booktitle = "Runtime Verification - 24th International Conference, RV 2024, Proceedings",

address = "United States",

}

Kauffman, S , Guldstrand Larsen, K & Zimmermann, M 2025, The Complexity of Data-Free Nfer. i E Ábrahám & H Abbas (red), Runtime Verification - 24th International Conference, RV 2024, Proceedings. Springer Science+Business Media, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), bind 15191 LNCS, s. 174-191, 24th International Conference on Runtime Verification, RV 2024, Instanbul, Tyrkiet, 15/10/2024. https://doi.org/10.1007/978-3-031-74234-7_11

The Complexity of Data-Free Nfer. / Kauffman, Sean ; Guldstrand Larsen, Kim ; Zimmermann, Martin.
Runtime Verification - 24th International Conference, RV 2024, Proceedings. red. / Erika Ábrahám; Houssam Abbas. Springer Science+Business Media, 2025. s. 174-191 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 15191 LNCS).

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › peer review

TY - GEN

T1 - The Complexity of Data-Free Nfer

AU - Kauffman, Sean

AU - Guldstrand Larsen, Kim

AU - Zimmermann, Martin

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025

Y1 - 2025

N2 - Nfer is a Runtime Verification language for the analysis of event traces that applies rules to create hierarchies of time intervals. This work examines the complexity of the evaluation and satisfiability problems for the data-free fragment of nfer. The evaluation problem asks whether a given interval is generated by applying rules to a known input, while the satisfiability problem asks if an input exists that will generate a given interval. By excluding data from the language, we obtain polynomial-time algorithms for the evaluation problem and for satisfiability when only considering inclusive rules. Furthermore, we show decidability for the satisfiability problem for cycle-free specifications and undecidability for satisfiability of full data-free nfer.

AB - Nfer is a Runtime Verification language for the analysis of event traces that applies rules to create hierarchies of time intervals. This work examines the complexity of the evaluation and satisfiability problems for the data-free fragment of nfer. The evaluation problem asks whether a given interval is generated by applying rules to a known input, while the satisfiability problem asks if an input exists that will generate a given interval. By excluding data from the language, we obtain polynomial-time algorithms for the evaluation problem and for satisfiability when only considering inclusive rules. Furthermore, we show decidability for the satisfiability problem for cycle-free specifications and undecidability for satisfiability of full data-free nfer.

KW - Complexity

KW - Interval Logic

KW - Runtime Verification

UR - http://www.scopus.com/inward/record.url?scp=85207651138&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-74234-7_11

DO - 10.1007/978-3-031-74234-7_11

M3 - Article in proceeding

AN - SCOPUS:85207651138

SN - 9783031742330

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 174

EP - 191

BT - Runtime Verification - 24th International Conference, RV 2024, Proceedings

A2 - Ábrahám, Erika

A2 - Abbas, Houssam

PB - Springer Science+Business Media

T2 - 24th International Conference on Runtime Verification, RV 2024

Y2 - 15 October 2024 through 17 October 2024

ER -

Kauffman S , Guldstrand Larsen K , Zimmermann M. The Complexity of Data-Free Nfer. I Ábrahám E, Abbas H, red., Runtime Verification - 24th International Conference, RV 2024, Proceedings. Springer Science+Business Media. 2025. s. 174-191. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 15191 LNCS). doi: 10.1007/978-3-031-74234-7_11