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
StatePublished - Sep 19 2005
EventFirst International Colloquium on Theoretical Aspects of Computing - ICTAC 2004 - Guiyang, China
Duration: Sep 20 2004Sep 24 2004

Fingerprint

Reactive Systems
Monitoring
Automata
Language
Class
Correctness
Express
Correspondence
Methodology

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Foundations for the run-time monitoring of reactive systems fundamentals of the MaC language. / Viswanathan, Mahesh; Kim, Moonzoo.

In: Lecture Notes in Computer Science, Vol. 3407, 19.09.2005, p. 543-556.

Research output: Contribution to journalConference article

@article{ae01a1c43644431a9ca9de167e6c2e75,
title = "Foundations for the run-time monitoring of reactive systems fundamentals of the MaC language",
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.",
author = "Mahesh Viswanathan and Moonzoo Kim",
year = "2005",
month = "9",
day = "19",
language = "English (US)",
volume = "3407",
pages = "543--556",
journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
issn = "0302-9743",
publisher = "Springer Verlag",

}

TY - JOUR

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

AU - Viswanathan, Mahesh

AU - Kim, Moonzoo

PY - 2005/9/19

Y1 - 2005/9/19

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=24644444646&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=24644444646&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:24644444646

VL - 3407

SP - 543

EP - 556

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SN - 0302-9743

ER -