Talk:Mildly context-sensitive grammar formalism

Comments on the new article

Joshi

The following bit from Joshi is worth quoting in full here:

“ It should be noted that the extra power of TAGs (beyond that of CFGs)

is not due to some ad hoc modification of the context-free rewriting rule, but, rather, it is the direct consequence of factoring recursion and the domains of dependencies in a particular manner, which is linguistically significant (see section 6.4 for linguistic examples). I would like to propose that the three properties 1. limited cross-serial dependencies, 2. constant growth, and 3. polynomial parsing roughly characterize a class of grammars (and associated languages) that are only slightly more powerful than context-free grammars (context-free languages). I will call these mildly context-sensitive grammars {languages), MCSGs (MCSLs). This is only a rough characterization because conditions 1 and 3 depend on the grammars, while condition 2 depends on the languages; further, condition 1 needs to be specified much more precisely than I have done so far.

”

The current article glosses over the important (IMHO) note that Joshi made about the mixed nature of the properties he put forth. JMP EAX (talk) 21:59, 17 August 2014 (UTC)

I have tried to make this point more clear in the new version of the article. Man in the Hollow (talk) 13:23, 18 August 2014 (UTC)

Kallmeyer

She stresses the point that MCS is a property of a set/class of languages. This got lost in the rewrite. Whether she's entirely right or not (Me and another editor actually had a big discussion about it at Template_talk:Formal_languages_and_grammars), I think her take on the matter is probably worth mentioning. (See also [1] amd [2]) In other words, this rewrite is not a WP:NPOV article right now, but a WP:POVFORK. JMP EAX (talk) 21:59, 17 August 2014 (UTC)

The rewrite already mentioned that ‘some authors’ define mild context-sensitivity as a property of languages. In the new version of the article I have added an explicit pointer to Kallmeyer. Man in the Hollow (talk) 13:23, 18 August 2014 (UTC)

Automata

The equivalence to various automata has disappeared in the rewrite. As annoying as I found Kallmeyer's book, she at least covers that. JMP EAX (talk) 21:59, 17 August 2014 (UTC)

I have added a note about automaton-based characterizations of mildly context-sensitive grammar formalisms, with an explicit link to embedded pushdown automata. I am aware of the fact that there are many others (including many not mentioned in the previous version of the article, such as top–down tree-to-string transducers and simple macro tree transducers under the yield mapping) but I feel that adding all these models would perhaps be a bit over the top. I explicitly removed the part about thread automata, for which it is not known (to the best of my knowledge) how to restrict them to accept exactly LCFRS. (But I maybe wrong there.) Man in the Hollow (talk) 13:23, 18 August 2014 (UTC)

Weir[d]

Weir's hierarchy has disappeared too [3]. JMP EAX (talk) 22:08, 17 August 2014 (UTC)

This was a deliberate choice. Weir’s hierarchy is typically not mentioned in connection with mild context-sensitivity. As such, the previous version of the article was unnecessarily detailed. Also, it stated that the languages in the Weir hierarchy get less and less mildly context-sensitive. Do you want to propose a new section that makes the link to the idea of mild context-sensitivity more explicit? Man in the Hollow (talk) 13:23, 18 August 2014 (UTC)

In Kallmeyer's book the Weir Hierarchy is covered (p. 199) in the context of k-Order EPDA. So it seems reasonable to merge that section there instead. JMP EAX (talk) 16:30, 18 August 2014 (UTC)

Rating

I've proposed some ratings for this article, feel free to change them if you think they are inadequate. Pintoch (talk) 16:36, 31 August 2014 (UTC)