konstantinoskokos / dyck-paper Goto Github PK

In your paper, make sure to add back the author names and affiliations.

The format should be consistent with the llncs2e package I sent earlier; if you added the svmono package, some students have pointed out this style conflicts with the llncs2e format. I've asked the publishers, and they said we should stick with the llncs2e format - no svmono.

For the overall organization of the paper, I would suggest
moving section 3 (on the computational toolkit backing up the work in
section 2) to an Appendix, and expanding the sections 1,2,4,5 along the
lines indicated below.

The link between D^2 and programming language analysis example 
is interesting, but the central motivation for studying this problem would
come from *natural language* grammars, and the proper characterization of
the required expressivity beyond context-free. MIX^3, as an abstract
representative of word-order freedom, is generally felt to be overpermissive,
and D^3, with its extra prefix constraint, would be a candidate for a
more constrained view of ordering, but this point needs elaboration:

-Are there NL patterns that, under a suitable string homomorphism, would
exemplify D^3 ? (cf the role of a^n b^n c^n or w^2 in the discussion of
crossed dependencies of Swiss German)
-Why the conjecture of D^3 as a 2-MCFL in the first place? Because
MIX_3 is a 2-MCFL (Salvati)?
-Given the prefix constraint separating D3 from MIX^3, one might be 
led to feel it might be properly included in the class of 2-MCFL,
for example being a *well-nested* 2-MCFL or TAG. If it isn't,
then explain why (using eg Kanazawa's 2009 pumping lemma for
well-nested MCFG, Kanazawa & Salvati's 2012 result that MIX^3
=/= a tree adjoining language, and their 2010 copying power
for wll-nested MCFG result).

There are many, as inspection of the Online
Encyclopedia of Integer Sequences shows. Restrict examples to
bijections that play a role for the techniques developed in
section 2. Drop constrained walks, for example.

this is a bad title for what
is the core section of the paper. Maybe "Abstract grammar
specification" or something of the kind?

- [ ] change introduce to employ (5)

The Van Wijgaarden metagrammar technique has a respectable
pedigree in linguistic description, see the separation of
LP (linear precedence) and ID (immediate dominance) in
Generalized Phrase Structure Grammars (Gazdar et.al.),
Mike Reape's work on domain union (eg 'Getting things in
order' in Bunt&vHorck, Discontinuous Constituency),
Nederhof,Shieber,Satta on Partially-ordered multiset
CFG and ID/LP parsing, etc. All these refs involving
shuffling, in addition to concatenation, in some way
or other. Please cite/discuss the relevant literature
here.

The technique of generating non-terminals to represent
incomplete word states is intriguing, especially the
connection with Petersen's rules for the generation of
combinatorial spider webs. This correspondence needs
better explanation/elaboration, though. In its present
form, readers who haven't studied combinatorial spider
webs in detail will not be able to appreciate what is
going on.

Note also that the idea of non-terminals representing
incomplete word states is what gives the standard CFG
for MIX^2 (eg Lewis & Papadimitriou, Elements ..)

Re webs: the correspondence is with a *subset* of
the growth rules - where does it fail? The rules that
combine two trivalent points? In what sense would they
be beyond the capacity of 2-MCFG rules?

rename to "Discussion"?
Given that the issue D^3=2-MCFG is not settled, it
would be nice to have some discussion here of upper/lower
demarcation bounds, and of the reasons why the successive
approximations fail in the end. As for lower bound,
settle the issue D3=/=well nested MCFG (cf above).
And if D^3=2-MCFG is elusive, what about 3-MCFG?
If a *3*-MCFG for D^3 is straighforward, can one learn
anything from it about a periodicity property of D^3
that a 2-dimensional MCFG cannot capture?

The references need some work (maybe because of bib style used?).
Check for missing volume editors/book titles/pages/place of
publication, uppercase escape (eg for Dyck, MCFL, Lie algebras)