{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:12:22Z","timestamp":1760145142338,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T00:00:00Z","timestamp":1718755200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"publisher","award":["2020-03852"],"award-info":[{"award-number":["2020-03852"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Knut and Alice Wallenberg Foundation","award":["2020-03852"],"award-info":[{"award-number":["2020-03852"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A regular unranked tree folding consists of a regular unranked tree language and a folding operation that merges (i.e., folds) selected nodes of a tree to form a graph; the combination is a formal device for representing graph languages. If, in the process of folding, the order among edges is discarded so that the result is an unordered graph, then two applications of a fold operation are enough to make the associated parsing problem NP-complete. However, if the order is kept, then the problem is solvable in non-uniform polynomial time. In this paper, we address the remaining case, where only one fold operation is applied, but the order among the edges is discarded. We show that, under these conditions, the problem is solvable in non-uniform polynomial time.<\/jats:p>","DOI":"10.3390\/a17060268","type":"journal-article","created":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T08:06:06Z","timestamp":1718784366000},"page":"268","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parsing Unranked Tree Languages, Folded Once"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3692-6994","authenticated-orcid":false,"given":"Martin","family":"Berglund","sequence":"first","affiliation":[{"name":"Deptartment of Computing Science, Ume\u00e5 University, 90836 Ume\u00e5, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4696-9787","authenticated-orcid":false,"given":"Henrik","family":"Bj\u00f6rklund","sequence":"additional","affiliation":[{"name":"Deptartment of Computing Science, Ume\u00e5 University, 90836 Ume\u00e5, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0596-627X","authenticated-orcid":false,"given":"Johanna","family":"Bj\u00f6rklund","sequence":"additional","affiliation":[{"name":"Deptartment of Computing Science, Ume\u00e5 University, 90836 Ume\u00e5, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,6,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Tang, L., and Liu, H. (2010). Graph mining applications to social network analysis. Managing and Mining Graph Data, Springer.","DOI":"10.1007\/978-1-4419-6045-0_16"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Plump, D. (2009). The graph programming language GP. Algebraic Informatics, Proceedings of the 3rd International Conference on Algebraic Informatics, CAI 2009, Thessaloniki, Greece, 19\u201322 May 2009, Springer.","DOI":"10.1007\/978-3-642-03564-7_6"},{"key":"ref_3","unstructured":"You, J., Leskovec, J., He, K., and Xie, S. (2020, January 13\u201318). Graph structure of neural networks. Proceedings of the International Conference on Machine Learning, PMLR, Virtual."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, H., Bj\u00f6rklund, J., and Ericson, P. (2017). On the regularity and learnability of ordered DAG languages. Implementation and Application of Automata, Proceedings of the 22nd International Conference, CIAA 2017, Marne-la-Vall\u00e9e, France, 27\u201330 June 2017, Springer.","DOI":"10.1007\/978-3-319-60134-2_3"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/BF00289017","article-title":"The complexity of graph languages generated by hyperedge replacement","volume":"27","author":"Lautemann","year":"1990","journal-title":"Acta Inform."},{"key":"ref_6","unstructured":"Quernheim, D., and Knight, K. (2012, January 23\u201325). DAGGER: A Toolkit for Automata on Directed Acyclic Graphs. Proceedings of the 10th International Workshop Finite-State Methods and Natural Language Processing, FSMNLP 2012, Donostia-San Sebastian, Spain."},{"key":"ref_7","unstructured":"Koller, A. (2015, January 14\u201317). Semantic construction with graph grammars. Proceedings of the 11th International Conference on Computational Semantics, IWCS, London, UK."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Rozenberg, G. (1997). Hyperedge Replacement Graph Grammars. Handbook of Graph Grammars and Computing by Graph Transformation, World Scientific.","DOI":"10.1142\/9789812384720"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Langkilde, I., and Knight, K. (1998, January 10\u201314). Generation That Exploits Corpus-based Statistical Knowledge. Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics (Volume 1), Montreal, QC, Canada.","DOI":"10.3115\/980845.980963"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kasper, R.T. (1989, January 21\u201323). A flexible interface for linking applications to Penman\u2019s sentence generator. Proceedings of the Workshop on Speech and Natural Language, Philadelphia, PA, USA.","DOI":"10.3115\/100964.100979"},{"key":"ref_11","unstructured":"Banarescu, L., Bonial, C., Cai, S., Georgescu, M., Griffitt, K., Hermjakob, U., Knight, K., Koehn, P., Palmer, M., and Schneider, N. (2013, January 8\u20139). Abstract Meaning Representation for Sembanking. Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse, Sofia, Bulgaria."},{"key":"ref_12","unstructured":"Braune, F., Bauer, D., and Knight, K. (2014, January 26\u201331). Mapping Between English Strings and Reentrant Semantic Graphs. Proceedings of the Ninth International Conference on Language Resources and Evaluation, LREC 2014, Reykjavik, Iceland."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of Finding Embeddings in a k-Tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"ref_14","first-page":"55","article-title":"Extending Predictive Shift-Reduce Parsing to Contextual Hyperedge Replacement Grammars","volume":"Volume 11629","author":"Guerra","year":"2019","journal-title":"Graph Transformation, Proceedings of the 12th International Conference, ICGT 2019, Eindhoven, The Netherlands, 15\u201316 July 2019"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Drewes, F., Hoffmann, B., and Minas, M. (2021). Rule-Based Top-Down Parsing for Acyclic Contextual Hyperedge Replacement Grammars. Graph Transformation, Proceedings of the 14th International Conference, ICGT 2021, Virtual Event, 24\u201325 June 2021, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-030-78946-6_9"},{"key":"ref_16","first-page":"3","article-title":"Acyclic Contextual Hyperedge Replacement: Decidability of Acyclicity and Generative Power","volume":"Volume 13349","author":"Behr","year":"2022","journal-title":"Graph Transformation, Proceedings of the 15th International Conference, ICGT 2022, Held as Part of STAF 2022, Nantes, France, 7\u20138 July 2022"},{"key":"ref_17","unstructured":"Minas, M. (2024, June 18). The Graph-Parsing Tool Grappa. Available online: https:\/\/www.unibw.de\/inf2\/grappa."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, J. (2018). Tree-to-graph transductions with scope. Developments in Language Theory, Proceedings of the 22nd International Conference, DLT 2018, Tokyo, Japan, 10\u201314 September 2018, Springer.","DOI":"10.1007\/978-3-319-98654-8_11"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"105111","DOI":"10.1016\/j.ic.2023.105111","article-title":"Transduction from trees to graphs through folding","volume":"295","author":"Berglund","year":"2023","journal-title":"Inf. Comput."},{"key":"ref_20","unstructured":"Br\u00fcggemann-Klein, A., Murata, M., and Wood, D. (2001). Regular Tree and Regular Hedge Languages over Unranked Alphabets: Version 1, The Hong Kong University of Science and Technology. Technical Report HKUST-TCSC-2001-0."},{"key":"ref_21","unstructured":"G\u00e9cseg, F., and Steinby, M. (2015). Tree Automata. arXiv."},{"key":"ref_22","first-page":"83","article-title":"Z-Automata for Compact and Direct Representation of Unranked Tree Languages","volume":"Volume 11601","author":"Drewes","year":"2019","journal-title":"Implementation and Application of Automata, Proceedings of the 24th International Conference, CIAA 2019, Ko\u0161ice, Slovakia, 22\u201325 July 2019"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Bierman, G., and Koch, C. (2005). Minimizing Tree Automata for Unranked Trees. Database Programming Languages, Proceedings of the 10th International Symposium, DBPL 2005, Trondheim, Norway, 28\u201329 August 2005, Springer.","DOI":"10.1007\/11601524"},{"key":"ref_24","unstructured":"Parikh, R. (1961). Language Generating Devices, Research Laboratory of Electronics, MIT. Technical Report."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0022-0000(69)80011-5","article-title":"Parallel program schemata","volume":"3","author":"Karp","year":"1969","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Czerwi\u0144ski, W., and Orlikowski, \u0141 (2022, January 7\u201310). Reachability in Vector Addition Systems is Ackermann-complete. Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), Denver, CO, USA.","DOI":"10.1109\/FOCS52979.2021.00120"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(77)90014-7","article-title":"Complexity of some problems in Petri nets","volume":"4","author":"Jones","year":"1977","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/6\/268\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:00:58Z","timestamp":1760108458000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/6\/268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,19]]},"references-count":27,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["a17060268"],"URL":"https:\/\/doi.org\/10.3390\/a17060268","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,6,19]]}}}