Foundations for the run-time monitoring of reactive systems fundamentals of the MaC language

Mahesh Viswanathan, Moonzoo Kim

Research output: Contribution to journalConference article

Abstract

As the complexity of systems grows, the correctness of systems becomes harder to achieve. This difficulty promotes a run-time monitoring technique as a promising complementary methodology for higher system assurance. To formalize and understand the computational nature of run-time monitoring is a key to utilize this valuable technique. In this paper, we formalize the notion of run-time monitoring of reactive systems in terms of ω-languages and show that the language of Monitoring and Checking (MaC) architecture, called MEDL, is expressive enough for the run-time monitoring. First, we provide a descriptive theory for the class of monitorable languages and show that this class of languages coincides with the class U i of the Arithmetic hierarchy. Second, we introduce a class of automata with storage that can be used to describe the class of monitorable languages using connections to the Arithmetic hierarchy. Finally, we show that MEDL can express the class of monitorable languages via the correspondence between MEDL and the automata with storage.

Original languageEnglish (US)
Pages (from-to)543-556
Number of pages14
JournalLecture Notes in Computer Science
Volume3407
DOIs
StatePublished - Jan 1 2005
EventFirst International Colloquium on Theoretical Aspects of Computing - ICTAC 2004 - Guiyang, China
Duration: Sep 20 2004Sep 24 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Foundations for the run-time monitoring of reactive systems fundamentals of the MaC language'. Together they form a unique fingerprint.

  • Cite this