Parametric runtime verification is NP-complete and coNP-complete
type: Item
instance of: scholarly article
title: Parametric runtime verification is NP-complete and coNP-complete
zbMATH Open document ID: 1405.68181
author: Zhe Chen
published in: Information Processing Letters
publication date: 2017-04-20T00:00:00Z
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6706362
zbMATH Keywords: runtime monitoring
zbMATH Keywords: computational complexity
zbMATH Keywords: formal languages
zbMATH Keywords: parametric words
zbMATH Keywords: membership problems
MaRDI profile type: Publication
full work available at URL: j.ipl.2017.02.006
OpenAlex ID: W2592713318
cites work: A brief account of runtime verification
cites work: Semantics and algorithms for parametric monitoring
cites work: Q5592246
cites work: Descriptional and computational complexity of finite automata -- a survey
cites work: Q3221403
cites work: The complexity of verification
cites work: Complexity of pattern-based verification for multithreaded programs
cites work: Keeping a Crowd Safe: On the Complexity of Parameterized Verification (Invited Talk).
DOI: 10.1016/J.IPL.2017.02.006
description: scientific article; zbMATH DE number 6706362