A note on the expressive power of linear orders

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 
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).
…show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Nicole Schweikardt, Thomas Schwentick
URN:urn:nbn:de:hebis:30:3-240649
DOI:http://dx.doi.org/10.2168/LMCS-7(4:7)2011
ISSN:1860-5974
Parent Title (English):Logical methods in computer science : LMCS
Publisher:Department of Theoretical Computer Science, Technical University of Braunschweig
Place of publication:Braunschweig
Document Type:Article
Language:English
Date of Publication (online):2012/03/13
Date of first Publication:2011/12/13
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2012/03/13
Volume:7
Issue:4:07
Pagenumber:13
HeBIS PPN:31088960X
Institutes:Informatik
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
Sammlungen:Universitätspublikationen
Licence (German):License LogoCreative Commons - Namensnennung 3.0

$Rev: 11761 $