Efficient Monitoring of ω-languages

d'Amorim, Marcelo; Rosu, Grigore

Permalink

https://hdl.handle.net/2142/10975 Copy

Description

Title

Efficient Monitoring of ω-languages

Author(s)

• d'Amorim, Marcelo
• Rosu, Grigore

Issue Date

2005-03

Keyword(s)

Formal systems

Abstract

We present a technique for generating efficient monitors for Omega-regular-languages. We show how Buchi automata can be reduced in size and transformed into special, statistically optimal nondeterministic finite state machines, called binary transition tree finite state machines (BTT-FSMs), which recognize precisely the minimal bad prefixes of the original omega-regular-language. The presented technique is implemented as part of a larger monitoring framework and is available for download.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/10975

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections