Complexity of pattern-based verification for multithreaded programs

DOI10.1145/1926385.1926443zbMath1284.68182OpenAlexW4242620488MaRDI QIDQ5408569

Javier Esparza, Pierre Ganty

Publication date: 10 April 2014

Published in: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1926385.1926443

zbMATH Keywords

safetycontext-free languagesconcurrent programming

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items (7)

A complete refinement procedure for regular separability of context-free languages ⋮ Interprocedural Reachability for Flat Integer Programs ⋮ Parikh's theorem: a simple and direct automaton construction ⋮ Bounded underapproximations ⋮ Unboundedness Problems for Languages of Vector Addition Systems. ⋮ Parametric runtime verification is NP-complete and coNP-complete ⋮ On the Complexity of Bounded Context Switching.

This page was built for publication: Complexity of pattern-based verification for multithreaded programs