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 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).
| 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): | 13.03.2012 |
| Date of first Publication: | 13.12.2011 |
| Publishing Institution: | Univ.-Bibliothek Frankfurt am Main |
| Volume: | 7 |
| Issue: | 4:07 |
| Pagenumber: | 13 |
| HeBIS PPN: | 31088960X |
| Institutes: | Informatik |
| Dewey Decimal Classification: | 004 Datenverarbeitung; Informatik |
| Sammlungen: | Universitätspublikationen |
| Licence (German): |  Creative Commons - Namensnennung 3.0 |
