The Complexity of Data-Free Nfer
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911130282098688 |
|---|---|
| author | Kauffman, Sean Larsen, Kim Guldstrand Zimmermann, Martin |
| author_facet | Kauffman, Sean Larsen, Kim Guldstrand Zimmermann, Martin |
| contents | 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 with a NExpTime lower bound and undecidability for satisfiability of full data-free nfer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_03155 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Complexity of Data-Free Nfer Kauffman, Sean Larsen, Kim Guldstrand Zimmermann, Martin Logic in Computer Science 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 with a NExpTime lower bound and undecidability for satisfiability of full data-free nfer. |
| title | The Complexity of Data-Free Nfer |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2407.03155 |