{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T16:02:16Z","timestamp":1765123336568,"version":"3.37.3"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2022,2,21]],"date-time":"2022-02-21T00:00:00Z","timestamp":1645401600000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["324435","328987"],"award-info":[{"award-number":["324435","328987"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2016\/21\/B\/ST6\/01444"],"award-info":[{"award-number":["2016\/21\/B\/ST6\/01444"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,7,25]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>One-dimensional fragment of first-order logic is obtained by restricting quantification to blocks of existential (universal) quantifiers that leave at most one variable free. We investigate this fragment over words and trees, presenting a complete classification of the complexity of its satisfiability problem for various navigational signatures and comparing its expressive power with other important formalisms. These include the two-variable fragment with counting and the unary negation fragment.<\/jats:p>","DOI":"10.1093\/logcom\/exac002","type":"journal-article","created":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T20:13:28Z","timestamp":1645042408000},"page":"902-941","source":"Crossref","is-referenced-by-count":1,"title":["One-dimensional fragment over words and trees"],"prefix":"10.1093","volume":"32","author":[{"given":"Emanuel","family":"Kiero\u0144ski","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Computer Science , University of Wroc\u0142aw, ul. Joliot-Curie 15, 50-383 Wroc\u0142aw, Poland"}]},{"given":"Antti","family":"Kuusisto","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology and Communication Sciences , Tampere University, Kalevantie 4, 33100 Tampere, Finland and Mathematics and Statistics, University of Helsinki, Pietari Kalmin katu 5, 00560 Helsinki, Finland"}]}],"member":"286","published-online":{"date-parts":[[2022,2,19]]},"reference":[{"key":"2022081614301836500_ref1","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1023\/A:1004275029985","article-title":"Modal languages and bounded fragments of predicate logic","volume":"27","author":"Andr\u00e9ka","year":"1998","journal-title":"Journal of Philosophical Logic"},{"key":"2022081614301836500_ref2","doi-asserted-by":"crossref","first-page":"32:1","DOI":"10.1145\/2996796","article-title":"Complexity of two-variable logic on finite trees","volume":"17","author":"Benaim","year":"2016","journal-title":"ACM Transactions on Computational Logic"},{"key":"2022081614301836500_ref3","first-page":"11:1","article-title":"Extending two-variable logic on trees","volume-title":"The 26th EACSL Annual Conference on Computer Science Logic, CSL 2017","author":"Bednarczyk","year":"2017"},{"key":"2022081614301836500_ref4","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/1970398.1970403","article-title":"Two-variable logic on data words","volume":"12","author":"Boja\u0144czyk","year":"2011","journal-title":"ACM Transactions on Computational Logic"},{"key":"2022081614301836500_ref5","doi-asserted-by":"crossref","first-page":"8:1","DOI":"10.1145\/1346330.1346333","article-title":"Xpath satisfiability in the presence of dtds","volume":"55","author":"Benedikt","year":"2008","journal-title":"Journal of the ACM"},{"key":"2022081614301836500_ref6","article-title":"Satisfiability of the two-variable fragment of first-order logic over trees","author":"Charatonik","year":"2013","journal-title":"CoRR"},{"key":"2022081614301836500_ref7","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"Journal of the ACM"},{"key":"2022081614301836500_ref8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-12(2:8)2016","article-title":"Two-variable logic with counting and a linear order","volume":"12","author":"Charatonik","year":"2016","journal-title":"Logical Methods in Computer Science"},{"key":"2022081614301836500_ref9","doi-asserted-by":"crossref","first-page":"31:1","DOI":"10.1145\/2983622","article-title":"Two-variable logic with counting and trees","volume":"17","author":"Charatonik","year":"2016","journal-title":"ACM Transactions on Computational Logic"},{"key":"2022081614301836500_ref10","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1006\/inco.2001.2953","article-title":"First-order logic with two variables and unary temporal logic","volume":"179","author":"Etessami","year":"2002","journal-title":"Inf. Comput."},{"key":"2022081614301836500_ref11","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0013976","volume-title":"Temporal Logic: Mathematical Foundations and\nComputational Aspects, vol. 1","author":"Gabbay","year":"1994"},{"key":"2022081614301836500_ref12","doi-asserted-by":"crossref","first-page":"1719","DOI":"10.2307\/2586808","article-title":"On the restraining power of guards","volume":"64","author":"Gr\u00e4del","year":"1999","journal-title":"Journal of Symbolic Logic"},{"key":"2022081614301836500_ref13","first-page":"274","article-title":"One-dimensional fragment of first-order logic","volume":"10","author":"Hella","year":"2014","journal-title":"Advances in Modal Logic"},{"volume-title":"Tense Logic and the Theory of Linear Order","year":"1968","author":"Kamp","key":"2022081614301836500_ref14"},{"key":"2022081614301836500_ref15","doi-asserted-by":"crossref","first-page":"1663","DOI":"10.1016\/j.ic.2006.08.001","article-title":"On the complexity of the two-variable guarded fragment with transitive guards","volume":"204","author":"Kieronski","year":"2006","journal-title":"Information and Computation"},{"key":"2022081614301836500_ref16","first-page":"38:1","article-title":"One-dimensional logic over words","volume-title":"The 25th EACSL Annual Conference on Computer Science Logic, CSL 2016","author":"Kieronski","year":"2016"},{"key":"2022081614301836500_ref17","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/978-3-662-44522-8_31","article-title":"Complexity and expressivity of uniform one-dimensional fragment with equality","author":"Kieronski","year":"2014","journal-title":"Mathematical Foundations of Computer Science 2014"},{"key":"2022081614301836500_ref18","first-page":"597","article-title":"Uniform one-dimensional fragments with one equivalence relation","volume-title":"Computer Science Logic","author":"Kieronski","year":"2015"},{"key":"2022081614301836500_ref19","first-page":"64:1","article-title":"One-dimensional logic over trees","volume-title":"42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017","author":"Kieronski","year":"2017"},{"key":"2022081614301836500_ref20","first-page":"16:1","article-title":"Two-variable logics with some betweenness relations: expressiveness, satisfiability and membership","volume":"16","author":"Krebs","year":"2020","journal-title":"Logical Methods in Computer Science"},{"key":"2022081614301836500_ref21","article-title":"On the uniform one-dimensional fragment","volume-title":"Proceedings of International Workshop on Description Logic","author":"Kuusisto","year":"2016"},{"key":"2022081614301836500_ref22","first-page":"477","article-title":"Xpath with conditional axis relations","volume":"2004","author":"Marx","year":"2004","journal-title":"Advances in Database Technology - EDBT"},{"key":"2022081614301836500_ref23","first-page":"41","article-title":"Semantic characterization of navigational XPath","volume-title":"ACM SIGMOD Record","author":"Marx","year":"2004"},{"key":"2022081614301836500_ref24","doi-asserted-by":"crossref","first-page":"685","DOI":"10.2307\/2695037","article-title":"Two variable first-order logic over ordered domains","volume":"66","author":"Otto","year":"2001","journal-title":"Journal of Symbolic Logic"},{"key":"2022081614301836500_ref25","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1145\/3828.3837","article-title":"The complexity of propositional linear temporal logics","volume":"32","author":"Sistla","year":"1985","journal-title":"Journal of the ACM"},{"key":"2022081614301836500_ref26","first-page":"477","article-title":"A decision method for validity of sentences in two variables","volume":"27","author":"Scott","year":"1962","journal-title":"Journal Symbolic Logic"},{"key":"2022081614301836500_ref27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-9(3:25)2013","article-title":"Unary negation","volume":"9","author":"Segoufin","year":"2013","journal-title":"Logical Methods in Computer Science"},{"volume-title":"The Complexity of Decision Problems in Automata Theory and Logic","year":"1974","author":"Stockmeyer","key":"2022081614301836500_ref28"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/32\/5\/902\/45445588\/exac002.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/32\/5\/902\/45445588\/exac002.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T14:34:37Z","timestamp":1660660477000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/32\/5\/902\/6532078"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,19]]},"references-count":28,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,2,19]]},"published-print":{"date-parts":[[2022,7,25]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exac002","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"type":"print","value":"0955-792X"},{"type":"electronic","value":"1465-363X"}],"subject":[],"published-other":{"date-parts":[[2022,7]]},"published":{"date-parts":[[2022,2,19]]}}}