| • | . Local temporal logic is expressively complete for cograph dependence alphabets. Information and Computation 195(1-2), pages 30-52, 2004. ( PDF | PS | PS.GZ ) |
| Abstract: | Recently, local logics for Mazurkiewicz traces are of increasing
interest. This is mainly due to the fact that the satisfiability problem has
the same complexity as in the word case. If we focus on a purely local
interpretation of formulae at vertices (or events) of a trace, then the
satisfiability problem of linear temporal logics over traces turns out to be
PSPACE-complete. But now the difficult problem is to obtain expressive
completeness results with respect to first order logic. The main result of the paper shows such an expressive completeness result, if the underlying dependence alphabet is a cograph, i.e. if all traces are series parallel posets. Moreover, we show that this is the best we can expect in our setting: If the dependence alphabet is not a cograph, then we cannot express all first order properties. |
| @article{icomp-DG2004, | ||
| author = | {Diekert, Volker and Gastin, Paul}, | |
| DOI = | {10.1016/j.ic.2004.08.001}, | |
| journal = | {Information and Computation}, | |
| month = | nov, | |
| number = | {1-2}, | |
| pages = | {30-52}, | |
| publisher = | {Elsevier Science Publishers}, | |
| title = | {Local temporal logic is expressively complete for cograph dependence alphabets}, | |
| url = | {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG04-icomp.pdf}, | |
| volume = | {195}, | |
| year = | {2004}, | |
| } | ||