Talk:Mildly context-sensitive grammar formalism

Linguistics Mid‑importance

	Linguistics portal This article is within the scope of WikiProject Linguistics, a collaborative effort to improve the coverage of linguistics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.LinguisticsWikipedia:WikiProject LinguisticsTemplate:WikiProject LinguisticsLinguistics
Mid	This article has been rated as Mid-importance on the project's importance scale.

Computer science Mid‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Weir[d]

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

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)[reply]

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)[reply]

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)[reply]