Is the commutative CFG in the mathematical linguistics literature?

Question

I am shocked that Linguists have not given a reasonably small canonical computationally precise representation of any natural language yet, so I wrote a recent EL&U post to explain how one does this for English. I know that this grammar (or a small modification if I forgot something) covers all New York Times English, and all artificial highly embedded sentences, leaving out only:

• Idioms and weird constructions: "How do you do?", "hello, dear.", "Okeh, oops!", etc
• Tense-matching: this is a local finite property, and it doesn't touch the embedding structure. It is a distracting complication. I ignored it.
• Subject-verb matching: again not difficult, but distracting.
• Pronoun-reference: "With a broom, John walked on the floor, beating it.", what does "it" refer to? This is a very interesting linguistic question which I ignore.
• General "and" and "or": The and rules are cut-and-paste for different kinds of objects, debugging (ADVERB "and" ADVERB), (ADJECTIVE and ADJECTIVE), (PREPISH and PREPISH), etc, is tedious, so I skipped this.
• Verb ellipsis: I am not sure when this appears in the NYT, I have not seen an example yet. Verb ellipses can be implemented on the parser level, but at the rule level it's very annoying.

The central possibly new idea that I used is the notion of a commutative context-free grammar. A commutative context-free grammar allows a string of nonterminals to move to different positions in the sentence before expanding. I will illustrate with a sentence with two movable ADVERB phrases, a subject and a verb. At some stage in the generation, it looks like this:

ADVERB+ ADVERB+ ADVERB+ (SUBJECT) (VERB OBJECT)

In the next stages, I can move ADVERB+ to the right, so long as I don't go inside regions enclosed by parentheses. So I might get

ADVERB+ (the ADJ[] man ) ADVERB+ (takes the box) ADVERB+

The ADVERB is a production that includes anything that attaches to the verb, including "if" clauses, initial "yes"/"no", and prepositional phrases that modify the action, as opposed to modifying the noun. At a later stage of production, the ADVERBs resolve to verb arguments, adverb words, or gerund phrases. So in a few steps, you get

With a broom (the tall man) to the big monster (takes the box) with a limp.

Then you drop parentheses and introduce commas as conventional, to get:

With a broom, the tall man, to the big monster takes the box, with a limp.

The point of this structure is to capture the commutativity of ADVERB position in a phrase. These really can appear anywhere, and often do in poetic work, although there are style conventions in English which tends to place them at canonical positions.

This idea produces a very compact BNF for the phrase structure of English, and explains why other methods don't. The commutativity produces a large number of different nodes if you ignore it. I will point out that the parse description that this generates for the sentence is the same in all permutation of the ADVERBs. It's still a parse tree abstractly, but the tree is not contiguously represented in the sentence. Some arguments far away are bound to distant objects.

There is always a position for the ADVERBs (after the verb) where if you force the writer to place them all there, the grammar becomes context free. If you restrict the ADVERBs to the very beginning too, you can also make it context free while still producing the ADVERBs from the verb, using the following trick:

define a single nonterminal symbol: ADVERBLIST_SUBJECT_VERB_ADVERBLIST, and have context free rules that spit out ADVERBs on both sides, then when you are done spitting out ADVERBs, break it into SUBJECT ADVERBLIST_VERB_ADVERBLIST, then spit out ADVERBs on both sides, then resolve ADVERBLIST_VERB_ADVERBLIST into a VERB. This allows you to artificially remove commutativity, at the cost of introducing more parse levels into the grammar. If you do it wrong, you can easily introduce new parsing ambiguity that isn't there in the original sentence.

Aside from being counterintuitive, a context-free reduction doesn't match the arguments to the verb the correct way, which is independent of their position, this trick also doesn't work in general. If you have two separate commutative lists, a list of ADJECTIVES and ADVERBs, these can commute past each other, so that if you force the grammar to be context free, you requiring an ever-growing number of nonterminals to represent the different permutations. You can probably parse all the New York Times with only a few permutations, since good style places the ADJECTIVE close to the noun it modifies, but this commutativity leads a combinatorial explosion in the representation of English that suggests that the reason is that the commutative grammar is not context free.

Formal Description

While one can define commutative grammars in extreme generality, I will restrict myself to the ones useful in English. The primitive commutation rule is a production of the form:

A+ B: B A+

And likewise for all + marked variables with all unplussed variables. This allows the plus variables to move rightward, and I place them at the leftmost position they can occur.

This production is not context free, it takes two objects to two other objects in the other order. But it isn't going hog-wild either--- the number and type of nonterminal symbols is preserved during this transformation--- it doesn't wreck the tree structure completely, it only permutes the order of the nonterminals, and the moment you expand "B" into something in parentheses, say:

B: (P Q)

Then A no longer is allowed to commute with P and Q. So the commutativity is at each nesting level individually.

