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)2011
A note on the expressive power of linear ordersArticle

Authors: Thomas Schwentick ; Nicole Schweikardt

    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).

    https://doi.org/10.2168/LMCS-7(4:7)2011
    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
    Licence: arXiv.org - Non-exclusive license to distribute

    Share and export

    Consultation statistics

    This page has been seen 999 times.
    This article's PDF has been downloaded 218 times.