{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T04:09:22Z","timestamp":1751342962272,"version":"3.41.0"},"publisher-location":"Cham","reference-count":11,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031970993","type":"print"},{"value":"9783031971006","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-97100-6_10","type":"book-chapter","created":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T14:08:45Z","timestamp":1751292525000},"page":"137-150","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Disjunctive Complexity"],"prefix":"10.1007","author":[{"given":"Nikita","family":"Ivanov","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Rubtsov","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9822-1060","authenticated-orcid":false,"given":"Mikhail","family":"Vyalyi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,29]]},"reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge Univ, Press (2009)"},{"issue":"4","key":"10_CR3","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"Z Bar-Yossef","year":"2004","unstructured":"Bar-Yossef, Z., Jayram, T., Kumar, R., Sivakumar, D.: Information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci. 68(4), 702\u2013732 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR4","unstructured":"Bar-Yossef, Z., Kumar R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201902), pp. 623\u2013632. Society for Industrial and Applied Mathematics, USA (2002)"},{"key":"10_CR5","unstructured":"Chakrabarti, A.: Data Stream Algorithms. Lecture Notes. https:\/\/www.cs.dartmouth.edu\/~ac\/Teach\/data-streams-lecnotes.pdf Last update: March 7, 2024"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Chou, C.-N., Golovnev, A., Velusamy, S.: Optimal streaming approximations for all Boolean Max-2CSPs and Max-$$k$$sat. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 330\u2013341. Durham, NC, USA (2020)","DOI":"10.1109\/FOCS46700.2020.00039"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Gibbons, P., Trithapura, S.: Estimating simple functions on the union of data streams. In: SPAA01: 13th ACM Symposium on Parallel Algorithms and Architectures, pp. 281\u2013290. Association for Computing Machinery, New York, NY, USA (2001)","DOI":"10.1145\/378580.378687"},{"issue":"10","key":"10_CR8","doi-asserted-by":"publisher","first-page":"6646","DOI":"10.1109\/TIT.2014.2339859","volume":"60","author":"R Jain","year":"2010","unstructured":"Jain, R., Nayak, A.: The space complexity of recognizing well-parenthesized expressions in the streaming model: the index function revisited. IEEE Trans. Inf. Theory 60(10), 6646\u20136668 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24508-4","volume-title":"Boolean Function Complexity Advances and Frontiers","author":"S Jukna","year":"2012","unstructured":"Jukna, S.: Boolean Function Complexity Advances and Frontiers. Springer-Verlag, Berlin Heidelberg (2012)"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends\u00ae Theoret. Comput. Sci. 1(2), 117\u2013236 (2005)","DOI":"10.1561\/0400000002"},{"issue":"3","key":"10_CR11","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1134\/S0032946024030050","volume":"60","author":"AA Rubtsov","year":"2024","unstructured":"Rubtsov, A.A., Vyalyi, M.N.: On universality of regular realizability problems. Probl. Inf. Transm. 60(3), 209\u2013232 (2024)","journal-title":"Probl. Inf. Transm."}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-97100-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T14:08:47Z","timestamp":1751292527000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-97100-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031970993","9783031971006"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-97100-6_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"29 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"DCFS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Descriptional Complexity of Formal Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Loughborough","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 July 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 July 2025","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":"dcfs2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.lboro.ac.uk\/departments\/compsci\/events\/dcfs-2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}