 |
 |
Thomas Schwentick ; Nicole Schweikardt - A note on the expressive power of linear orders
lmcs:1008 - Logical Methods in Computer Science, December 14, 2011, Volume 7, Issue 4 - https://doi.org/10.2168/LMCS-7(4:7)2011A note on the expressive power of linear ordersArticle
This article shows that there exist two particular linear orders such that first-order logic with these two linear orders has the same expressive power as first-order logic with the Bit-predicate FO(Bit). As a corollary we obtain that there also exists a built-in permutation such that first-order logic with a linear order and this permutation is as expressive as FO(Bit).
Source: arXiv.org:1111.5901
Volume: Volume 7, Issue 4
Published on: December 14, 2011
Imported on: March 25, 2011
Keywords: Computer Science - Logic in Computer Science, F.4.1
Classifications
Mathematics Subject Classification 20201
- 68N30 - Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
- 68Q60 - Specification and verification (program logics, model checking, etc.)
- 68Q85 - Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Consultation statistics
This page has been seen 3017 times.
This article's PDF has been downloaded 440 times.