{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T17:08:21Z","timestamp":1776272901619,"version":"3.50.1"},"publisher-location":"Cham","reference-count":51,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032227294","type":"print"},{"value":"9783032227300","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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-032-22730-0_24","type":"book-chapter","created":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T16:24:20Z","timestamp":1776270260000},"page":"505-526","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Complete Propositional Dynamic Logic for Regular Expressions with Lookahead"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4106-0408","authenticated-orcid":false,"given":"Yoshiki","family":"Nakamura","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,15]]},"reference":[{"key":"24_CR1","doi-asserted-by":"publisher","unstructured":"Afanasiev, L., Blackburn, P., Dimitriou, I., Gaiffe, B., Goris, E., Marx, M., de\u00a0Rijke, M.: PDL for ordered trees. Journal of Applied Non-Classical Logics 15(2), 115\u2013135 (2005). https:\/\/doi.org\/10.3166\/jancl.15.115-135","DOI":"10.3166\/jancl.15.115-135"},{"key":"24_CR2","doi-asserted-by":"publisher","unstructured":"Andr\u00e9ka, H., Mikul\u00e1s, S., N\u00e9meti, I.: The equational theory of Kleene lattices. Theoretical Computer Science 412(52), 7099\u20137108 (2011). https:\/\/doi.org\/10.1016\/J.TCS.2011.09.024","DOI":"10.1016\/J.TCS.2011.09.024"},{"key":"24_CR3","doi-asserted-by":"publisher","unstructured":"Ben-Ari, M., Halpern, J., Pnueli, A.: Deterministic propositional dynamic logic: Finite models, complexity, and completeness. Journal of Computer and System Sciences 25(3), 402\u2013417 (1982). https:\/\/doi.org\/10.1016\/0022-0000(82)90018-6","DOI":"10.1016\/0022-0000(82)90018-6"},{"key":"24_CR4","doi-asserted-by":"publisher","unstructured":"Benevides, M., Gomes, L., Lopes, B.: Towards determinism in PDL: relations and proof theory. Journal of Logic and Computation 35(5), exae022 (2025). https:\/\/doi.org\/10.1093\/logcom\/exae022","DOI":"10.1093\/logcom\/exae022"},{"key":"24_CR5","doi-asserted-by":"publisher","unstructured":"Blackburn, P., Meyer-Viol, W.: Linguistics, logic and finite trees. Bulletin of the IGPL 2(1), 3\u201329 (1994). https:\/\/doi.org\/10.1093\/jigpal\/2.1.3","DOI":"10.1093\/jigpal\/2.1.3"},{"key":"24_CR6","doi-asserted-by":"publisher","unstructured":"Blackburn, P., Meyer-Viol, W., de\u00a0Rijke, M.: A proof system for finite trees. In: CSL. LNCS, vol.\u00a01092, pp. 86\u2013105. Springer (1996). https:\/\/doi.org\/10.1007\/3-540-61377-3_33","DOI":"10.1007\/3-540-61377-3_33"},{"key":"24_CR7","doi-asserted-by":"publisher","unstructured":"Brunet, P.: Reversible Kleene lattices. In: MFCS. LIPIcs, vol.\u00a083, pp. 66:1\u201366:14. Schloss Dagstuhl (2017). https:\/\/doi.org\/10.4230\/LIPICS.MFCS.2017.66","DOI":"10.4230\/LIPICS.MFCS.2017.66"},{"key":"24_CR8","doi-asserted-by":"publisher","unstructured":"Brunet, P.: A complete axiomatisation of a fragment of language algebra. In: CSL. LIPIcs, vol.\u00a0152, p. 11:1\u201311:15. Schloss Dagstuhl (2020). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2020.11","DOI":"10.4230\/LIPIcs.CSL.2020.11"},{"key":"24_CR9","doi-asserted-by":"publisher","unstructured":"Calvanese, D., De\u00a0Giacomo, G., Lenzerini, M., Vardi, M.: An automata-theoretic approach to regular XPath. In: DBPL. LNISA, vol.\u00a05708, pp. 18\u201335. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-03793-1_2","DOI":"10.1007\/978-3-642-03793-1_2"},{"key":"24_CR10","doi-asserted-by":"publisher","unstructured":"Chida, N., Terauchi, T.: On lookaheads in regular expressions with backreferences. IEICE Transactions on Information E106-D(5), 959\u2013975 (2023). https:\/\/doi.org\/10.1587\/transinf.2022EDP7098","DOI":"10.1587\/transinf.2022EDP7098"},{"key":"24_CR11","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., L\u00f6ding, C., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (2007), https:\/\/inria.hal.science\/hal-03367725"},{"key":"24_CR12","doi-asserted-by":"publisher","unstructured":"Danecki, R.: Propositional dynamic logic with strong loop predicate. In: MFCS. LNCS, vol.\u00a0176, pp. 573\u2013581. Springer (1984). https:\/\/doi.org\/10.1007\/BFb0030342","DOI":"10.1007\/BFb0030342"},{"key":"24_CR13","doi-asserted-by":"publisher","unstructured":"Das, A., Girlando, M.: Cyclic proofs, hypersequents, and transitive closure logic. In: IJCAR. LNAI, vol. 13385, pp. 509\u2013528. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-10769-6_30","DOI":"10.1007\/978-3-031-10769-6_30"},{"key":"24_CR14","unstructured":"De\u00a0Giacomo, G., Vardi, M.: Linear temporal logic and linear dynamic logic on finite traces. In: IJCAI. pp. 854\u2013860. AAAI Press (2013), https:\/\/www.ijcai.org\/Proceedings\/13\/Papers\/132.pdf"},{"key":"24_CR15","doi-asserted-by":"publisher","unstructured":"Desharnais, J., M\u00f6ller, B., Struth, G.: Kleene algebra with domain. ACM Transactions on Computational Logic 7(4), 798\u2013833 (2006). https:\/\/doi.org\/10.1145\/1183278.1183285","DOI":"10.1145\/1183278.1183285"},{"key":"24_CR16","doi-asserted-by":"publisher","unstructured":"Desharnais, J., Struth, G.: Modal semirings revisited. In: MPC. LNTCS, vol.\u00a05133, pp. 360\u2013387. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-70594-9_19","DOI":"10.1007\/978-3-540-70594-9_19"},{"key":"24_CR17","doi-asserted-by":"publisher","unstructured":"Desharnais, J., Struth, G.: Internal axioms for domain semirings. Science of Computer Programming 76(3), 181\u2013203 (2011). https:\/\/doi.org\/10.1016\/j.scico.2010.05.007","DOI":"10.1016\/j.scico.2010.05.007"},{"key":"24_CR18","unstructured":"Developers, T.P.: Perl-compatible regular expressions (revised api: PCRE2), https:\/\/www.pcre.org\/current\/doc\/html\/pcre2syntax.html, last updated: 14 October 2025"},{"key":"24_CR19","doi-asserted-by":"publisher","unstructured":"Doumane, A., Pous, D.: Completeness for identity-free Kleene lattices. In: CONCUR. LIPIcs, vol.\u00a0118, pp. 18:1\u201318:17. Schloss Dagstuhl (2018). https:\/\/doi.org\/10.4230\/LIPICS.CONCUR.2018.18","DOI":"10.4230\/LIPICS.CONCUR.2018.18"},{"key":"24_CR20","doi-asserted-by":"publisher","unstructured":"Fischer, M., Ladner, R.: Propositional dynamic logic of regular programs. Journal of Computer and System Sciences 18(2), 194\u2013211 (1979). https:\/\/doi.org\/10.1016\/0022-0000(79)90046-1","DOI":"10.1016\/0022-0000(79)90046-1"},{"key":"24_CR21","unstructured":"Friedl, J.: Mastering Regular Expressions. O\u2019Reilly Media, Inc., 3 edn. (2006), https:\/\/www.oreilly.com\/library\/view\/mastering-regular-expressions\/0596528124\/"},{"key":"24_CR22","unstructured":"Gabbay, D.: Axiomatizations of logics of programs (1977), note: unpublished manuscript"},{"key":"24_CR23","doi-asserted-by":"publisher","unstructured":"Harel, D., Kozen, D., Tiuryn, J.: Dynamic Logic. The MIT Press (2000). https:\/\/doi.org\/10.7551\/mitpress\/2516.001.0001","DOI":"10.7551\/mitpress\/2516.001.0001"},{"key":"24_CR24","doi-asserted-by":"publisher","unstructured":"Hollenberg, M.: Equational axioms of test algebra. In: CSL. LNCS, vol.\u00a01414, pp. 295\u2013310. Springer (1998). https:\/\/doi.org\/10.1007\/BFb0028021","DOI":"10.1007\/BFb0028021"},{"key":"24_CR25","doi-asserted-by":"publisher","unstructured":"Jiang, T., Ravikumar, B.: A note on the space complexity of some decision problems for finite automata. Information Processing Letters 40(1), 25\u201331 (1991). https:\/\/doi.org\/10.1016\/S0020-0190(05)80006-7","DOI":"10.1016\/S0020-0190(05)80006-7"},{"key":"24_CR26","unstructured":"Kleene, S.: Representation of events in nerve nets and finite automata. Tech. rep., RAND Corporation (1951), https:\/\/www.rand.org\/pubs\/research_memoranda\/RM704.html"},{"key":"24_CR27","doi-asserted-by":"publisher","unstructured":"Kozen, D.: A completeness theorem for Kleene algebras and the algebra of regular events. In: LICS. pp. 214\u2013225. IEEE (1991). https:\/\/doi.org\/10.1109\/LICS.1991.151646","DOI":"10.1109\/LICS.1991.151646"},{"key":"24_CR28","unstructured":"Kozen, D.: Typed Kleene algebra. Tech. rep., Cornell University (1998), https:\/\/hdl.handle.net\/1813\/7323"},{"key":"24_CR29","doi-asserted-by":"publisher","unstructured":"Kozen, D., Parikh, R.: An elementary proof of the completeness of PDL. Theoretical Computer Science 14(1), 113\u2013118 (1981). https:\/\/doi.org\/10.1016\/0304-3975(81)90019-0","DOI":"10.1016\/0304-3975(81)90019-0"},{"key":"24_CR30","doi-asserted-by":"publisher","unstructured":"Kracht, M.: Syntactic codes and grammar refinement. Journal of Logic, Language and Information 4(1), 41\u201360 (1995). https:\/\/doi.org\/10.1007\/BF01048404","DOI":"10.1007\/BF01048404"},{"key":"24_CR31","doi-asserted-by":"publisher","unstructured":"Kracht, M.: Inessential features. In: Logical Aspects of Computational Linguistics. pp. 43\u201362. Springer (1997). https:\/\/doi.org\/10.1007\/BFb0052150","DOI":"10.1007\/BFb0052150"},{"key":"24_CR32","doi-asserted-by":"publisher","unstructured":"Mamouras, K., Chattopadhyay, A.: Efficient matching of regular expressions with lookaround assertions. Proc. ACM Program. Lang. 8(POPL), 92:2761\u201392:2791 (2024). https:\/\/doi.org\/10.1145\/3632934","DOI":"10.1145\/3632934"},{"key":"24_CR33","doi-asserted-by":"publisher","unstructured":"Miyazaki, T., Minamide, Y.: Derivatives of regular expressions with lookahead. Journal of Information Processing 27, 422\u2013430 (2019). https:\/\/doi.org\/10.2197\/ipsjjip.27.422","DOI":"10.2197\/ipsjjip.27.422"},{"key":"24_CR34","doi-asserted-by":"publisher","unstructured":"Morihata, A.: Translation of regular expression with lookahead into finite state automaton (written in Japanese). Computer Software 29(1), 1_147\u20131_158 (2012). https:\/\/doi.org\/10.11309\/jssst.29.1_147","DOI":"10.11309\/jssst.29.1_147"},{"key":"24_CR35","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: Partial derivatives on graphs for Kleene allegories. In: LICS. pp. 1\u201312. IEEE (2017). https:\/\/doi.org\/10.1109\/LICS.2017.8005132","DOI":"10.1109\/LICS.2017.8005132"},{"key":"24_CR36","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: Existential calculi of relations with transitive closure: Complexity and edge saturations. In: LICS. pp. 1\u201313. IEEE (2023). https:\/\/doi.org\/10.1109\/LICS56636.2023.10175811","DOI":"10.1109\/LICS56636.2023.10175811"},{"key":"24_CR37","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: On the finite variable-occurrence fragment of the calculus of relations with bounded dot-dagger alternation. In: MFCS. LIPIcs, vol.\u00a0272, p. 69:1\u201369:15. Schloss Dagstuhl (2023). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2023.69","DOI":"10.4230\/LIPIcs.MFCS.2023.69"},{"key":"24_CR38","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: Undecidability of the positive calculus of relations with transitive closure and difference: Hypothesis elimination using graph loops. In: RAMICS. LNTCS, vol. 14787, pp. 207\u2013224. Springer (2024). https:\/\/doi.org\/10.1007\/978-3-031-68279-7_13","DOI":"10.1007\/978-3-031-68279-7_13"},{"key":"24_CR39","doi-asserted-by":"crossref","unstructured":"Nakamura, Y.: Derivatives on graphs for the positive calculus of relations with transitive closure. Logical Methods in Computer Science Volume 21, Issue 4 (2025), https:\/\/lmcs.episciences.org\/17069","DOI":"10.46298\/lmcs-21(4:27)2025"},{"key":"24_CR40","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: Finite relational semantics for language Kleene algebra with complement. In: CSL. LIPIcs, vol.\u00a0326, pp. 37:1\u201337:23. Schloss Dagstuhl (2025). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2025.37","DOI":"10.4230\/LIPIcs.CSL.2025.37"},{"key":"24_CR41","unstructured":"Nakamura, Y.: Undecidability of the emptiness problem of deterministic propositional while programs with graph loop: Hypothesis elimination using loops (2025), http:\/\/arxiv.org\/abs\/2504.20415v1"},{"key":"24_CR42","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: A complete propositional dynamic logic for regular expressions with lookahead (2026). https:\/\/doi.org\/10.48550\/arXiv.2601.15214","DOI":"10.48550\/arXiv.2601.15214"},{"key":"24_CR43","unstructured":"Palm, A.: Propositional tense logic for finite trees. In: MOL 6, 6th Biennial Conference on Mathematics of Language (1999), https:\/\/citeseerx.ist.psu.edu\/document? doi=934688af7e9150b78a0e1035ccef8c4b95a05e94"},{"key":"24_CR44","doi-asserted-by":"publisher","unstructured":"Parikh, R.: The completeness of propositional dynamic logic. In: MFCS. LNCS, vol.\u00a064, pp. 403\u2013415. Springer (1978). https:\/\/doi.org\/10.1007\/3-540-08921-7_88","DOI":"10.1007\/3-540-08921-7_88"},{"key":"24_CR45","doi-asserted-by":"publisher","unstructured":"Sedl\u00e1r, I.: On the complexity of Kleene algebra with domain. In: RAMICS. LNCS, vol. 13896, pp. 208\u2013223. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-28083-2_13","DOI":"10.1007\/978-3-031-28083-2_13"},{"key":"24_CR46","unstructured":"Segerberg, K.: An Essay in Classical Modal Logic. Ph.D. thesis, Uppsala universitet (1971)"},{"key":"24_CR47","doi-asserted-by":"publisher","unstructured":"Segerberg, K.: A completeness theorem in the modal logic of programs. Banach Center Publications 9, 31\u201346 (1982). https:\/\/doi.org\/10.4064\/-9-1-31-46","DOI":"10.4064\/-9-1-31-46"},{"key":"24_CR48","unstructured":"Spaan, E.: Complexity of Modal Logics. Ph.D. thesis, University of Amsterdam (1993), https:\/\/eprints.illc.uva.nl\/id\/eprint\/1846\/"},{"key":"24_CR49","doi-asserted-by":"publisher","unstructured":"Stockmeyer, L., Meyer, A.: Word problems requiring exponential time (preliminary report). In: STOC. pp.\u00a01\u20139. ACM (1973). https:\/\/doi.org\/10.1145\/800125.804029","DOI":"10.1145\/800125.804029"},{"key":"24_CR50","doi-asserted-by":"publisher","unstructured":"Uezato, Y.: Regular expressions with backreferences and lookaheads capture NLOG. In: ICALP. LIPIcs, vol.\u00a0297, pp. 155:1\u2013155:20. Schloss Dagstuhl (2024). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2024.155","DOI":"10.4230\/LIPIcs.ICALP.2024.155"},{"key":"24_CR51","doi-asserted-by":"publisher","unstructured":"Vardi, M., Wolper, P.: Automata-theoretic techniques for modal logics of programs. Journal of Computer and System Sciences 32(2), 183\u2013221 (1986). https:\/\/doi.org\/10.1016\/0022-0000(86)90026-7","DOI":"10.1016\/0022-0000(86)90026-7"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-22730-0_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T16:24:24Z","timestamp":1776270264000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-22730-0_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032227294","9783032227300"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-22730-0_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"15 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Turin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2026\/conferences\/fossacs\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}