On the complexity of determinizing monitors

DOI10.1007/978-3-319-60134-2_1zbMath1489.68149OpenAlexW2617976510MaRDI QIDQ2399244

Sævar Örn Kjartansson, Adrian Francalanza, Anna Ingólfsdóttir, Antonis Achilleos, Luca Aceto

Publication date: 22 August 2017

Full work available at URL: https://www.um.edu.mt/library/oar//handle/123456789/23173

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

A process calculus approach to detection and mitigation of PLC malware ⋮ Computer says no: verdict explainability for runtime monitors using a local proof system ⋮ A survey of challenges for runtime verification from advanced application domains (beyond software) ⋮ Determinizing monitors for HML with recursion ⋮ A theory of monitors ⋮ Consistently-detecting monitors ⋮ Monitoring for Silent Actions

Cites Work

• Unnamed Item
• Unnamed Item
• The tractability frontier for NFA minimization
• Results on the propositional \(\mu\)-calculus
• Runtime verification with minimal intrusion through parallelism
• Proof systems for satisfiability in Hennessy-Milner logic with recursion
• Finite automata and unary languages
• A calculus of communicating systems
• Reasoning about infinite computations
• A brief account of runtime verification
• Minimizing nfa's and regular expressions
• A Theory of Monitors
• Minimal NFA Problems are Hard
• Quantified Event Automata: Towards Expressive and Efficient Runtime Monitors
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP

This page was built for publication: On the complexity of determinizing monitors