{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:18:54Z","timestamp":1760242734282,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2016,5,11]],"date-time":"2016-05-11T00:00:00Z","timestamp":1462924800000},"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":["621-2011-6080"],"award-info":[{"award-number":["621-2011-6080"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Parsing for mildly context-sensitive language formalisms is an important area within natural language processing. While the complexity of the parsing problem for some such formalisms is known to be polynomial, this is not the case for all of them. This article presents a series of results regarding the complexity of parsing for linear context-free rewriting systems and deterministic tree-walking transducers. We discuss the difference between uniform and nonuniform complexity measures and how parameterized complexity theory can be used to investigate how different aspects of the formalisms influence how hard the parsing problem is. The main results we survey are all hardness results and indicate that parsing is hard even for relatively small values of parameters such as rank and fan-out in a rewriting system.<\/jats:p>","DOI":"10.3390\/a9020032","type":"journal-article","created":{"date-parts":[[2016,5,11]],"date-time":"2016-05-11T10:53:59Z","timestamp":1462964039000},"page":"32","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Uniform vs. Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey"],"prefix":"10.3390","volume":"9","author":[{"given":"Henrik","family":"Bj\u00f6rklund","sequence":"first","affiliation":[{"name":"Department of Computing Science, Ume\u00e5 University, SE-901 87 Ume\u00e5, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Berglund","sequence":"additional","affiliation":[{"name":"Department of Computing Science, Ume\u00e5 University, SE-901 87 Ume\u00e5, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petter","family":"Ericson","sequence":"additional","affiliation":[{"name":"Department of Computing Science, Ume\u00e5 University, SE-901 87 Ume\u00e5, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,5,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1109\/TIT.1956.1056813","article-title":"Three models for the description of language","volume":"2","author":"Chomsky","year":"1956","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref_2","unstructured":"Hopcroft, J.E., and Ullman, J.D. (1979). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley."},{"key":"ref_3","unstructured":"Joshi, A.K. (1985). Natural Language Parsing, Cambridge University Press."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/BF01191624","article-title":"The equivalence of four extensions of context-free grammars","volume":"27","author":"Weir","year":"1994","journal-title":"Math. Syst. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1162\/COLI_a_00219","article-title":"Lexicalization and generative power in CCG","volume":"41","author":"Kuhlmann","year":"2015","journal-title":"Comput. Linguist."},{"key":"ref_6","unstructured":"Weir, D.J. (1988). Characterizing Mildly Context-Sensitive Grammar Formalisms. [Ph.D. Thesis, University of Pennsylvania]."},{"key":"ref_7","unstructured":"Joshi, A.K. (1987). Mathematics of Language, John Benjamins Publishing Company."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Vijay-Shanker, K., Weir, D.J., and Joshi, A.K. (1987, January 6\u20139). Characterizing structural descriptions produced by various grammatical formalisms. Proceedings of the 25th Meeting of the Association for Computational Linguists (ACL\u201987), Stanford, CA, USA.","DOI":"10.3115\/981175.981190"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(91)90374-B","article-title":"On multiple contex-free grammars","volume":"88","author":"Seki","year":"1991","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/S0019-9958(71)90706-6","article-title":"Translations on a context-free grammar","volume":"19","author":"Aho","year":"1971","journal-title":"Inf. Control"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1016\/0022-0000(91)90018-Z","article-title":"The string generating power of context-free hypergraph grammars","volume":"43","author":"Engelfriet","year":"1991","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(80)90058-6","article-title":"Tree transducers, L systems, and two-way machines","volume":"20","author":"Engelfriet","year":"1980","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Weir, D.J. (1992, January 2\u20137). Linear contex-free rewriting systems and deterministic tree-walking transducers. Proceedings of the 30th Meeting of the Association for Computational Linguists (ACL\u201992), Newark, DE, USA.","DOI":"10.3115\/981967.981985"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1006\/jcss.1997.1515","article-title":"Trading independent for synchronized parallelism in finite copying parallel rewriting systems","volume":"56","author":"Satta","year":"1998","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Burden, H., and Ljungl\u00f6f, P. (2005, January 9\u201310). Parsing linear context-free rewriting systems. Proceedings of the 9th International Workshop on Parsing Technologies, Vancouver, BC, Canada.","DOI":"10.3115\/1654494.1654496"},{"key":"ref_16","unstructured":"Boullier, P. (2004). New Developments in Parsing Technology, Kluwer Academic Publishers."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Kallmeyer, L. (2010). Parsing Beyond Context-Free Grammars, Springer.","DOI":"10.1007\/978-3-642-14846-0"},{"key":"ref_18","first-page":"78","article-title":"The universal recognition problem for multiple context-free grammars and for Linear context-free rewriting systems","volume":"75","author":"Kaji","year":"1992","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Satta, G. (1992, January 2\u20137). Recognition of linear context-free rewriting systems. Proceedings of the 30th Annual Meeting of the Association for Computational Linguistics (ACL\u201992), Newark, DE, USA.","DOI":"10.3115\/981967.981979"},{"key":"ref_20","unstructured":"Boja\u0144czyk, M. (2008, January 13\u201319). Tree-walking automata. Proceedings of the Second International Conference on Language and Automata Theory and Applications (LATA\u201908), Tarragona, Spain."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (1999). Parameterized Complexity, Springer-Verlag.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref_22","unstructured":"Flum, J., and Grohe, M. (2006). Parameterized Complexity Theory, Springer-Verlag."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Kuhlmann, M. (2010). Dependency Structures and Lexicalized Grammars: An Algebraic Approach, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-642-14568-1"},{"key":"ref_24","unstructured":"Berglund, M., Bj\u00f6rklund, H., and Drewes, F. (2013, January 9). On the parameterized complexity of linear context-free rewriting systems. Proceedings of the Mathematics of Language (MOL\u201913), Sofia, Bulgaria."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","article-title":"Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE-analogues","volume":"73","author":"Abrahamson","year":"1995","journal-title":"Ann. Pure Appl. Logic"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Abrahamson, K.A., Downey, R.G., and Fellows, M.R. (1993, January 25\u201327). Fixed-parameter intractability II (Extended abstract). Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201993), W\u00fcrzburg, Germany.","DOI":"10.1007\/3-540-56503-5_38"},{"key":"ref_27","unstructured":"Pietrzak, K. (2003). A conjecture on the parameterized hierarchy. Notes on a talk given at Dagstuhl Seminar 03311, Unpublished work."},{"key":"ref_28","unstructured":"Bj\u00f6rklund, H., and Ericson, P. (2013, January 13\u201314). A note on the complexity of deterministic tree-walking transducers. Proceedings of the Non-Classical Models of Automata and Applications (NCMA\u201913), Umea, Sweden."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/2\/32\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:23:40Z","timestamp":1760210620000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/2\/32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,11]]},"references-count":28,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2016,6]]}},"alternative-id":["a9020032"],"URL":"https:\/\/doi.org\/10.3390\/a9020032","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2016,5,11]]}}}