{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T13:11:08Z","timestamp":1769605868621,"version":"3.49.0"},"reference-count":14,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2018,7,24]],"date-time":"2018-07-24T00:00:00Z","timestamp":1532390400000},"content-version":"vor","delay-in-days":23,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider two\u2010variable, first\u2010order logic in which a single distinguished predicate is required to be interpreted as a transitive relation. We show that the finite satisfiability problem for this logic is decidable in triply exponential non\u2010deterministic time. Complexity falls to doubly exponential non\u2010deterministic time if the transitive relation is constrained to be a partial order.<\/jats:p>","DOI":"10.1002\/malq.201700055","type":"journal-article","created":{"date-parts":[[2018,7,25]],"date-time":"2018-07-25T06:03:33Z","timestamp":1532498613000},"page":"218-248","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Finite satisfiability for two\u2010variable, first\u2010order logic with one transitive relation is decidable"],"prefix":"10.1002","volume":"64","author":[{"given":"Ian","family":"Pratt\u2010Hartmann","sequence":"first","affiliation":[{"name":"School of Computer Science University of Manchester Oxford Road Manchester M13 9PL United Kingdom"},{"name":"Instytut Matematyki i Informatyki Uniwersytet Opolski ul. Oleska 48 45\u2013040 Opole Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2018,7,24]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_10"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59207-2"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/421196"},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36576-1_19"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538363_22"},{"key":"e_1_2_7_7_1","first-page":"337","volume-title":"Computer Science Logic, 25th International Workshop \/ 20th Annual Conference of the EACSL, CSL 2011","author":"Kiero\u0144ski E.","year":"2011"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/120900095"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.49"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.39"},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/2695037"},{"issue":"1","key":"e_1_2_7_12_1","first-page":"1","article-title":"Two\u2010variable logic with two order relations","volume":"8","author":"Schwentick T.","year":"2012","journal-title":"Log. Methods Comput. Sci."},{"key":"e_1_2_7_13_1","first-page":"477","article-title":"A decision method for validity of sentences in two variables","volume":"27","author":"Scott D.","year":"1962","journal-title":"J. Symb. Log."},{"key":"e_1_2_7_14_1","first-page":"317","volume-title":"30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013","author":"Szwast W.","year":"2013"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2933594"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.201700055","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.201700055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T19:25:31Z","timestamp":1694978731000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.201700055"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["10.1002\/malq.201700055"],"URL":"https:\/\/doi.org\/10.1002\/malq.201700055","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7]]},"assertion":[{"value":"2017-09-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}