Improved normal form for grammars with one-sided contexts (Q2348260)

The contribution investigates a new normal form for conjunctive grammars with one-sided context restrictions. Roughly speaking, a conjunctive grammar [\textit{A. Okhotin}, J. Autom. Lang. Comb. 6, No. 4, 519--535 (2001; Zbl 1004.68082)] is an extension of the classical notion of a context-free grammar to include a conjunctive operator~\(\&\). In addition to the productions like \(A \to BC \mid D\) of a context-free grammar, which expresses that the nonterminal~\(A\) can develop into \(BC\)~or~\(D\) (disjunction), a conjunctive grammar also offers productions of the form \(A \to BC \& D\), which states that the nonterminal~\(A\) has to develop (successfully) into both \(BC\) and \(D\), which in some sense implies a branching into two (independent) derivations which both need to be successful in generating the same nonterminal-free string. Context-restrictions are built on top of conjunctive grammars by adding specialized new conjuncts \(\vartriangleleft\)~and~\(\trianglelefteq\). In slightly more detail, the proper (left) context operator~\(\vartriangleleft\) applied to a standard right-hand side requires that the (left) context (i.e., the prefix of the finally generated string up to the location generated by the current nonterminal) is generated by that right-hand side. For example, \(A \to BC \& \mathord{\vartriangleleft}D\) states that in a sentential form~\(uAv\), the nonterminal~\(A\) has to develop into~\(BC\), but additionally the nonterminal \(D\) must be able to generate the prefix~\(u\). There is another context operator,~\(\trianglelefteq\), which restricts the prefix including the substring generated by the current nonterminal. For such conjunctive grammars with left contexts, an extension of Chomsky normal form was established in [\textit{M. Barash} and \textit{A. Okhotin}, Inf. Comput. 237, 268--293 (2014; Zbl 1360.68531)], which states that each such grammar can equivalently be expressed as a grammar that only uses productions of the form \(A \to B_1C_1 \& \dotsm \& B_nC_n \& \dotsm\) and \(A \to a \& \dotsm\), in which the capital letters are nonterminals, the lower-case letters are terminals, and, in addition, there may be context operators applied to nonterminals in both forms of the productions. The transformation into this normal form can induce a single exponential size increase. The main result of this contribution states that each conjunctive grammar with left-contexts is indeed equivalent to a conjunctive grammar in the mentioned extension of Chomsky normal form, in which additionally no context operators occur in the binary productions and only proper context operators occur in the terminal productions. This normal form completely removes circular dependencies and makes parsing conceptually simpler, but unfortunately, it involves a triple-exponential blow-up on the grammar size. The simplification of the parser is also presented and it improves the complexity (using the old normal form, the complexity of the parsing algorithm is quadratic in the grammar size whereas the simplification is linear in the grammar size as usual). Finally, the new normal form enables optimizations that concern the evaluation order. It is well known that standard parsing for context-free grammars and conjunctive grammars as well is effectively as efficient as Boolean matrix multiplication. While the reduction to Boolean matrix multiplication seems unavailable for conjunctive grammars with contexts, an optimization using matrix-vector products is presented, which cuts essentially a \(\log n\)-factor from the parsing complexity. Overall, the paper is very well written and exceptionally illustrated and exemplified. All notions are clearly motivated, defined, and exemplified. In addition, all notions and approaches are linked to the existing literature. The paper is extremely self-contained and each graduate of computer science with some background on context-free grammars should be able to fully appreciate this contribution.