Question: Are there any introductory texts in formal language or programming language theory which discuss how to apply it to the study of optimal notation?

In particular, I am interested to learn what stack-languages, parse trees, and indices are, and how to predict when a certain type of notation will lead to exponential redundancy.

I have basically no background in either formal language/grammar or programming theory, since as a math major the only computer science I learned was algorithms and graph theory, as well as very modest smidgens of complexity theory and Boolean functions. Thus, if the only books which discuss this are not introductory, I would be grateful for answers that both list such books discussing exponential notation blow-up as well as introductory books that will prepare for the books which directly address my question.

Context: This question is inspired primarily by an answer on Physics.SE, which says that:

It is very easy to prove (rigorously) that there is no parentheses notation which reproduces tensor index contractions, because parentheses are parsed by a stack-language (context free grammar in Chomsky's classification) while indices cannot be parsed this way, because they include general graphs. The parentheses generate parse trees, and you always have exponentially many maximal trees inside any graph, so there is exponential redundancy in the notation.

Throughout the rest of the answer, other examples of "exponential notation blow-up" are discussed, for example with Petri Nets in computational biology.

There are also other instances where mathematical notation is difficult to parse, for example as mentioned here when functions and functions applied to the argument are not distinguished clearly. This can become especially confusing when the function becomes the argument and the argument becomes the function, e.g. here.

  • 3
    $\begingroup$ This question sounds super-broad. Can you narrow it down? Also, can you define your terms? What precisely do you mean by "optimal notation"? What do you mean by "exponential redundancy" or "exponential notation blowup"? When you talk about notation, in what context? Notation for expressing what kinds of statements? $\endgroup$ – D.W. Nov 6 '16 at 18:30
  • 3
    $\begingroup$ Also, you say you want to learn what parse trees etc. are; well, explaining all of that would be much too long to provide in a single answer. I suggest you go read standard references (e.g., textbooks, online course notes), and then if you have specific questions as you're reading, come back and ask about those specific things you're confused on. $\endgroup$ – D.W. Nov 6 '16 at 18:30
  • 3
    $\begingroup$ I still think it's too broad. It'd be better to request a reference for a single topic. Also, if you just want to request references that cover stack-languages, parse trees, and indices, then all the rest (about notation redundancy etc) is irrelevant and distracting and should be removed. Finally and most importantly: What research have you already done? What references have you already found? Why did you reject them? What criteria do you plan to use for evaluating references? For instance, what background do you already have, and what level should the textbook be at? $\endgroup$ – D.W. Nov 6 '16 at 19:07
  • 3
    $\begingroup$ Basically, you want a reference for formal languages theory. A standard one is infolab.stanford.edu/~ullman/ialc.html , but know that there are university courses dedicated to the topic. The topic is very broad, so don't expect to pick it up in one afternoon ;-) $\endgroup$ – chi Nov 7 '16 at 10:31
  • 3
    $\begingroup$ What is "optimal notation" supposed to be? $\endgroup$ – Raphael Nov 8 '16 at 0:05
  1. Formal language theory does not concern itself with the semantics of the language. That might seem odd, since we tend to think of language as a mechanism for communicating something, but if you think about it, there are really two levels of understanding language (at least): the surface level, in which the language is a stream of lexemes, and the underlying denotational level which is more or less divorced from the surface representation. (Chomsky posited an intermediate "transformational" level to get around some limitations with CFGs but that's not relevant here.) Consequently, it is possible to say "the same thing" in different languages; Chomsky is not a Whorfian. (See Wikipedia for a brief overview, with some references).

  2. Nonetheless, a context-free grammar is not sufficient to distinguish correct and incorrect utterances. Chomsky offered the classic example: Colourless ideas sleep furiously (which he spelled incorrectly, being a USian). See Wikipedia, again. (Unfortunately Wikipedia doesn't have a Canadian English version.) The precise division between syntactic and semantic errors is hard, if not impossible, to demarcate and there has been considerable debate over this topic in CS fields, which I'm not going to even attempt to discuss here because I always get into trouble when I do. However, we can identify one classic grammatical rule present in many human languages: noun/verb agreement. I disagrees seems to me to be a syntactic error in the sense that I understand the intent of the utterance perfectly but also recognize it as erroneous. But this syntactic issue can only be captured by a context-free grammar if we enumerate all possible agreements. That is, we can write something vaguely like $S \to NP_{sing} VP_{sing} | NP_{plural} VP_{plural}$, but it is easy to see how the enumeration could get out of hand in language with more complicated agreement rules (gender, for example).

  3. The problem with context-free grammars is that they are context-free, although you shouldn't take that description too seriously because it is easy to fall into the trap of misinterpreting technical use of common words (which, I might argue, is the basis of this question in the first place). That means that a nonterminal (like $NP$ above) must derive exactly the same set of phrases regardless of the context in which it appears. So we could not write, for example, $S \to NP_X VP_X$ with the understanding that $X$ needs to be filled in the same way in both expansions. (This is one of the issues which which transformational grammar attempted to grapple.)

  4. That is exactly the problem with tensor index contractions. A tensor index contraction places a particular requirement on the use of index variables: an index variable must be used exactly twice, in which case it cannot be on the left-hand side, or exactly once, in which it must be on the left-hand side. (Since I'm not a physicist, I'd be tempted to collapse that into saying that an index variable must appear exactly twice in all. But there is a semantic distinction between free and placeholder variables, which is important to the understanding of the expression.) Here, there is no simple finite collection of index variables and no limit to the number of placeholders used. Moreover, renaming placeholders does not affect semantics provided that the new names are not used elsewhere in the expression, and one might expect the formal language description to capture that fact.

  5. It is in fact possible to rigorously prove the assertion that context-free grammars cannot capture contextual agreement, as in the previous examples. I think that has something to do with what the quoted claim is asserting. Depending on how omnicurious you are, you might find it interesting to learn more, but I don't think it will end up being particularly relevant to the philosophical or physical insights you seem to be seeking.

  6. The other linked articles, about unfortunate surface forms in mathematical notation, are simply anecdotal; none of them, as far as I can see, makes any deep or even superficial point relevant to formal language theory, just as the possibly famous joke that one man's fish is another man's poisson is not even vaguely insightful about romance linguistics, but it's still funny (IMO).

  • $\begingroup$ This is interesting -- I didn't realize there was such an overlap between linguistics and computer science. This does seem very relevant because one of the things that confuses me a lot about tensor/Einstein notation is the distinction between free and placeholder variables, see e.g. math.stackexchange.com/questions/2001893/… For the record, the problem the answer I mentioned seems to be referencing is with parenthetical notation, and not index notation per se, although I don't understand the argument myself. $\endgroup$ – Chill2Macht Nov 8 '16 at 6:17
  • $\begingroup$ I.e. something about parentheses being "stack-parsed" means they are "stack-languages" which means that they correspond to "parsing trees" whereas index notation supposedly corresponds to "general graphs" and the number of (maximal) trees in a graph grows exponentially with the size of the graph, so somehow this means that there are exponentially many parentheses expressions which all mean the same thing as a single index expression? I know what a stack is (LIFO) and I know what a maximal spanning tree is, but I'm not sure what is meant by parsing or parsing tree. $\endgroup$ – Chill2Macht Nov 8 '16 at 6:21
  • 2
    $\begingroup$ To parse a context free grammar, you need a "push-down automaton", which is a finite state machine with a stack. (You also need an oracle or algorithm or patience in order to find the right action; the theoretical automaton is non-deterministic.) Hence "stack language". The issue with parenthetic expressions is not the parentheses, but rather the fact that they have no indices. $\endgroup$ – rici Nov 8 '16 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.