{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T19:19:54Z","timestamp":1758395994939,"version":"3.37.3"},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2020,5,12]],"date-time":"2020-05-12T00:00:00Z","timestamp":1589241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["I2420-N31"],"award-info":[{"award-number":["I2420-N31"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004956","name":"Austrian Ministry for Transport, Innovation and Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004956","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012416","name":"Federal Ministry for Digital and Economic Affairs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,5,22]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce a restricted second-order logic $\\textrm{SO}^{\\textit{plog}}$ for finite structures where second-order quantification ranges over relations of size at most poly-logarithmic in the size of the structure. We demonstrate the relevance of this logic and complexity class by several problems in database theory. We then prove a Fagin\u2019s style theorem showing that the Boolean queries which can be expressed in the existential fragment of $\\textrm{SO}^{\\textit{plog}}$ correspond exactly to the class of decision problems that can be computed by a non-deterministic Turing machine with random access to the input in time $O((\\log n)^k)$ for some $k \\ge 0$, i.e. to the class of problems computable in non-deterministic poly-logarithmic time. It should be noted that unlike Fagin\u2019s theorem which proves that the existential fragment of second-order logic captures NP over arbitrary finite structures, our result only holds over ordered finite structures, since $\\textrm{SO}^{\\textit{plog}}$ is too weak as to define a total order of the domain. Nevertheless, $\\textrm{SO}^{\\textit{plog}}$ provides natural levels of expressibility within poly-logarithmic space in a way which is closely related to how second-order logic provides natural levels of expressibility within polynomial space. Indeed, we show an exact correspondence between the quantifier prefix classes of $\\textrm{SO}^{\\textit{plog}}$ and the levels of the non-deterministic poly-logarithmic time hierarchy, analogous to the correspondence between the quantifier prefix classes of second-order logic and the polynomial-time hierarchy. Our work closely relates to the constant depth quasipolynomial size AND\/OR circuits and corresponding restricted second-order logic defined by David A. Mix Barrington in 1992. We explore this relationship in detail.<\/jats:p>","DOI":"10.1093\/jigpal\/jzz078","type":"journal-article","created":{"date-parts":[[2019,11,18]],"date-time":"2019-11-18T14:07:35Z","timestamp":1574086055000},"page":"389-412","source":"Crossref","is-referenced-by-count":3,"title":["A restricted second-order logic for non-deterministic poly-logarithmic time"],"prefix":"10.1093","volume":"28","author":[{"given":"Flavio","family":"Ferrarotti","sequence":"first","affiliation":[{"name":"Software Competence Center Hagenberg 4232, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sen\u00c9n","family":"Gonz\u00c1les","sequence":"first","affiliation":[{"name":"Software Competence Center Hagenberg 4232, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus-Dieter","family":"Schewe","sequence":"first","affiliation":[{"name":"Zhejiang University, UIUC Institute, Haining 314400, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00c9 Mar\u00cda","family":"Turull-Torres","sequence":"first","affiliation":[{"name":"Universidad Nacional de La Matanza, Buenos Aires C1093 ABE, Argentina"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,5,12]]},"reference":[{"key":"2020060108500270600_ref1","doi-asserted-by":"crossref","first-page":"684","DOI":"10.1145\/2897518.2897542","article-title":"Graph isomorphism in quasipolynomial time","volume-title":"Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2016)","author":"Babai","year":"2016"},{"key":"2020060108500270600_ref2","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/S0168-0072(99)00005-6","article-title":"Choiceless polynomial time","volume":"100","author":"Blass","year":"1999","journal-title":"Annals of Pure and Applied Logic"},{"key":"2020060108500270600_ref3","first-page":"783","article-title":"Predicate logic as a modeling language: modeling and solving some machine learning and data mining problems with IDP3","volume":"15","author":"Bruynooghe","year":"2015","journal-title":"TPLP"},{"key":"2020060108500270600_ref4","first-page":"151","article-title":"The complexity of theorem-proving procedures","volume-title":"Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC \u201871","author":"Cook","year":"1971"},{"key":"2020060108500270600_ref5","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1006\/inco.1998.2703","article-title":"A restricted second order logic for finite structures","volume":"143","author":"Dawar","year":"1998","journal-title":"Information and Computation"},{"key":"2020060108500270600_ref6","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1093\/logcom\/8.2.189","article-title":"Subclasses of binary NP","volume":"8","author":"Durand","year":"1998","journal-title":"Journal of Logic and Computation"},{"key":"2020060108500270600_ref7","first-page":"37","article-title":"Second-order logic over strings: Regular and non-regular fragments","volume-title":"Developments in Language Theory","author":"Eiter","year":"2001"},{"key":"2020060108500270600_ref8","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/331605.331609","article-title":"Existential second-order logic over strings","volume":"47","author":"Eiter","year":"2000","journal-title":"Journal of the ACM"},{"volume-title":"Contributions to Model Theory of Finite Structures","year":"1973","author":"Fagin","key":"2020060108500270600_ref9"},{"key":"2020060108500270600_ref10","article-title":"The polylog-time hierarchy captured by restricted second-order logic","volume-title":"Post-Proceedings of the 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (to appear)","author":"Ferrarotti","year":"2019"},{"key":"2020060108500270600_ref11","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1145\/972639.972646","article-title":"Existential second-order logic over graphs: Charting the tractability frontier","volume":"51","author":"Gottlob","year":"2004","journal-title":"Journal of the ACM"},{"key":"2020060108500270600_ref12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","article-title":"Capturing complexity classes by fragments of second-order logic","volume":"101","author":"Gr\u00e4del","year":"1992","journal-title":"Theoretical Computer Science"},{"volume-title":"Finite Model Theory and its Applications. Texts in Theoretical Computer Science. An EATCS Series","year":"2007","author":"Gr\u00e4del","key":"2020060108500270600_ref13"},{"key":"2020060108500270600_ref14","first-page":"270","article-title":"A second-order logic in which variables range over relations with complete first-order types","volume-title":"SCCC","author":"Grosso","year":"2010"},{"key":"2020060108500270600_ref15","first-page":"581","article-title":"FO(FD): extending classical logic with rule-based fixpoint definitions","volume":"10","author":"Hou","year":"2010","journal-title":"TPLP"},{"key":"2020060108500270600_ref16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"Immerman","year":"1999"},{"key":"2020060108500270600_ref17","first-page":"205","article-title":"Logics for context-free languages","volume-title":"CSL","author":"Lautemann","year":"1994"},{"key":"2020060108500270600_ref18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"Libkin","year":"2004"},{"key":"2020060108500270600_ref19","first-page":"86","article-title":"Quasipolynomial size circuit classes","volume-title":"Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22\u201325, 1992","author":"David","year":"1992"},{"key":"2020060108500270600_ref20","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","article-title":"On uniformity within NC${{\\hspace *{-0.0001pt}}}^1$","volume":"41","author":"Mix Barrington","year":"1990","journal-title":"Journal of Computer and System Sciences"},{"key":"2020060108500270600_ref21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial-time hierarchy","volume":"3","author":"Stockmeyer","year":"1976","journal-title":"Theoretical Computer Science"}],"container-title":["Logic Journal of the IGPL"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/jigpal\/article-pdf\/28\/3\/389\/33330582\/jzz078.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/jigpal\/article-pdf\/28\/3\/389\/33330582\/jzz078.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,3]],"date-time":"2021-02-03T23:09:38Z","timestamp":1612393778000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jigpal\/article\/28\/3\/389\/5698568"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,12]]},"references-count":21,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2020,5,12]]},"published-print":{"date-parts":[[2020,5,22]]}},"URL":"https:\/\/doi.org\/10.1093\/jigpal\/jzz078","relation":{},"ISSN":["1367-0751","1368-9894"],"issn-type":[{"type":"print","value":"1367-0751"},{"type":"electronic","value":"1368-9894"}],"subject":[],"published-other":{"date-parts":[[2020,6]]},"published":{"date-parts":[[2020,5,12]]}}}