Bibliography | Horsch, Martin; Kufleitner, Manfred: The Expressive Power of Simple Logical Fragments over Traces. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Technical Report Computer Science No. 2006/06. 17 pages, english.
|
CR-Schema | F.4.1 (Mathematical Logic)
|
Keywords | First-order logic; Temporal logic; Mazurkiewicz traces; Ehrenfeucht-Fraisse games |
Abstract | 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[<]$ and $FO^2[<]$ over partial orders both can express concurrency of two actions, we show that in general they are incomparable over traces. For $FO^2[<]$ we give a characterization in terms of temporal logic by allowing an operator for parallelism.
|
Full text and other links | PDF (178113 Bytes) PostScript (385955 Bytes)
|
Contact | manfred.kufleitner@informatik.uni-stuttgart.de |
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
|
Entry date | May 23, 2006 |
---|