{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,19]],"date-time":"2026-08-19T10:30:28Z","timestamp":1787135428777,"version":"3.56.0"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031999901","type":"print"},{"value":"9783031999918","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:00:00Z","timestamp":1761609600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:00:00Z","timestamp":1761609600000},"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":[[2026]]},"DOI":"10.1007\/978-3-031-99991-8_11","type":"book-chapter","created":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T05:35:57Z","timestamp":1761543357000},"page":"221-226","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Complexity of Formal Reasoning in State Space Models (Extended Abstract)"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2603-7827","authenticated-orcid":false,"given":"Eric","family":"Alsmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1621-0972","authenticated-orcid":false,"given":"Martin","family":"Lange","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,10,28]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","unstructured":"De, S., et al.: Griffin: mixing gated linear recurrences with doucetlocal attention for efficient language models (2024). https:\/\/doi.org\/10.48550\/arXiv.2402.19427","DOI":"10.48550\/arXiv.2402.19427"},{"key":"11_CR2","unstructured":"De\u00a0Giacomo, G., Vardi, M.Y.: Linear temporal logic and linear dynamic logic on finite traces. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pp. 854\u2013860. IJCAI \u201913, AAAI Press, Beijing, China (2013)"},{"key":"11_CR3","unstructured":"Gu, A., Dao, T.: Mamba: linear-time sequence modeling with selective state spaces. In: First Conference on Language Modeling (2024)"},{"key":"11_CR4","unstructured":"Gu, A., Goel, K., Re, C.: Efficiently modeling long sequences with structured state spaces. In: International Conference on Learning Representations (2022)"},{"key":"11_CR5","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations: Proceedings of a Symposium on the Complexity of Computer Computations, Held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and Sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, pp. 85\u2013103. Springer US, Boston, MA (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"11_CR6","unstructured":"Mehta, H., Gupta, A., Cutkosky, A., Neyshabur, B.: Long range language modeling via gated state spaces. In: The Eleventh International Conference on Learning Representations (2023)"},{"key":"11_CR7","unstructured":"Merrill, W., Petty, J., Sabharwal, A.: The illusion of state in state-space models. In: Proceedings of the 41st International Conference on Machine Learning. ICML\u201924, vol.\u00a0235, pp. 35492\u201335506. JMLR.org, Vienna, Austria (2024)"},{"key":"11_CR8","volume-title":"Computation: Finite and Infinite Machines","author":"ML Minsky","year":"1967","unstructured":"Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall Inc, USA (1967)"},{"key":"11_CR9","unstructured":"Orvieto, A., et al.: Resurrecting recurrent neural networks for long sequences. In: Proceedings of the 40th International Conference on Machine Learning. ICML\u201923, JMLR.org, Honolulu, Hawaii, USA (2023)"},{"key":"11_CR10","unstructured":"S\u00e4lzer, M., Alsmann, E., Lange, M.: Transformer encoder satisfiability: complexity and impact on formal reasoning. In: The Thirteenth International Conference on Learning Representations (2024)"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Sarrof, Y., Veitsman, Y., Hahn, M.: The expressive capacity of state space models: a formal language perspective. In: The Thirty-eighth Annual Conference on Neural Information Processing Systems (2024)","DOI":"10.52202\/079017-1304"},{"key":"11_CR12","doi-asserted-by":"publisher","unstructured":"Sun, Y., et al.: Retentive network: a successor to transformer for large language models (2023). https:\/\/doi.org\/10.48550\/arXiv.2307.08621","DOI":"10.48550\/arXiv.2307.08621"},{"key":"11_CR13","unstructured":"Yang, S., Wang, B., Shen, Y., Panda, R., Kim, Y.: Gated linear attention transformers with hardware-efficient training. In: Proceedings of the 41st International Conference on Machine Learning. ICML\u201924, JMLR.org, Vienna, Austria (2024)"}],"container-title":["Lecture Notes in Computer Science","AI Verification"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-99991-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,19]],"date-time":"2026-08-19T10:14:01Z","timestamp":1787134441000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-99991-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,28]]},"ISBN":["9783031999901","9783031999918"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-99991-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,28]]},"assertion":[{"value":"28 October 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAIV","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on AI Verification","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Zagreb","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Croatia","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":"21 July 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"saiv2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.aiverification.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}