{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:06:44Z","timestamp":1743037604555,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662595329"},{"type":"electronic","value":"9783662595336"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-662-59533-6_13","type":"book-chapter","created":{"date-parts":[[2019,6,22]],"date-time":"2019-06-22T19:02:35Z","timestamp":1561230155000},"page":"208-222","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Descriptive Complexity of Deterministic Polylogarithmic Time"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2278-8233","authenticated-orcid":false,"given":"Flavio","family":"Ferrarotti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sen\u00e9n","family":"Gonz\u00e1lez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 Mar\u00eda","family":"Turull Torres","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0072-3252","authenticated-orcid":false,"given":"Jan","family":"Van\u00a0den Bussche","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1582-3718","authenticated-orcid":false,"given":"Jonni","family":"Virtema","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,9]]},"reference":[{"key":"13_CR1","volume-title":"Foundations of Databases","author":"S Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Boston (1995)"},{"key":"13_CR2","volume-title":"Finite Model Theory","author":"HD Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"13_CR3","unstructured":"Fagin, R.: Contributions to model theory of finite structures. Ph.D. thesis, U. C. Berkeley (1973)"},{"key":"13_CR4","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R. (ed.) Complexity of Computation. SIAM-AMS Proceedings, vol. 7, pp. 43\u201373 (1974)"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Ferrarotti, F., Gonz\u00e1lez, S., Schewe, K.D., Turull Torres, J.M.: The polylog-time hierarchy captured by restricted second-order logic. In: Post-Proceedings of the 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. IEEE Computer Society (2019, to appear)","DOI":"10.1109\/SYNASC.2018.00032"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Ferrarotti F., Gonz\u00e1lez S., Turull Torres J.M., Van den Bussche J., Virtema J.: Descriptive complexity of deterministic polylogarithmic time. CoRR abs\/1903.03413 (2019)","DOI":"10.1007\/978-3-662-59533-6_13"},{"key":"13_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68804-8","volume-title":"Finite Model Theory and Its Applications","author":"E Gr\u00e4del","year":"2007","unstructured":"Gr\u00e4del, E., et al.: Finite Model Theory and Its Applications. Springer, Heidelberg (2007). \nhttps:\/\/doi.org\/10.1007\/3-540-68804-8"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1016\/j.jcss.2003.09.002","volume":"68","author":"E Grandjean","year":"2004","unstructured":"Grandjean, E., Olive, F.: Graph properties checkable in linear time in the number of vertices. J. Comput. Syst. Sci. 68, 546\u2013597 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR9","series-title":"Lecture Notes in Logic","doi-asserted-by":"publisher","DOI":"10.1017\/9781139028868","volume-title":"Descriptive Complexity, Canonisation, and Definable Graph Structure Theory","author":"M Grohe","year":"2017","unstructured":"Grohe, M.: Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic. Cambridge University Press, Cambridge (2017)"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Grohe, M., Pakusa, W.: Descriptive complexity of linear equation systems and applications to propositional proof complexity. In: Proceedings of the 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017, pp. 1\u201312. IEEE Computer Society (2017)","DOI":"10.1109\/LICS.2017.8005081"},{"key":"13_CR11","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BFb0099486","volume-title":"Computation and Proof Theory","author":"Y Gurevich","year":"1984","unstructured":"Gurevich, Y.: Toward logic tailored for computational complexity. In: B\u00f6rger, E., Oberschelp, W., Richter, M.M., Schinzel, B., Thomas, W. (eds.) Computation and Proof Theory. LNM, vol. 1104, pp. 175\u2013216. Springer, Heidelberg (1984). \nhttps:\/\/doi.org\/10.1007\/BFb0099486"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y Gurevich","year":"1986","unstructured":"Gurevich, Y., Shelah, S.: Fixed-point extensions of first-order logic. Ann. Pure Appl. Logic 32, 265\u2013280 (1986)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"3","key":"13_CR13","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/0022-0000(81)90039-8","volume":"22","author":"N Immerman","year":"1981","unstructured":"Immerman, N.: Number of quantifiers is better than number of tape cells. J. Comput. Syst. Sci. 22(3), 384\u2013406 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N Immerman","year":"1986","unstructured":"Immerman, N.: Relational queries computable in polynomial time. Inf. Control 68, 86\u2013104 (1986)","journal-title":"Inf. Control"},{"key":"13_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Springer, New York (1999). \nhttps:\/\/doi.org\/10.1007\/978-1-4612-0539-5"},{"key":"13_CR16","series-title":"Sorting and Searching","volume-title":"The Art of Computer Programming","author":"D Knuth","year":"1998","unstructured":"Knuth, D.: The Art of Computer Programming. Sorting and Searching, vol. 3. Addison-Wesley, Boston (1998)"},{"key":"13_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer, Heidelberg (2004). \nhttps:\/\/doi.org\/10.1007\/978-3-662-07003-1"},{"key":"13_CR18","unstructured":"Mix Barrington, D.A.: Quasipolynomial size circuit classes. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, 22\u201325 June 1992, pp. 86\u201393. IEEE Computer Society (1992)"},{"issue":"3","key":"13_CR19","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"DA Mix Barrington","year":"1990","unstructured":"Mix Barrington, D.A., Immerman, N., Straubing, H.: On uniformity within NC$$^1$$. J. Comput. Syst. Sci. 41(3), 274\u2013306 (1990)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR20","volume-title":"Database Management Systems","author":"R Ramakrishnan","year":"2003","unstructured":"Ramakrishnan, R., Gehrke, J.: Database Management Systems, 3rd edn. McGraw-Hill, Inc., New York (2003)","edition":"3"},{"issue":"1","key":"13_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"LJ Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theor. Comput. Sci. 3(1), 1\u201322 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"Vardi, M.: The complexity of relational query languages. In: Proceedings 14th ACM Symposium on the Theory of Computing, pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Logic, Language, Information, and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-59533-6_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,6]],"date-time":"2019-12-06T15:02:56Z","timestamp":1575644576000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-59533-6_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783662595329","9783662595336"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-59533-6_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"9 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WoLLIC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Logic, Language, Information, and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Utrecht","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wollic2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/wollic2019.sites.uu.nl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2,3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}