Model-checking trace event structures

Research output: Contribution to journalConference articlepeer-review


Given a regular collection of Mazurkiewicz traces, which can be seen as the behaviours of a finite-state concurrent system, one can associate with it a canonical regular event structure. This event structure is a single (often infinite) structure that captures both the concurrency and conflict information present in the system. We study the problem of model-checking such structures against logics such as first-order logic (FOL), monadic second-order logic (MSOL) and a new logic that lies in between these two called monadic trace logic (MTL). MTL is a fragment of MSOL where the quantification is restricted to sets that are conflict-free. While it is known that model-checking such event structures against MSOL is undecidable, our main results are that FOL and MTL admit effective model-checking procedures. It turns out that FOL captures previously known decidable temporal logics on event structures. MTL is more powerful and can express interesting branching-time properties of event structures, and when restricted to a sequential setting, can express the standard logic CTL* over trees.

Original languageEnglish (US)
Pages (from-to)371-380
Number of pages10
JournalProceedings - Symposium on Logic in Computer Science
StatePublished - 2003
Externally publishedYes
Event18th Annual IEEE Symposium on Logic in Computer Science - Ottawa, Ont., Canada
Duration: Jun 22 2003Jun 25 2003

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Model-checking trace event structures'. Together they form a unique fingerprint.

Cite this