Parametric runtime verification is NP-complete and coNP-complete

DOI10.1016/j.ipl.2017.02.006zbMath1405.68181OpenAlexW2592713318MaRDI QIDQ522961

Zhe Chen

Publication date: 20 April 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.02.006

zbMATH Keywords

computational complexityformal languagesmembership problemsruntime monitoringparametric words

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• A brief account of runtime verification
• The complexity of verification
• Semantics and Algorithms for Parametric Monitoring
• Keeping a Crowd Safe: On the Complexity of Parameterized Verification (Invited Talk).
• Complexity of pattern-based verification for multithreaded programs

This page was built for publication: Parametric runtime verification is NP-complete and coNP-complete