{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:36:41Z","timestamp":1753889801930,"version":"3.41.2"},"reference-count":10,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2011,12,14]],"date-time":"2011-12-14T00:00:00Z","timestamp":1323820800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>This article shows that there exist two particular linear orders such that\nfirst-order logic with these two linear orders has the same expressive power as\nfirst-order logic with the Bit-predicate FO(Bit). As a corollary we obtain that\nthere also exists a built-in permutation such that first-order logic with a\nlinear order and this permutation is as expressive as FO(Bit).<\/jats:p>","DOI":"10.2168\/lmcs-7(4:7)2011","type":"journal-article","created":{"date-parts":[[2012,6,20]],"date-time":"2012-06-20T09:05:51Z","timestamp":1340183151000},"source":"Crossref","is-referenced-by-count":0,"title":["A note on the expressive power of linear orders"],"prefix":"10.46298","volume":"Volume 7, Issue 4","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2011,12,14]]},"reference":[{"issue":"2","key":"10.2168\/LMCS-7(4:7)2011_BILST-JCSS","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.jcss.2004.07.004","volume":"70","author":"David A. Mix Barrington, Neil Immerman,","year":"2005","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"10.2168\/LMCS-7(4:7)2011_BIS90","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"David A. Mix Barrington, Neil Immerman,","year":"1990","journal-title":"J. Comput. Syst. Sci."},{"key":"10.2168\/LMCS-7(4:7)2011_Bennett-Phd","unstructured":"J. H. Bennett.On spectra. PhD thesis, Princeton University, Princeton, NJ, 1962."},{"key":"10.2168\/LMCS-7(4:7)2011_DDLW98","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1002\/malq.19980440306","volume":"44","author":"Anuj Dawar, Kees Doets, Steven Lindell,","year":"1998","journal-title":"Math. Log. Q."},{"issue":"4","key":"10.2168\/LMCS-7(4:7)2011_TroyLee03","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1002\/malq.200310041","volume":"49","author":"Troy Lee","year":"2003","journal-title":"Math. Log. Q."},{"key":"10.2168\/LMCS-7(4:7)2011_Libkin-FMT","doi-asserted-by":"crossref","unstructured":"Leonid Libkin.Elements of Finite Model Theory. Springer, 2004.","DOI":"10.1007\/978-3-662-07003-1"},{"issue":"2","key":"10.2168\/LMCS-7(4:7)2011_Lynch82-squares","first-page":"127","volume":"15","author":"James F. Lynch","year":"1982","journal-title":"Math. Syst. Theory"},{"key":"10.2168\/LMCS-7(4:7)2011_Schweikardt_Diss","unstructured":"Nicole Schweikardt.On the Expressive Power of First-Order Logic with Built-In Predicates. PhD thesis, Institute for Computer Science, Johannes Gutenberg-Universit\u00e4t Mainz, 2001. Published at Logos Verlag Berlin, 2002."},{"issue":"3","key":"10.2168\/LMCS-7(4:7)2011_Schweikardt_ACMToCL","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/1071596.1071602","volume":"6","author":"Nicole Schweikardt","year":"2005","journal-title":"ACM Trans. Comput. Log."},{"key":"10.2168\/LMCS-7(4:7)2011_Schwentick_CSL97","doi-asserted-by":"crossref","unstructured":"Thomas Schwentick. Padding and the expressive power of existential second-order logics. InProc. of 11th International Workshop on Computer Science Logic (CSL'97), Selected Papers, volume 1414 ofLecture Notes in Computer Science, pages 461-477. Springer, 1997.","DOI":"10.1007\/BFb0028031"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1008\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1008\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:01:01Z","timestamp":1681243261000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,14]]},"references-count":10,"URL":"https:\/\/doi.org\/10.2168\/lmcs-7(4:7)2011","relation":{"is-same-as":[{"id-type":"arxiv","id":"1111.5901","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1111.5901","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2011,12,14]]},"article-number":"1008"}}