The expressive power of simple logical fragments over traces

Martin Horsch & Manfred Kufleitner
We compare the expressive power of some first-order fragments and of two simple temporal logics over Mazurkiewicz traces. Over words, most of these fragments have the same expressive power whereas over traces we show that the ability of formulating concurrency increases the expressive power. We also show that over so-called dependence structures it is impossible to formulate concurrency with the first-order fragments under consideration. Although the first-order fragments $\Delta_n[
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.