polynomial parsing if its membership problem can be solved in deterministic polynomial time. This is the problem to decide, given a grammar G written in the formalism and a string w, whether w is generated by G – that is, whether w is "grammatical" according to G. The time complexity of this problem is measured in terms of the combined size of G and w. Under the view on mild context-sensitivity as a property of classes of languages, polynomial parsing refers to the language membership problem. This is the problem to decide, for a fixed language L, whether a given string w belongs to L. The time complexity of this problem is measured in terms of the length of w; it ignores the question how L is specified. Note that both understandings of polynomial parsing are idealizations in the sense that for practical applications one is interested not only in the yes/no question whether a sentence is grammatical, but also in the syntactic structure that the grammar assigns to the sentence. Formalisms Over the years, a large number of grammar formalisms have been introduced that satisfy some or all of the characteristic properties put forth by Joshi. Several of them have alternative, automaton-based characterizations that are not discussed in this article; for example, the languages generated by tree-adjoining grammar can be characterized by embedded pushdown automata. Formalisms equivalent to TAG Tree-adjoining grammar (TAG) Head grammar (HG) Linear indexed grammar (LIG) Combinatory categorial grammar (CCG) Well-nested LCFRS/MCFG of fan-out 2 Formalisms equivalent to general LCFRS/MCFG Linear context-free rewriting systems (LCFRS) Multiple context-free grammars (MCFG) Multicomponent tree-adjoining grammars (MCTAG) Minimalist grammars (MG) Simple (linear, non-erasing, non-combinatorial), positive range concatenation grammars (sRCG) Formalisms equivalent to well-nested LCFRS/MCFG Non-duplicating macro grammars Coupled context-free grammars (CCFG) Well-nested linear context-free rewriting systems Well-nested multiple context-free grammars Relations among the formalisms Linear context-free rewriting systems/multiple context-free grammars form a two-dimensional hierarchy of generative power with respect to two grammar-specific parameters called fan-out and rank. More precisely, the languages generated by LCFRS/MCFG with fan-out and rank are properly included in the class of languages generated by LCFRS/MCFG with rank and fan-out f, as well as the class of languages generated by LCFRS/MCFG with rank r and fan-out . In the presence of well-nestedness, this hierarchy collapses to a one-dimensional hierarchy with respect to fan-out; this is because every well-nested LCFRS/MCFG can be transformed into an equivalent well-nested LCFRS/MCFG