Local Logics for Traces

Authors

  • Igor Walukiewicz

DOI:

https://doi.org/10.7146/brics.v7i2.20130

Abstract

A mu-calculus over dependence graph representation of traces
is considered. It is shown that the mu-calculus cannot express all
monadic second order (MSO) properties of dependence graphs.
Several extensions of the mu-calculus are presented and it is proved
that these extensions are equivalent in expressive power to MSO
logic. The satisfiability problem for these extensions is PSPACE
complete.

Downloads

Published

2000-01-01

How to Cite

Walukiewicz, I. (2000). Local Logics for Traces. BRICS Report Series, 7(2). https://doi.org/10.7146/brics.v7i2.20130