Talk:Mildly context-sensitive language

	This article is within the scope of WikiProject Cognitive science, a project which is currently considered to be inactive.Cognitive scienceWikipedia:WikiProject Cognitive scienceTemplate:WikiProject Cognitive scienceCognitive science articles
???	This article has not yet received a rating on Wikipedia's content assessment scale.

EPDA's, TA's, etc.

The first two of these grammar classes define the same set of languages, while the rest define a single, strictly smaller class;

...

The larger of the classes described above may be parsed by thread automatons, while the smaller one may be parsed by embedded pushdown automatons.

Is there a paper(s) we can cite for these two statements? Thanks. –jonsafari (talk) 17:29, 21 November 2007 (UTC)[reply]

I believe I got the result from one of Kallmeyer's lecture notes linked at the bottom of the page. She would probably have repeated the claim in her papers too, if you want something formally published. Ben Standeven (talk) 04:42, 15 February 2008 (UTC)[reply]

As proven by Vijay-Shanker and Weir (1994) the following formalisms are weakly equivalent and can express the same set of languages: Linear indexed grammars, Combinatory categorial grammars, Tree-adjoining grammar, and Head grammars (!). So why are head grammars in another class? -- JakobVoss (talk) 08:47, 19 April 2011 (UTC)[reply]

Do linear indexed grammars accept exactly the mildly context-sensitive languages?

This article states, "While all languages in both classes are mildly context-sensitive and both classes support some cross-serial dependency, neither class exhausts the full set of mildly context-sensitive languages". However, the article on Indexed grammars states, "He [Gerald Gazdar] showed that this new class of grammars [the linear indexed grammars] defines a strictly smaller class of languages, the mildly context sensitive languages". So the former states that the linear indexed grammars do not include all mildly context-sensitive languages, while the latter states that the linear indexed grammars do include all mildly context-sensitive languages. Which is true? J. Finkelstein (talk) 17:54, 19 January 2012 (UTC)[reply]

The class of languages generated by linear indexed grammars is a proper subset of the maximal (largest possible) mildly context-sensitive set of languages. I've changed the statement in the indexed grammar article. Tim Smith (talk) 21:18, 30 May 2013 (UTC)[reply]

Improvements

I think there are a number of ways in which this article can be improved.

Most importantly, I think that the article should avoid creating the impression that there is a generally agreed upon formal definition of ‘mild context-sensitivity’. The definition given in the current version of the article (taken from Kallmeyer^[1]) is debatable on a number of points. For instance, I think I am not the only one who thinks that cross-serial dependencies and the copy language are not exactly the same thing.

Another issue that I take with the definition is that it attributes ‘mild context-sensitivity’ to classes of languages, whereas the original characterization by Joshi^[2] attributes it to classes of grammars. This is an important difference; for example, it leads to a different meaning of polynomial parsing, which would refer to the problem where one takes a grammar and a string as input and has to decide whether the string is generated by the grammar. This problem is arguably more relevant for computational linguistics than the language membership problem, because the specific syntactic structure that a grammar assigns to a sentence is more important than the yes/no question about the language membership.

More generally, I would like to see the article making it more clear that ‘mild context-sensitivity’ is, in many ways, a rather fuzzy and informal concept. Joshi recognized this when he wrote that his only aim was to provide a ‘rough characterization’ – not a formal definition.

I have added a draft of some new paragraphs about mild context-sensitivity to my sandbox. I would be happy if those who feel in charge of this article could have a look at it and see whether they want to use any of the material there.

Thanks for taking the time!

^ Laura Kallmeyer. Parsing Beyond Context-Free Grammars. Springer, 2010.
^ Aravind K. Joshi. Tree Adjoining Grammars: How Much Context-Sensitivity Is Required to Provide Reasonable Structural Descriptions?. In David R. Dowty, Lauri Karttunen, and Arnold M. Zwicky, editors, Natural Language Parsing, pages 206–250. Cambridge University Press, 1985.

Man in the Hollow (talk) 13:57, 25 July 2014 (UTC)[reply]

Thanks for your input! Yes, Joshi's original characterization of mild context-sensitivity was "rough", while Kallmeyer's is precise. Joshi attributes it to classes of grammars (actually he notes that his "conditions 1 and 3 depend on the grammars, while condition 2 depends on the languages"), while Kallmeyer defines it for classes of languages. Given these differences, I think we should try to cover both perspectives. It would be good to merge your sandbox article (which is closer to Joshi) with the current article (which follows Kallmeyer) in a way which preserves the material relevant to each view. The merged article could then be moved to the common title mildly context-sensitive, and mildly context-sensitive language and mildly context-sensitive grammar could redirect to it. Tim Smith (talk) 08:25, 27 July 2014 (UTC)[reply]

Sounds like a plan. If I do not hear any objections, I will try to draft a new version in a week or so. Man in the Hollow (talk) 18:47, 2 August 2014 (UTC)[reply]

I have now made the proposed changes and set up the redirects. Given that the naming conventions prefer nouns over adjectives, I have decided to create the new article as Mildly context-sensitive grammar formalism, but mention both mildly context-sensitive grammars and mildly context-sensitive languages. Man in the Hollow (talk) 20:23, 17 August 2014 (UTC)[reply]

I think there are maybe three interesting classes on the table at the moment, which are in MCFG terms, and going from smallest to largest, the well-nested MCFGs of dimension 2, well-nested MCFGs, and all MCFGs.

Aclark17 (talk) 15:25, 3 August 2014 (UTC)[reply]

Thanks Alex, I have tried to make that a bit more clear in the new article, but feel free to rewrite! Man in the Hollow (talk) 20:23, 17 August 2014 (UTC)[reply]

I was taken by surprise by this. I have left some comments about the new article on the new talk page. Let's continue there. JMP EAX (talk) 22:21, 17 August 2014 (UTC)[reply]

[1] Laura Kallmeyer. Parsing Beyond Context-Free Grammars. Springer, 2010.

[2] Aravind K. Joshi. Tree Adjoining Grammars: How Much Context-Sensitivity Is Required to Provide Reasonable Structural Descriptions?. In David R. Dowty, Lauri Karttunen, and Arnold M. Zwicky, editors, Natural Language Parsing, pages 206–250. Cambridge University Press, 1985.

[1]

[2]