{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T04:46:02Z","timestamp":1782535562930,"version":"3.54.5"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032297297","type":"print"},{"value":"9783032297303","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-29730-3_1","type":"book-chapter","created":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T04:06:55Z","timestamp":1782533215000},"page":"3-24","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["LR-Based Parsing of\u00a0Hypergraph Languages: A\u00a0Positional Grammar Approach"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3816-7765","authenticated-orcid":false,"given":"Gennaro","family":"Costagliola","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6922-5529","authenticated-orcid":false,"given":"Mattia","family":"De Rosa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4978-4307","authenticated-orcid":false,"given":"Salvatore","family":"La Torre","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,28]]},"reference":[{"key":"1_CR1","volume-title":"Implementing Domain-Specific Languages with Xtext and Xtend","author":"L Bettini","year":"2016","unstructured":"Bettini, L.: Implementing Domain-Specific Languages with Xtext and Xtend, 2nd edn. Packt Publishing, Birmingham (2016)","edition":"2"},{"key":"1_CR2","unstructured":"Chiang, D., Andreas, J., Bauer, D., Hermann, K.M., Jones, B., Knight, K.: Parsing graphs with hyperedge replacement grammars. In: Proceedings of the 51st Annual Meeting of the ACL (Volume 1: Long Papers), pp. 924\u2013932 (2013). https:\/\/aclanthology.org\/P13-1091\/"},{"key":"1_CR3","unstructured":"Chimes, M., Iosif, R., Zuleger, F.: Tree-verifiable graph grammars (2024). https:\/\/arxiv.org\/abs\/2402.17015"},{"key":"1_CR4","doi-asserted-by":"publisher","unstructured":"Costagliola, G.: Extended positional grammars: a formalism for describing and parsing visual languages. In: Ferri, F. (ed.) Visual Languages for Interactive Computing, pp. 102\u2013116. IGI Global (2008). https:\/\/doi.org\/10.4018\/978-1-59904-534-4.ch005","DOI":"10.4018\/978-1-59904-534-4.ch005"},{"key":"1_CR5","doi-asserted-by":"publisher","unstructured":"Costagliola, G., Chang, S.K.: DR parsers: a generalization of LR parsers. In: Proceedings of the 1990 IEEE Workshop on Visual Languages (1990). https:\/\/doi.org\/10.1109\/WVL.1990.128401","DOI":"10.1109\/WVL.1990.128401"},{"key":"1_CR6","unstructured":"Costagliola, G., Chang, S.K.: Parsing 2D languages with positional grammars. In: Proceedings of the 2nd Int. Workshop on Parsing Technologies, pp. 235\u2013243 (1991)"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1006926614934","volume":"2","author":"G Costagliola","year":"1999","unstructured":"Costagliola, G., Chang, S.K.: Using linear positional grammars for the LR parsing of 2-D symbolic languages. Grammars 2, 1\u201334 (1999)","journal-title":"Grammars"},{"issue":"12","key":"1_CR8","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1109\/32.637392","volume":"23","author":"G Costagliola","year":"1997","unstructured":"Costagliola, G., De Lucia, A., Orefice, S., Tortora, G.: A parsing methodology for the implementation of visual systems. IEEE Trans. Softw. Eng. 23(12), 777\u2013799 (1997). https:\/\/doi.org\/10.1109\/32.637392","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"12","key":"1_CR9","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1109\/32.637392","volume":"23","author":"G Costagliola","year":"1997","unstructured":"Costagliola, G., De Lucia, A., Orefice, S., Tortora, G.: A parsing methodology for the implementation of visual systems. IEEE Trans. Softw. Eng. 23(12), 777\u2013799 (1997). https:\/\/doi.org\/10.1109\/32.637392","journal-title":"IEEE Trans. Softw. Eng."},{"key":"1_CR10","doi-asserted-by":"publisher","unstructured":"Costagliola, G., De Lucia, A., Orefice, S., Tortora, G.: Positional grammars: a formalism for LR-like parsing of visual languages. In: Marriott, K., Meyer, B. (eds.) Visual Language Theory, pp. 171\u2013191. Springer (1998). https:\/\/doi.org\/10.1007\/978-1-4612-1676-6_5","DOI":"10.1007\/978-1-4612-1676-6_5"},{"key":"1_CR11","unstructured":"Costagliola, G., Deufemia, V.: Visual language editors based on LR parsing techniques. In: Proceedings of the 8th International Conference on Parsing Technologies, pp. 78\u201390 (2003)"},{"key":"1_CR12","doi-asserted-by":"publisher","unstructured":"Costagliola, G., Deufemia, V., Ferrucci, F., Gravino, C.: On the PLR parsability of visual languages. In: Proceedings IEEE Symposium on Human-Centric Computing Languages and Environments. pp. 48\u201351. IEEE (2001). https:\/\/doi.org\/10.1109\/HCC.2001.995234","DOI":"10.1109\/HCC.2001.995234"},{"key":"1_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.cola.2020.100943","volume":"57","author":"G Costagliola","year":"2020","unstructured":"Costagliola, G., Deufemia, V., Ferrucci, F., Gravino, C.: Run-time conflict detection in visual language parsing. J. Comput. Lang. 57, 100943 (2020). https:\/\/doi.org\/10.1016\/j.cola.2020.100943","journal-title":"J. Comput. Lang."},{"issue":"6","key":"1_CR14","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1016\/j.jvlc.2005.06.001","volume":"16","author":"G Costagliola","year":"2005","unstructured":"Costagliola, G., Deufemia, V., Polese, G., Risi, M.: Building syntax-aware editors for visual languages. J. Visual Lang. Comput. 16(6), 508\u2013540 (2005). https:\/\/doi.org\/10.1016\/j.jvlc.2005.06.001","journal-title":"J. Visual Lang. Comput."},{"issue":"3","key":"1_CR15","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1109\/2.366162","volume":"28","author":"G Costagliola","year":"1995","unstructured":"Costagliola, G., Tortora, G., Orefice, S., De Lucia, A.: Automatic generation of visual programming environments. IEEE Comput. 28(3), 56\u201366 (1995). https:\/\/doi.org\/10.1109\/2.366162","journal-title":"IEEE Comput."},{"issue":"4","key":"1_CR16","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/1040291.1040293","volume":"13","author":"G Costagliola","year":"2004","unstructured":"Costagliola, G., Deufemia, V., Polese, G.: A framework for modeling and implementing visual notations with applications to software engineering. ACM Trans. Softw. Eng. Methodol. 13(4), 431\u2013487 (2004). https:\/\/doi.org\/10.1145\/1040291.1040293","journal-title":"ACM Trans. Softw. Eng. Methodol."},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4204\/eptcs.440.1","volume":"440","author":"G Costagliola","year":"2026","unstructured":"Costagliola, G., Vastarini, F.: Parsing hypergraphs using context-free positional grammars. Electron. Proc. Theoretic. Comput. Sci. 440, 1\u20135 (2026). https:\/\/doi.org\/10.4204\/eptcs.440.1","journal-title":"Electron. Proc. Theoretic. Comput. Sci."},{"key":"1_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic \u2013 A Language-Theoretic Approach","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic \u2013 A Language-Theoretic Approach. Cambridge Univ, Press (2012)"},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0304-3975(93)90065-2","volume":"109","author":"F Drewes","year":"1993","unstructured":"Drewes, F.: Recognising $$k$$-connected hypergraphs in cubic time. Theoret. Comput. Sci. 109, 83\u2013122 (1993). https:\/\/doi.org\/10.1016\/0304-3975(93)90065-2","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1_CR20","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1162\/coli_a_00488","volume":"49","author":"F Drewes","year":"2023","unstructured":"Drewes, F., Bj\u00f6rklund, H., Ericson, J.: Generation and polynomial parsing of graph languages with non-structural reentrancies. Comput. Linguist. 49(4), 841\u2013880 (2023). https:\/\/doi.org\/10.1162\/coli_a_00488","journal-title":"Comput. Linguist."},{"key":"1_CR21","doi-asserted-by":"publisher","unstructured":"Drewes, F., Habel, A., Kreowski, H.J.: Hyperedge replacement graph grammars. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation, vol. I, pp. 95\u2013162. World Scientific (1997) . https:\/\/doi.org\/10.1142\/9789812384720_0002","DOI":"10.1142\/9789812384720_0002"},{"key":"1_CR22","doi-asserted-by":"publisher","unstructured":"Drewes, F., Hoffmann, B., Minas, M.: Predictive top-down parsing for hyperedge replacement grammars. In: Parisi-Presicce, F., Westfechtel, B. (eds.) ICGT 2015. LNCS, vol. 9151, pp. 19\u201334. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21145-9_2","DOI":"10.1007\/978-3-319-21145-9_2"},{"key":"1_CR23","doi-asserted-by":"publisher","unstructured":"Drewes, F., Hoffmann, B., Minas, M.: Predictive shift-reduce parsing for hyperedge replacement grammars. In: de Lara, J., Plump, D. (eds.) ICGT 2017. LNCS, vol. 10373, pp. 106\u2013122. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-61470-0_7","DOI":"10.1007\/978-3-319-61470-0_7"},{"key":"1_CR24","doi-asserted-by":"publisher","unstructured":"Drewes, F., Hoffmann, B., Minas, M.: Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement. J. Logic. Algebraic Methods Program. 104, 303\u2013341 (2019). https:\/\/doi.org\/10.1016\/j.jlamp.2018.12.006","DOI":"10.1016\/j.jlamp.2018.12.006"},{"key":"1_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114763","volume":"1015","author":"F Drewes","year":"2024","unstructured":"Drewes, F., Stade, Y.: On the power of local graph expansion grammars with and without additional restrictions. Theoret. Comput. Sci. 1015, 114763 (2024). https:\/\/doi.org\/10.1016\/j.tcs.2024.114763","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR26","doi-asserted-by":"publisher","unstructured":"Gilroy, S., Lopez, A., Maneth, S.: Parsing graphs with regular graph grammars. In: Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (*SEM 2017), pp. 199\u2013208. Association for Computational Linguistics (2017). https:\/\/doi.org\/10.18653\/v1\/S17-1024","DOI":"10.18653\/v1\/S17-1024"},{"key":"1_CR27","unstructured":"Habel, A.: Hyperedge Replacement: Grammars and Languages, LNCS, vol. 643. Springer (1992)"},{"key":"1_CR28","doi-asserted-by":"publisher","unstructured":"Hoffmann, B., Minas, M.: Generating efficient predictive shift-reduce parsers for hyperedge replacement grammars. In: Seidl, M., Zschaler, S. (eds.) STAF 2017. LNCS, vol. 10748, pp. 76\u201391. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-74730-9_7","DOI":"10.1007\/978-3-319-74730-9_7"},{"key":"1_CR29","doi-asserted-by":"publisher","unstructured":"Hoffmann, B., Minas, M.: Generalized predictive shift-reduce parsing for hyperedge replacement graph grammars. In: Mart\u00edn-Vide, C., Okhotin, A., Shapira, D. (eds.) LATA 2019. LNCS, vol. 11417, pp. 233\u2013245. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-13435-8_17","DOI":"10.1007\/978-3-030-13435-8_17"},{"key":"1_CR30","unstructured":"Johnson, S.C.: YACC: yet another compiler-compiler. Tech. Rep. Computing Science Technical Report 32, Bell Laboratories, Murray Hill, NJ, USA (1975)"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/BF00289017","volume":"27","author":"C Lautemann","year":"1990","unstructured":"Lautemann, C.: The complexity of graph languages generated by hyperedge replacement. Acta Informatica 27, 399\u2013421 (1990). https:\/\/doi.org\/10.1007\/BF00289017","journal-title":"Acta Informatica"},{"key":"1_CR32","doi-asserted-by":"publisher","unstructured":"McPeak, S., Necula, G.C.: Elkhound: a fast, practical GLR parser generator. In: Duesterwald, E. (ed.) CC 2004. LNCS, vol. 2985, pp. 73\u201388. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24723-4_6","DOI":"10.1007\/978-3-540-24723-4_6"},{"key":"1_CR33","unstructured":"Piscitelli, A.: Multidimensional languages, a grammar specification for the definition of multidimensional languages. Master\u2019s thesis, Universit\u00e0 di Salerno, Fisciano (SA), Italia (2019). https:\/\/alfy91.github.io\/files\/master-thesis.pdf. Accessed 27 April 2026"},{"key":"1_CR34","unstructured":"Reccia, L.: A formal grammar definition to describe Multidimensional Languages. Master\u2019s thesis, Universit\u00e0 di Salerno, Fisciano (SA), Italia (2020). https:\/\/cluelab.di.unisa.it\/old\/images\/stories\/papers\/reccia_thesis.pdf. Accessed 27 April 2026"},{"key":"1_CR35","doi-asserted-by":"publisher","unstructured":"Riedl, M., Seifert, S., Fischer, I.: String generating hypergraph grammars with word order restrictions. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L., Rozenberg, G. (eds.) ICGT 2006. LNCS, vol. 4178, pp. 138\u2013152. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11841883_11","DOI":"10.1007\/11841883_11"},{"key":"1_CR36","doi-asserted-by":"publisher","unstructured":"Seifert, S., Fischer, I.: Parsing string generating hypergraph grammars. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT 2004. LNCS, vol. 3256, pp. 352\u2013367. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30203-2_25","DOI":"10.1007\/978-3-540-30203-2_25"},{"key":"1_CR37","doi-asserted-by":"publisher","unstructured":"Vogler, W.: Recognizing edge replacement graph languages in cubic time. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) Graph Grammars 1990. LNCS, vol. 532, pp. 676\u2013687. Springer, Heidelberg (1991). https:\/\/doi.org\/10.1007\/BFb0017421","DOI":"10.1007\/BFb0017421"}],"container-title":["Lecture Notes in Computer Science","Graph Transformation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-29730-3_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T04:06:57Z","timestamp":1782533217000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-29730-3_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032297297","9783032297303"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-29730-3_1","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":"28 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"ICGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Graph Transformation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rennes","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","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":"1 July 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"icgt2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conf.researchr.org\/home\/icgt-2026","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}