{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T20:45:39Z","timestamp":1789591539861,"version":"build-2803163510"},"reference-count":34,"publisher":"IEEE","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1109\/lics.2017.8005141","type":"proceedings-article","created":{"date-parts":[[2017,8,10]],"date-time":"2017-08-10T16:43:24Z","timestamp":1502383404000},"page":"1-12","source":"Crossref","is-referenced-by-count":27,"title":["Decidability, complexity, and expressiveness of first-order logic over the subword ordering"],"prefix":"10.1109","author":[{"given":"Simon","family":"Halfon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philippe","family":"Schnoebelen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georg","family":"Zetzsche","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.2307\/2268308"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132584"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90021-1"},{"key":"ref30","author":"matiyasevich","year":"1993","journal-title":"Hilbert's Tenth Problem"},{"key":"ref34","author":"stockmeyer","year":"1974","journal-title":"The Complexity of Decision Problems in Automata Theory and Logic"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0062837"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39611-3_21"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1966-0201310-3"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60246-1_113"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-10(4:4)2014"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603092"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005141"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90025-1"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s10515-012-0111-x"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322058"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13962-8_28"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-012-0234-7"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.16"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2012013"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2005039"},{"key":"ref5","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1002\/malq.19880340410","article-title":"Definability in the existential theory of concatenation and undecidable extensions of this theory","volume":"34","author":"buchi","year":"1988","journal-title":"Z Math Logik Grundlag Math"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108005802"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017470"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1023\/B:FORM.0000033962.51898.1a"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02112533"},{"key":"ref1","first-page":"150","article-title":"String constraints for verification","author":"abdulla","year":"2014","journal-title":"CAV 2014 LNCS 8559"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/2743014"},{"key":"ref22","first-page":"84","article-title":"Decidability in the logic of subsequences and supersequences","author":"karandikar","year":"2015","journal-title":"Proc FST&TCS 2015 LIPIcs 45"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.028"},{"key":"ref24","first-page":"37:1","article-title":"The height of piecewise-testable languages with applications in logical complexity","author":"karandikar","year":"2016","journal-title":"Proc CSL 2016 LIPIcs 62"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9561-9"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38771-5_26"},{"key":"ref25","first-page":"681","article-title":"Monadic second-order logics with cardinalities","author":"klaedtke","year":"2003","journal-title":"Proc ICALP 2003 LNCS 2719"}],"event":{"name":"2017 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)","location":"Reykjavik, Iceland","start":{"date-parts":[[2017,6,20]]},"end":{"date-parts":[[2017,6,23]]}},"container-title":["2017 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/7999337\/8005055\/08005141.pdf?arnumber=8005141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T03:39:23Z","timestamp":1569987563000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/8005141\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6]]},"references-count":34,"URL":"https:\/\/doi.org\/10.1109\/lics.2017.8005141","relation":{},"subject":[],"published":{"date-parts":[[2017,6]]}}}