I define a language to be commutative context-free if all comutative objects can be generated, commuted, and resolved into unplussed-variables before any other rules are applied. Further, I will only allow them to move in one direction, by convention to the right, since this is no loss of generality in the cases I am considering. Finally, I will require that any further expansion of nonterminals will always be enclosed in parentheses which provide a firm boundary to any commuting variables introduced at a deeper nesting level, so that objects at a lower level will never commute out of their level.

Questions

1. Is the commutative CFG in the mathematical linguistics literature?
2. Does anyone see a proof that the commutative CFG is strictly stronger than CFG (I am pretty sure this is true)?

Answer 1

Modern research into grammar formalisms have developed analyses for many of the constructions you deem to be impossible or difficult to account for.

Out of your list, 'tense matching' and 'subject-verb matching', 'pronoun-reference' (usually called anaphora resolution), 'general "and" and "or"' (coordination) have definitely been addressed in many formalisms including generative grammar, Head-driven Phrase Structure Grammar (HPSG), Combinatory Categorial Grammar (CCG), and many others. (I am not sure what you mean by verb ellipsis, but if you mean:

He baked and she ate a delicious chocolate cake.

this, too, is well-studied and well-addressed by computationally efficient methods in the literature.)

As for the extension to CFGs which you propose,

A+ B -> B A+

can (I think) be expressed in a linear indexed grammar (LIG), so you're right that the generative power required is strictly greater than context-free.

However, I'm not even sure this is a valid generalisation — not all modifiers can occur on either side of the verb phrase (at least not without changing the denotation):

I honestly believe he is a crook.

?I believe he is a crook honestly.

Frankly I don't give a damn.

*I don't give a damn frankly.

Answer 2

It was in the literature! Very recently, though. According to the citations in the paper linked below, the idea first appeared in 2009 here:

• W. Czerwinski, S. B. Fröschle & S. Lasota (2009): "Partially-Commutative Context-Free Processes." In: CONCUR, pp. 259–273, doi:10.1007/978-3-642-04081-8_18

And the description of the commutation rule for symbols, some basic theorems, were given here:

• W. Czerwinski, S. B. Fröschle & S. Lasota (2011): Partially-commutative context-free processes: expressibility and tractability. Inf. Comput. 209(5), pp. 782–798, doi:10.1016/j.ic.2010.12.003

Although I found the following free reference first.

• Wojciech Czerwinski, Sławomir Lasota, "Partially Commutative Context Free Languages" ( http://arxiv.org/pdf/1208.2747.pdf )

This free text only appeared about 6 months after this question, so my ignorance was justified.

The paper describes a formalization of the commutative context free grammer (what they name, more precisely, a "partially commutative context free grammer", but this is what is described in the body of my question. The formalization is not difficult, it is exactly by introducing two-element swap operations). The paper also reviews existing literature, and explains in detail how this differs from other ideas which are naively similar.

The straightforward definition is on page 37, it introduces the "swap operation" for independent symbols, and allows productions which swap, in addition to a standard representation of CFGs. Instead of "plussing" variables and commuting only to the right, it defines an "independent set" of variables which can be moved back and forth to any permutation. This can be more general than what I defined in the question, but it subsumes the right-moving grammars. The paper states an automaton model for the class, using multiple stacks, on page 38.

The main theorems prove that the decision procedure for general pcCFGs (partially commutative context free grammars) is NP complete, and introduces a notion of "shuffling" or "interleaving" of grammars, so that you have two different interleaved grammars going on at the same time (this was one of my own original motivation for thinking about this).

The main difference between what I suggested and the paper is that the paper has a more general class, as it is interested in full automaton theory for such languages, not just in natural language processing. The natural language processing does not require commutation beyond certain natural stopping points--- the commutation steps are only to reorder the ADVERB and ADJECTIVE phrases amongst each other, and with the NOUNPHRASE and VERBPHRASE symbol within the same verb-scope level, they never permute anything into deeper levels of the tree. With this restriction, I am sure that the decision procedure is not NP complete, since the permutation steps can be made to a canonical order level by level. But since this is of current interest, and there is something to reference, one should publish a paper, rather than just say it here.

The implication of this for natural language processing is just that you define the parse tree with commutation rules at each level, so that you can permute the adverb and adjective nodes arbitrary on any one level the tree, so long as they don't go inside deeper parts of the tree. A "level" of the tree is one where you haven't introduced a new verb, it is the collection of all things which attach to one verb.

With this additional commutativity structure, you can permute the adverbs and adjectives in any level to a standard context free form, this should not be NP complete or anything, and then parse the sentence in the usual CFG way. I am pretty sure that there are no remaining issues for a formal description of natural language grammar, as all the verified examples of the failure of CFG come from cases where a permutation on one level fixes the structure of the sentence.