You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'In a recent paper (M. Barash, A. Okhotin, “Defining contexts in context-free grammars”, LATA 2012), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions and establishes the basic theory of such grammars, leading to a normal form and a parsing algorithm working in time $\mathcal{O}(n^4)$, where $n$ is the length of the input string.'
author:
- Mikhail Barash
- Alexander Okhotin
title: 'Grammars with two-sided contexts[^1]'
---

Introduction
============

The context-free grammars are a logic for representing the syntax of languages, in which the properties of longer strings are defined by concatenating shorter strings with known properties. Disjunction of syntactic conditions is represented in this logic as multiple alternative rules defining a single symbol. One can further augment this logic with conjunction and negation operations, leading to *conjunctive grammars* [@Conjunctive] and *Boolean grammars* [@BooleanGrammars]. These grammars are context-free in the general sense of the word, as they define the properties of each substring independently of the context, in which it occurs. Furthermore, most of the practically important features of ordinary context-free grammars, such as efficient parsing algorithms, are preserved in their conjunctive and Boolean variants [@BooleanGrammars; @BooleanMatrix]. These grammar models have been a subject of recent theoretical studies [@AizikowitzKaminski_LR0; @EsikKuich; @Jez; @Kountouriotis_et_al; @Ziervogel]. Not long ago, the authors [@grammars_with_contexts_lata; @grammars_with_contexts] proposed an extension of the context-free grammars with special operators for expressing the form of the *left context*, in which the substring occurs. For example, a rule $A \to BC {\mathop{\&}}{{\lhd} D}$ asserts that every string representable as $BC$ in a left context of the form described by $D$ therefore has the property $A$. These grammars were motivated by Chomsky’s [@Chomsky p. 142] well-known idea of a phrase-structure rule applicable only in some particular contexts. Chomsky’s own attempt to implement this idea by string rewriting resulted in a model equivalent to linear-space Turing machines, in which the “nonterminal symbols”, meant to represent syntactic categories, could be freely manipulated as tape symbols. In spite of the name “context-sensitive grammars”, the resulting model was unsuitable for describing the syntax of languages, and thus failed to represent the idea of a rule applicable in a context.

Taking a new start with this idea, the authors [@grammars_with_contexts] defined *grammars with one-sided contexts*, following the logical outlook on grammars, featured in the work of Kowalski [@Kowalski Ch. 3] and of Pereira and Warren [@PereiraWarren], and later systematically developed by Rounds [@Rounds]. A grammar defines the truth value of statements of the form “a certain string has a certain property”, and these statements are deduced from each other according to the rules of the grammar. The resulting definition maintains the underlying logic of the context-free grammars, and many crucial properties of grammars are preserved: grammars with one-sided contexts have parse trees, can be transformed to a normal form and have a cubic-time parsing algorithm [@grammars_with_contexts]. However, the model allowed specifying contexts only on one side, and thus it implemented, so to say, only one half of Chomsky’s idea.

This paper continues the development of formal grammars with context specifications by allowing contexts in both directions. The proposed *grammars with two-sided contexts* may contain such rules as $A \to BC {\mathop{\&}}{{\lhd} D} {\mathop{\&}}{{\rhd} E}$, which define any substring of the form $BC$ preceded by a substring of the form $D$ and followed by a substring of the form $E$. If the grammar contains additional rules $B \to b$, $C \to c$, $D \to d$ and $E \to e$, then the above rule for $A$ asserts that a substring $bc$ of a string $w=dbce$ has the property $A$. However, this rule will not produce the same substring $bc$ occurring in another string $w'=dbcd$, because its right context does not satisfy the conjunct ${{\rhd} E}$. Furthermore, the grammars allow expressing the so-called *extended right context* (${{\trianglerighteqslant} \alpha}$), which defines the form of the current substring concatenated with its right context, as well as the symmetrically defined *extended left context* (${{\trianglelefteqslant} \alpha}$).

In Section \[section\_deduction\], this intuitive definition is formalized by deduction of propositions of the form ${A\big({u \langle w \rangle v}\big)}$, which states that the substring $w$ occurring in the context between $u$ and $v$ has the property $A$, where $A$ is a syntactic category defined by the grammar (“nonterminal symbol” in Chomsky’s terminology). Then, each rule of the grammar becomes a schema for deduction rules, and a string $w$ is generated by the grammar, if there is a proof of the proposition ${S\big({{\varepsilon}\langle w \rangle {\varepsilon}}\big)}$. A standard proof tree of such a deduction constitutes a parse tree of the string $w$.

The next Section \[section\_examples\] presents basic examples of grammars with two-sided contexts. These examples model several types of cross-references, such as declaration of identifiers before or after their use.

The paper then proceeds with developing a normal form for these grammars, which generalizes the Chomsky normal form for ordinary context-free grammars. In the normal form, every rule is a conjunction of one or more *base conjuncts* describing the form of the current substring (either as a concatenation of the form $BC$ or as a single symbol $a$), with any context specifications (${{\lhd} D}$, ${{\trianglelefteqslant} E}$, ${{\trianglerighteqslant} F}$, ${{\rhd} H}$). The transformation to the normal form, presented in Section \[section\_normal\_form\], proceeds in three steps. First, all rules generating the empty string in any contexts are eliminated. Second, all rules with an explicit empty context specification (${{\lhd} {\varepsilon}}$, ${{\rhd} {\varepsilon}}$) are also eliminated. The final step is elimination of any rules of the form $A \to B {\mathop{\&}}\ldots$, where the dependency of $A$ on $B$ potentially causes cycles in the definition.

Once the normal form is established, a simple parsing algorithm for grammars with two-sided contexts with the running time $\mathcal{O}(n^4)$ is presented in Section \[section\_parsing\_algorithm\]. While this paper has been under preparation, Rabkin [@Rabkin] has developed a more efficient and more sophisticated parsing algorithm for grammars with two-sided contexts, with the running time $\mathcal{O}(n^3)$.

Definition {#section_deduction}
==========

Ordinary context-free grammars allow using the concatenation operation to express the form of a string, and disjunction to define alternative forms. In conjunctive grammars, the conjunction operation may be used to assert that a substring being defined must conform to several conditions at the same time. The grammars studied in this paper further allow operators for expressing the form of the left context (${{\lhd} }$, ${{\trianglelefteqslant} }$) and the right context (${{\rhd} }$, ${{\trianglerighteqslant} }$) of a substring being defined.

A grammar with two-sided contexts is a quadruple $G=(\Sigma, N, R, S)$, where

-   $\Sigma$ is the alphabet of the language being defined;

-   $N$ is a finite set of auxiliary symbols (“nonterminal symbols” in Chomsky’s terminology), which denote the properties of strings defined in the grammar;

-   $R$ is a finite set of grammar rules, each of the form $$\label{eq:rule}
    \begin{split}
    A \to \alpha_1 {\mathop{\&}}\ldots {\mathop{\&}}\alpha_k {\mathop{\&}}&{{\lhd} \beta_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\lhd} \beta_m} {\mathop{\&}}{{\trianglelefteqslant} \gamma_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglelefteqslant} \gamma_n} {\mathop{\&}}\\ {\mathop{\&}}&{{\trianglerighteqslant} \kappa_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglerighteqslant} \kappa_{m'}} {\mathop{\&}}{{\rhd} \delta_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\rhd} \delta_{n'}},
    \end{split}$$ with $A \in N$, $k \geqslant 1$, $m,n,m',n' \geqslant 0$ and $\alpha_i, \beta_i, \gamma_i, \kappa_i, \delta_i \in (\Sigma \cup N)^*$;

-   $S \in N$ is a symbol representing well-formed sentences of the language.

If all rules in a grammar have only left contexts (that is, if $m'=n'=0$), then this is a grammar with one-sided contexts [@grammars_with_contexts]. If no context operators are ever used ($m=n=m'=n'=0$), this is a conjunctive grammar, and if the conjunction is also never used ($k=1$), this is an ordinary context-free grammar.

For each rule (\[eq:rule\]), each term $\alpha_i$, ${{\lhd} \beta_i}$, ${{\trianglelefteqslant} \gamma_i}$, ${{\trianglerighteqslant} \kappa_i}$ and ${{\rhd} \delta_i}$ is called a *conjunct*. Denote by ${u \langle w \rangle v}$ a substring $w \in \Sigma^*$, which is preceded by $u \in \Sigma^*$ and followed by $v \in \Sigma^*$, as illustrated in Figure \[f:substring\_with\_contexts\]. Intuitively, such a substring is generated by a rule (\[eq:rule\]), if

-   each *base conjunct* $\alpha_i=X_1 \ldots X_\ell$ gives a representation of $w$ as a concatenation of shorter substrings described by $X_1, \ldots, X_\ell$, as in context-free grammars;

-   each conjunct ${{\lhd} \beta_i}$ similarly describes the form of the *left context* $u$;

-   each conjunct ${{\trianglelefteqslant} \gamma_i}$ describes the form of the *extended left context* $uw$;

-   each conjunct ${{\trianglerighteqslant} \kappa_i}$ describes the *extended right context* $wv$;

-   each conjunct ${{\rhd} \delta_i}$ describes the *right context* $v$.

![A substring $w$ of a string $uwv$: four types of contexts.[]{data-label="f:substring_with_contexts"}](substring_with_contexts)

The semantics of grammars with two-sided contexts are defined by a deduction system of elementary propositions (items) of the form “a string $w \in \Sigma^*$ written in a left context $u \in \Sigma^*$ and in a right context $v \in \Sigma^*$ has the property $X \in \Sigma \cup N$”, denoted by ${X\big({u \langle w \rangle v}\big)}$. The deduction begins with axioms: any symbol $a \in \Sigma$ written in any context has the property $a$, denoted by ${a\big({u \langle a \rangle v}\big)}$ for all $u,v \in \Sigma^*$. Each rule in $R$ is then regarded as a schema for deduction rules. For example, a rule $A \to BC$ allows making deductions of the form $$\begin{aligned}
    {B\big({u \langle w \rangle w'v}\big)},
    {C\big({uw \langle w' \rangle v}\big)}
    \vdash_G
    {A\big({u \langle ww' \rangle v}\big)}
    && (\text{for all $u,w,w',v \in \Sigma^*$}),\end{aligned}$$ which is essentially a concatenation of $w$ and $w'$ that respects the contexts. If the rule is of the form $A \to BC {\mathop{\&}}{{\lhd} D}$, this deduction requires an extra premise: $$\begin{aligned}
    {B\big({u \langle w \rangle w'v}\big)},
    {C\big({uw \langle w' \rangle v}\big)},
    {D\big({{\varepsilon}\langle u \rangle ww'v}\big)}
    &\vdash_G
    {A\big({u \langle ww' \rangle v}\big)}.
\intertext{And if the rule is $A \to BC {\mathop{\&}}{{\trianglerighteqslant} F}$,
the deduction proceeds as follows:}
    {B\big({u \langle w \rangle w'v}\big)},
    {C\big({uw \langle w' \rangle v}\big)},
    {F\big({u \langle ww'v \rangle {\varepsilon}}\big)}
    &\vdash_G
    {A\big({u \langle ww' \rangle v}\big)}.
$$ The general form of deduction schemata induced by a rule in $R$ is defined below.

\[def:deduction\_system\] Let $G=(\Sigma, N, R, S)$ be a grammar with two-sided contexts. Define the following deduction system of items of the form ${X\big({u \langle w \rangle v}\big)}$, with $X \in \Sigma \cup N$ and $u,w,v \in \Sigma^*$. There is a single axiom scheme $\vdash_G {a\big({u \langle a \rangle v}\big)}$, for all $a \in \Sigma$ and $u,v \in \Sigma^*$. Each rule (\[eq:rule\]) in $R$ defines the following scheme for deduction rules: $$I \vdash_G {A\big({u \langle w \rangle v}\big)},$$ for all $u, w, v \in \Sigma^*$ and for every set of items $I$ satisfying the below properties:

-   For every base conjunct $\alpha_i=X_1 \ldots X_\ell$, with $\ell \geqslant 0$ and $X_j \in \Sigma \cup N$, there should exist a partition $w=w_1 \ldots w_\ell$ with ${X_j\big({u w_1 \ldots w_{j-1} \langle w_j \rangle w_{j+1} \ldots w_\ell v}\big)} \in I$ for all $j \in \{1, \ldots, \ell\}$.

-   For every conjunct ${{\lhd} \beta_i}={{\lhd} X_1 \ldots X_\ell}$ there should be such a partition $u=u_1 \ldots u_\ell$, that ${X_j\big({u_1 \ldots u_{j-1} \langle u_j \rangle u_{j+1} \ldots u_\ell w v}\big)} \in I$ for all $j \in \{1, \ldots, \ell\}$.

-   Every conjunct ${{\trianglelefteqslant} \gamma_i}={{\trianglelefteqslant} X_1 \ldots X_\ell}$ should have a corresponding partition $uw=x_1 \ldots x_\ell$ with ${X_j\big({x_1 \ldots x_{j-1} \langle x_j \rangle x_{j+1} \ldots x_\ell v}\big)} \in I$ for all $j \in \{1, \ldots, \ell\}$.

-   For every conjunct ${{\rhd} \delta_i}$ and ${{\trianglerighteqslant} \kappa_i}$, the condition is defined symmetrically.

Then the language generated by a symbol $A \in N$ is defined as $$L_G(A) = {\{ \, {u \langle w \rangle v} \mid u,w,v \in \Sigma^*, \: \vdash_G {A\big({u \langle w \rangle v}\big)} \, \}}.$$ The language generated by the grammar $G$ is the set of all strings with empty left and right contexts generated by $S$: $L(G)={\{ \, w \mid w \in \Sigma^{*}, \: \vdash_G {S\big({{\varepsilon}\langle w \rangle {\varepsilon}}\big)} \, \}}$.

The following trivial example of a grammar is given to illustrate the definitions.

\[example:abca\_grammar\] Consider the grammar with two-sided contexts that defines the singleton language $\{abca\}$: $$\begin{aligned}
S &\to& a S \ | \ S a \ | \ B C \\
A &\to& a \\
B &\to& b {\mathop{\&}}{{\lhd} A} \\
C &\to& c {\mathop{\&}}{{\rhd} A}\end{aligned}$$

The deduction given below proves that the string $abca$ has the property $S$. $$\begin{aligned}
    & \vdash {a\big({{\varepsilon}\langle a \rangle bca}\big)}
        && (axiom) \\
    & \vdash {b\big({a \langle b \rangle ca}\big)}
        && (axiom) \\
    & \vdash {c\big({ab \langle c \rangle a}\big)}
        && (axiom) \\
    & \vdash {a\big({abc \langle a \rangle {\varepsilon}}\big)}
        && (axiom) \\
    {a\big({{\varepsilon}\langle a \rangle bca}\big)}
    & \vdash {A\big({{\varepsilon}\langle a \rangle bca}\big)}
        && (A \to a) \\
    {b\big({a \langle b \rangle ca}\big)}, {A\big({{\varepsilon}\langle a \rangle bca}\big)}
    & \vdash {B\big({a \langle b \rangle ca}\big)}
        && (B \to b {\mathop{\&}}{{\lhd} A}) \\
    {a\big({abc \langle a \rangle {\varepsilon}}\big)}
    & \vdash {A\big({abc \langle a \rangle {\varepsilon}}\big)}
        && (A \to a) \\
    {c\big({ab \langle c \rangle a}\big)}, {A\big({abc \langle a \rangle {\varepsilon}}\big)}
    & \vdash {C\big({ab \langle c \rangle a}\big)}
        && (C \to c {\mathop{\&}}{{\rhd} A}) \\
    {B\big({a \langle b \rangle ca}\big)}, {C\big({ab \langle c \rangle a}\big)}
    & \vdash {S\big({a \langle bc \rangle a}\big)}
        && (S \to BC) \\
    {a\big({{\varepsilon}\langle a \rangle bca}\big)}, {S\big({a \langle bc \rangle a}\big)}
    & \vdash {S\big({{\varepsilon}\langle abc \rangle a}\big)}
        && (S \to a S) \\
    {S\big({{\varepsilon}\langle abc \rangle a}\big)}, {a\big({abc \langle a \rangle {\varepsilon}}\big)} 
    & \vdash {S\big({{\varepsilon}\langle abca \rangle {\varepsilon}}\big)}
        && (S \to S a)\end{aligned}$$

![A parse tree of the string $abca$ according to the grammar in Example \[example:abca\_grammar\].[]{data-label="f:abca_tree"}](simple_parse_tree)

Another possible definition of grammars with contexts is by directly expressing them in first-order logic over positions in a string [@Rounds]. Nonterminal symbols become *binary predicates*, with the arguments referring to positions in the string. Each predicate $A(x, y)$ is defined by a formula $\varphi_A(x, y)$ that states the condition of a substring delimilited by positions $x$ and $y$ having the property $A$. There are built-in unary predicates $a(x)$, for each $a \in \Sigma$, which assert that the symbol in position $x$ in the string is $a$, and binary predicates $x<y$ and $x=y$ for comparing positions. Arguments to predicates are given as *terms*, which are either variables ($t=x$) or constants referring to the first and the last positions ($t={\ensuremath{ \underline{\mathrm{begin}} }}$, $t={\ensuremath{ \underline{\mathrm{end}} }}$), and which may be incremented ($t+1$) or decremented ($t-1$). Each formula is constructed from predicates using conjunction, disjunction and first-order existential quantification.

The grammar from Example \[example:abca\_grammar\] is expressed by the following formulae defining predicates $S(x,y)$, $B(x,y)$, $A(x,y)$ and $C(x,y)$. $$\begin{aligned}
S(x,y) &=&
    \left( a(x) \land S(x+1,y) \right)
    \,\lor\,
    \left( S(x,y-1) \land a(y) \right)
    \,\lor\,
    \left( \exists z \left( x < z < y     \land B(x,z) \land C(z,y) \right) \right) \\
A(x,y) &=&
    a(x) \land x+1 = y \\
B(x,y) &=&
    b(x) \land x+1 = y \land A({\ensuremath{ \underline{\mathrm{begin}} }}, x) \\
C(x,y) &=&
    c(x) \land x+1 = y \land A(y, {\ensuremath{ \underline{\mathrm{end}} }})\end{aligned}$$ The membership of a string $w$ is expressed by the statement $S({\ensuremath{ \underline{\mathrm{begin}} }}, {\ensuremath{ \underline{\mathrm{end}} }})$, which may be true of false.

Examples {#section_examples}
========

This section presents several examples of grammars with two-sided contexts generating important syntactic constructs. All examples use ordinary context-free elements, such as a grammar for ${\{ \, a^nb^n \mid n \geqslant 0 \, \}}$, and combine these elements using the new context operators. This leads to natural specifications of languages in the style of classical formal grammars.

Consider the problem of checking declaration of identifiers before their use: this construct can be found in all kinds of languages, and it can be expressed by a conjunctive grammar [@BooleanSurvey Ex. 3]. The variant of this problem, in which the identifiers may be declared *before or after* their use, is also fairly common: consider, for instance, the declaration of classes in C++, where an earlier defined method can refer to a class member defined later. However, no conjunctive grammar expressing this construct is known.

A grammar with one-sided contexts for declarations before or after use has recently been constructed by the authors [@grammars_with_contexts]. That grammar used context specifications, along with iterated conjunction, to express what would be more naturally expressed in terms of two-sided contexts. In the model proposed in this paper, the same language can be defined in a much more natural way.

\[declarations\_before\_or\_after\_use\_example\] Consider the language $$\label{declarations_before_or_after_use_language}
    {\{ \, u_1 \ldots u_n \mid \text{for every $u_i$,
        \textbf{either}
        $u_i \in a^* c$,
        \textbf{or}
        $u_i = b^k c$ and
        there exists $j \in \{1, \ldots, n\}$
        with $u_j=a^k c$} \, \}}.$$ Substrings of the form $a^k c$ represent declarations, while every substring of the form $b^k c$ is a reference to a declaration of the form $a^k c$.

This language is generated by the following grammar. $$\begin{array}{rcl@{\quad \qquad}rcl}
S &\to& AS \ | \ CS \ | \ DS \ | \ {\varepsilon}& C &\to& B {\mathop{\&}}{{\trianglelefteqslant} EFc} \\
A &\to& a A \ | \ c
    & D &\to& B {\mathop{\&}}{{\trianglerighteqslant} HcE} \\
B &\to& b B \ | \ c
    & F &\to& a F b \ | \ c E \\
E &\to& AE \ | \ BE \ | \ {\varepsilon}& H &\to& b H a \ | \ c E
\end{array}$$

The idea of the grammar is that $S$ should generate a substring ${u_1 \ldots u_\ell \langle u_{\ell+1} \ldots u_n \rangle {\varepsilon}}$, with $0 \leqslant \ell \leqslant n$ and $u_i \in a^* c \cup b^* c$, if and only if every reference in $u_{\ell+1} \ldots u_n$ has a corresponding declaration somewhere in the whole string $u_1 \ldots u_n$. The rules for $S$ define all substrings satisfying this condition inductively on their length, until the entire string ${{\varepsilon}\langle u_1 \ldots u_n \rangle {\varepsilon}}$ is defined. The rule $S \to {\varepsilon}$ defines the base case: the string ${u_1 \ldots u_n \langle {\varepsilon}\rangle {\varepsilon}}$ has the desired property. The rule $S \to CS$ appends a reference of the form $b^*c$, restricted by an extended left context ${{\trianglelefteqslant} EFc}$, which ensures that this reference has a matching *earlier* declaration; here $E$ represents the prefix of the string up to that earlier declaration, while $F$ matches the symbols $a$ in the declaration to the symbols $b$ in the reference. The possibility of a *later* declaration is checked by another rule $S \to DS$, which adds a reference of the form $b^*c$ with an extended right context ${{\trianglerighteqslant} HcE}$, where $H$ is used to match the $b$s forming this reference to the $a$s in the later declaration.

The next example abstracts another syntactic mechanism—*function prototypes*—found in the C programming language and, under the name of *forward declarations*, in the programming language Pascal.

\[example:prototypes\] Consider the language

$$\begin{aligned}
\label{eq:prototype_declarations__prototype}
\big\{
u_1 \ldots u_n
\: \big| \:
\text{for every $u_i$}, \;
    & \text{\textbf{either} $u_i = a^k c$ and there exists $j > i$,
        such that $u_j = d^k c$,} \\
\label{eq:prototype_declarations__reference}
    & \text{\textbf{or} $u_i = b^k c$ and there exists $j < i$,
        for which $u_j = a^k c$}\big\}.
$$

A substring of the form $a^k c$ represents a function prototype and a substring $d^k c$ represents its body. Calls to functions are expressed as substrings $b^k c$. Condition (\[eq:prototype\_declarations\_\_prototype\]) means that every prototype must be followed by its body, and restriction (\[eq:prototype\_declarations\_\_reference\]) requires that references are only allowed to declared prototypes. This language can be generated by the following grammar with two-sided contexts. $$\begin{array}{rcl@{\quad\qquad}rcl@{\quad\qquad}rcl}
S &\to& U S \ | \ V S \ | \ D S \ | \ {\varepsilon}& D &\to& d D \ | \ c
        & E &\to& A E \ | \ B E \ | \ D E \ | \ {\varepsilon}\\
A &\to& a A \ | \ c
    & U &\to& A {\mathop{\&}}{{\trianglerighteqslant} H c E}
        & H &\to& a H d \ | \ c E\\
B &\to& b B \ | \ c
    & V &\to& B {\mathop{\&}}{{\trianglelefteqslant} E F c}
        & F &\to& a F b \ | \ c E\\
\end{array}$$

The rules $S \to US$ and $U \to A {\mathop{\&}}{{\trianglerighteqslant} HcE}$ append a prototype $a^k c$ and the extended right context of the form $a^k c \ldots d^k c \ldots$ ensures that this prototype has a matching body somewhere *later* within the string. The rules $S \to VS$ and $V \to B {\mathop{\&}}{{\trianglelefteqslant} EFc}$ append a reference $b^k c$, and the context specification $\ldots a^k c \ldots b^k c$ checks that it has a matching prototype *ealier* in the string. Function bodies $d^k c$ are added by the rule $S \to DS$. Using these rules, $S$ generates substrings of the form ${u_1 \ldots u_\ell \langle u_{\ell+1} \ldots u_n \rangle {\varepsilon}}$, with $0 \leqslant \ell \leqslant n$ and $u_i \in a^*c \cup b^*c \cup d^*c$, such that every prototype $u_i = a^k c$ in $u_{\ell+1} \ldots u_n$ has a corresponding body $d^k c$ in $u_{i+1} \ldots u_n$ and every reference $u_i = b^k c$ in $u_{\ell+1} \ldots u_n$ has a corresponding prototype $a^k c$ in $u_1 \ldots u_{i-1}$.

The next example gives a grammar with contexts that defines reachability on graphs. Sudborough [@Sudborough] defined a linear context-free grammar for a special encoding of the graph reachability problem on acyclic graphs, in which every arc goes from a lower-numbered vertex to a higher-numbered vertex. The grammar presented below allows any graphs and uses a direct encoding. This example illustrates the ability of grammars with contexts to define various kinds of cross-references.

\[graph\_example\] Consider encodings of directed graphs as strings of the form $b^s \:
a^{i_1} b^{j_1} \: a^{i_2} b^{j_2} \: \ldots \: a^{i_n} b^{j_n} \:
a^t$, with $s, t \geqslant 1, \: n \geqslant 0, \: i_k,j_k \geqslant 1$, where each block $a^i b^j$ denotes an arc from vertex number $i$ to vertex number $j$, while the prefix $b^s$ and the suffix $a^t$ mark $s$ as the source vertex and $t$ as the target. Then the following grammar defines all graphs with a path from $s$ to $t$. $$\begin{array}{rcl@{\quad \qquad}rcl}
S &\to& F D C A \ | \ F 
    & &&\\
A &\to& a A \ | \ c
    & D &\to& B {\mathop{\&}}{{\trianglelefteqslant} B C E} \ | \ B {\mathop{\&}}{{\trianglerighteqslant} FDCA} \ | \ B {\mathop{\&}}{{\trianglerighteqslant} F} \\
B &\to& b B \ | \ c
    & E &\to& a E b \ | \ D C A \\
C &\to& A B C \ | \ {\varepsilon}& F &\to& b F a \ | \ b C a
\end{array}$$

The grammar is centered around the nonterminal $D$, which generates all such substrings ${b^s a^{i_1} b^{j_1} \ldots a^{i_k} \langle b^{j_k} \rangle a^{i_{k+1}}b^{j_{k+1}} \ldots a^{i_n} b^{j_n} a^t}$ that there is a path from $j_k$ to $t$ in the graph. If this path is empty, then $j_k = t$. Otherwise, the first arc in the path can be listed either to the left or to the right of $b^k$. These three cases are handled by the three rules for $D$. Each of these rules generates $b^{j_k}$ by the base conjunct $B$, and then uses an extended left or right context operator to match $b^{j_k}$ to the tail of the next arc or to $a^t$.

The rule $D \to B {\mathop{\&}}{{\trianglelefteqslant} B C E}$ considers the case when the next arc in the path is located to the left of $b^{j_k}$. Let this arc be $a^{i_\ell}b^{j_\ell}$, for some $\ell<k$. Then the extended left context $BCE$ covers the substring $b^s a^{i_1}b^{j_1} \ldots a^{i_\ell}b^{j_\ell} \ldots a^{i_k}b^{j_k}$. The concatenation $BC$ skips the prefix $b^s a^{i_1}b^{j_1} \ldots a^{i_{\ell-1}}b^{j_{\ell-1}}$, and then the nonterminal $E$ matches $a^{i_\ell}$ to $b^{j_k}$, verifying that $i_\ell=j_k$. After this, the rule $E \to DCA$ ensures that the substring $b^{j_\ell}$ is generated by $D$, that is, that there is a path from $j_\ell$ to $t$. The concatenation $CA$ skips the inner substring $a^{i_{\ell+1}}b^{j_{\ell+1}} \ldots a^{i_k}$.

The second rule $D \to B {\mathop{\&}}{{\trianglerighteqslant} FDCA}$ searches for the next arc to the right of $b^{j_k}$. Let this be an $\ell$-th arc in the list, with $\ell>k$. The extended right context $FDCA$ should generate the suffix $b^{j_k} \ldots a^{i_\ell}b^{j_\ell} \ldots a^{i_n}b^{j_n} a^t$. The symbol $F$ covers the substring $b^{j_k} \ldots a^{i_\ell}$, matching $b^{j_k}$ to $a^{i_\ell}$. Then, $D$ generates the substring $b^{j_\ell}$, checking that there is a path from $j_\ell$ to $t$. The concatenation $CA$ skips the rest of the suffix.

Finally, if the path is of length zero, that is, $j_k=t$, then the rule $D \to B {\mathop{\&}}{{\trianglerighteqslant} F}$ uses $F$ to match $b^{j_k}$ to the suffix $a^t$ in the end of the string.

Once the symbol $D$ checks the path from any vertex to the vertex $t$, for the initial symbol $S$, it is sufficient to match $b^s$ in the beginning of the string to any arc $a^{j_k} b^{j_k}$, with $j_k=s$. This is done by the rule $S \to FDCA$, which operates in the same way as the second rule for $D$. The case of $s$ and $t$ being the same node is handled by the rule $S \to F$.

All the above examples use identifiers given in unary, which are matched by rules of the same kind as the rules defining the language ${\{ \, a^n b^n \mid n \geqslant 0 \, \}}$. These examples can be extended to use identifiers over an arbitrary alphabet $\Sigma$, owing to the fact that there is a conjunctive grammar generating the language ${\{ \, w\#w \mid w \in \Sigma^* \, \}}$, for some separator $\# \notin \Sigma$ [@Conjunctive; @BooleanSurvey].

Normal form {#section_normal_form}
===========

An ordinary context-free grammar can be transformed to the Chomsky normal form, with the rules restricted to $A \to BC$ and $A \to a$, with $B,C \in N$ and $a \in \Sigma$. This form has the following generalization to grammars with contexts.

A grammar with two-sided contexts $G=(\Sigma,N,R,S)$ is said to be in the binary normal form, if each rule in $R$ is of one of the forms $$\begin{aligned}
    A &\to B_1 C_1 {\mathop{\&}}\ldots {\mathop{\&}}B_k C_k {\mathop{\&}}{{\lhd} D_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\lhd} D_m} {\mathop{\&}}{{\trianglelefteqslant} E_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglelefteqslant} E_n} {\mathop{\&}}{{\trianglerighteqslant} F_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglerighteqslant} F_{n'}} {\mathop{\&}}{{\rhd} H_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\rhd} H_{m'}}, \\
    A &\to a {\mathop{\&}}{{\lhd} D_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\lhd} D_m} {\mathop{\&}}{{\trianglelefteqslant} E_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglelefteqslant} E_n} {\mathop{\&}}{{\trianglerighteqslant} F_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglerighteqslant} F_{n'}} {\mathop{\&}}{{\rhd} H_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\rhd} H_{m'}},\end{aligned}$$ where $k \geqslant 1$, $m,n,n',m' \geqslant 0$, $B_i, C_i, D_i, E_i, F_i, H_i \in N$, $a \in \Sigma$.

The transformation to the normal form consists of three stages: first, removing all *empty conjuncts* ${\varepsilon}$; secondly, eliminating *empty contexts* (${{\lhd} {\varepsilon}}$, ${{\rhd} {\varepsilon}}$); finally, getting rid of *unit conjuncts* of the form $B$, with $B \in N$.

The first step is the removal of all rules of the form $A \to {\varepsilon}{\mathop{\&}}\ldots$, so that no symbols generate ${\varepsilon}$, while all non-empty strings are generated as before. As generation of longer strings may depend on the generation of ${\varepsilon}$, already for ordinary context-free grammars, such a transformation requires adding extra rules that simulate the same dependence without actually generating any empty strings.

\[example:nullable\_context\_free\] Consider the following context-free grammar, which defines the language $\{abc, ab, ac, a, bcd, bd, cd, d\}$. $$\begin{aligned}
S &\to& a A \ | \ A d \\
A &\to& BC\\
B &\to& {\varepsilon}\ | \ b \\
C &\to& {\varepsilon}\ | \ c\end{aligned}$$ Since $B$ generates the empty string, the rule $A \to BC$ can be used to generate just $C$; therefore, once the rule $B \to {\varepsilon}$ is removed, one should add a new rule $A \to C$, in which $B$ is omitted. Similarly one can remove the rule $C \to {\varepsilon}$ and add a “compensatory” rule $A \to B$. Since both $B$ and $C$ generate ${\varepsilon}$, so does $A$ by the rule $A \to BC$. Hence, extra rules $S \to a$ and $S \to d$, where $A$ is omitted, have to be added.

An algorithm for carrying out such a transformation first calculates the set of nonterminals that generate the empty string, known as $\textsc{Nullable}(G) \subseteq N$, and then uses it to reconstruct the rules of the grammar. This set is calculated as a least upper bound of an ascending sequence of sets $\textsc{Nullable}_i(G)$. The set $\textsc{Nullable}_1(G) = {\{ \, A \in N \mid A \to {\varepsilon}\in R \, \}}$ contains all nonterminals which directly define the empty string. Every next set $\textsc{Nullable}_{i+1}(G) = {\{ \, A \in N \mid A \to \alpha \in R, \: \alpha \in \textsc{Nullable}_i^*(G) \, \}}$ contains nonterminals that generate ${\varepsilon}$ by the rules referring to other nullable nonterminals. This knowledge is given by the Kleene star of $\textsc{Nullable}_i(G)$.

For the grammar in Example \[example:nullable\_context\_free\], the calculation of the set $\textsc{Nullable}(G)$ proceeds as follows: $$\begin{aligned}
\textsc{Nullable}_0(G) &=& {\varnothing},\\
\textsc{Nullable}_1(G) &=& \big\{ B, C \big\},\\
\textsc{Nullable}_2(G) &=& \big\{ B, C, A \big\},\end{aligned}$$ and $\textsc{Nullable}(G) = \textsc{Nullable}_2(G)$.

The same idea works for conjunctive grammars as well [@Conjunctive]. For grammars with contexts [@grammars_with_contexts], the generation of the empty string additionally depends on the left contexts, in which the string occurs. This requires an elaborated version of the set $\textsc{Nullable}(G)$, formed of nonterminals along with the information about the left contexts in which they may define ${\varepsilon}$.

In order to eliminate null conjuncts in case of grammars with two-sided contexts, one has to consider yet another variant of the set $\textsc{Nullable}(G)$, which respects both left and right contexts.

\[example:nullable\_grammar\_with\_two\_sided\_contexts\] Consider the following grammar with two-sided contexts, obtained by adding context restrictions to the grammar in Example \[example:nullable\_context\_free\]; this grammar defines the language $L = \{abc, ac, bcd, bd\}$. $$\begin{aligned}
S &\to& a A \ | \ A d\\
A &\to& B C\\
B &\to& {\varepsilon}{\mathop{\&}}{{\lhd} D} \ | \ b\\
C &\to& {\varepsilon}{\mathop{\&}}{{\rhd} E} \ | \ c\\
D &\to& a\\
E &\to& d\end{aligned}$$ In this grammar, the nonterminal $B$ generates the empty string only in a left context of the form defined by $D$, while $C$ defines the empty string only in a right context of the form $E$. In those contexts where *both* $B$ and $C$ generate ${\varepsilon}$, so can $A$, by the rule $A \to BC$.

The information about the left and right contexts, in which a nonterminal generates the empty string, is to be stored in the set $\textsc{Nullable}(G)$, which is defined as a subset of $2^N \times N \times 2^N$. An element $(U, A, V)$ of this set represents an intuitive idea that $A$ defines ${\varepsilon}$ in a left context of the form described by each nonterminal in $U$, and in a right context of the form given by nonterminals in $V$.

For the grammar in Example \[example:nullable\_grammar\_with\_two\_sided\_contexts\], such a set $\textsc{Nullable}(G)$ is constructed as follows. $$\begin{aligned}
\textsc{Nullable}_0(G) &=& {\varnothing}\\
\textsc{Nullable}_1(G) &=& \big\{ (\{D\}, B, {\varnothing}), ({\varnothing}, C, \{E\}) \big\} \\
\textsc{Nullable}_2(G) &=& \big\{ (\{D\}, B, {\varnothing}), ({\varnothing}, C, \{E\}), (\{D\}, A, \{E\}) \big\}\end{aligned}$$ Then $\textsc{Nullable}(G) = \textsc{Nullable}_2(G)$. The elements $(\{D\}, B, {\varnothing})$ and $({\varnothing}, C, \{E\})$ are obtained directly from the rules of the grammar, and the element $(\{D\}, A, \{E\})$ represents the “concatenation” $BC$ in the rule for $A$. Note the similarity of this construction to the one for the ordinary grammar in Example \[example:nullable\_context\_free\]: the construction given here is different only in recording information about the contexts.

The above “concatenation” of triples $(\{D\}, B, {\varnothing})$ and $({\varnothing}, C, \{E\})$ should be defined to accumulate both left and right contexts. This can be regarded as a generalization of the Kleene star to sets of triples, denoted by $\textsc{Nullable}^\star(G)$. Formally, $\textsc{Nullable}^\star(G)$ is the set of all triples $(U_1 \cup \ldots \cup U_\ell, \: A_1 \ldots A_\ell, \: V_1 \cup \ldots \cup V_\ell)$ with $\ell \geqslant 0$ and $(U_i, A_i, V_i) \in \textsc{Nullable}(G)$. The symbols $A_i$ are concatenated, while their left and right contexts are accumulated. In the special case when $\ell = 0$, the concatenation of zero symbols is the empty string, and thus ${\varnothing}^\star = \big\{ ({\varnothing}, {\varepsilon}, {\varnothing}) \big\}$.

Before giving a formal definition of the set $\textsc{Nullable}(G)$, assume, for the sake of simplicity, that context operators are only applied to single nonterminal symbols, that is, every rule is of the form $$\label{eq:rule_alpha_D_E_F_H}
\begin{split}
A \to \alpha_1 {\mathop{\&}}\ldots {\mathop{\&}}\alpha_k {\mathop{\&}}{{\lhd} D_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\lhd} D_m} {\mathop{\&}}{{\trianglelefteqslant} E_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglelefteqslant} E_n} {\mathop{\&}}{{\trianglerighteqslant} F_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglerighteqslant} F_{m'}} {\mathop{\&}}{{\rhd} H_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\rhd} H_{n'}},
\end{split}$$ with $A \in N$, $k \geqslant 1$, $m,n,m',n' \geqslant 0$, $\alpha_i \in (\Sigma \cup N)^*$ and $D_i, E_i, F_i, H_i \in N$. As will be shown in Lemma \[lemma:almost\_normal\_form\], there is no loss of generality in this assumption.

\[def:Nullable\] Let $G = (\Sigma, N, R, S)$ be a grammar with two-sided contexts with all rules of the form (\[eq:rule\_alpha\_D\_E\_F\_H\]).

Construct the sequence of sets $\textsc{Nullable}_i(G) \subseteq 2^N \times N \times 2^N$, for $i \geqslant 0$, as follows.

Let $\textsc{Nullable}_0(G) = {\varnothing}$. Every next set $\textsc{Nullable}_{i+1}(G)$ contains the following triples: for every rule (\[eq:rule\_alpha\_D\_E\_F\_H\]) and for every $k$ triples $(U_1, \alpha_1, V_1)$, …, $(U_k, \alpha_k, V_k)$ in $\textsc{Nullable}_i^\star(G)$, the triple $\big(
    \{D_1,\ldots,D_m, E_1, \ldots, E_n\}
    \cup \{U_1, \ldots, U_k\},
    \; A, \;
    \{F_1,\ldots,F_{m'}, H_1, \ldots, H_{n'}\}
    \cup \{V_1, \ldots, V_k\}
    \big)$ is in $\textsc{Nullable}_{i+1}(G)$. Finally, let $\textsc{Nullable}(G) = \bigcup_{i \geqslant 0} \textsc{Nullable}_{i}(G)$.

The next lemma explains how exactly the set $\textsc{Nullable}(G)$ represents the generation of the empty string by different nonterminals in different contexts.

\[lemma:nullable\] Let $G = (\Sigma,N,R,S)$ be a grammar with contexts, let $A \in N$ and $u, v \in \Sigma^*$. Then, ${u \langle {\varepsilon}\rangle v} \in L_G(A)$ if and only if there is a triple $(\{J_1, \ldots, J_s\}, A, \{K_1, \ldots, K_t\})$ in $\textsc{Nullable}(G)$, such that ${{\varepsilon}\langle u \rangle v} \in L_G(J_i)$ for all $i$ and ${u \langle v \rangle {\varepsilon}} \in L_G(K_j)$ for all $j$.

The plan is to reconstruct the grammar, so that for every triple $(\{J_1, \ldots, J_s\}, A, \{K_1, \ldots, K_t\})$ in $\textsc{Nullable}(G)$, and for every occurrence of $A$ in the right-hand side of any rule, the new grammar contains a companion rule, in which $A$ is omitted and context operators for $J_i$ and $K_i$ are introduced.

The following case requires special handling in the new grammar. Assume that $A$ generates ${\varepsilon}$ in the empty left context (that is, $u={\varepsilon}$ in Lemma \[lemma:nullable\]). This is reflected by a triple $(\{J_1, \ldots, J_s\}, A, \{K_1, \ldots, K_t\})$ in $\textsc{Nullable}(G)$, in which all symbols $J_i$ also generate ${\varepsilon}$ in the left context ${\varepsilon}$. The latter generation may in turn involve some further right context operators. In the new grammar, the left context will be explicitly set to be empty (${{\lhd} {\varepsilon}}$), whereas all those right contexts should be assembled together with the set $\{K_1, \ldots, K_t\}$, and used in the new rules, where $A$ is omitted. This calculation of right contexts is done in the following special variant of the set $\textsc{Nullable}$.

\[def:left\_Nullable\] Let $G = (\Sigma, N, R, S)$ be a grammar. Define sets ${\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}_i(G) \subseteq N \times 2^N$, with $i \geqslant 0$: $$\begin{aligned}
    {\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}_0(G) &= {\{ \, (A, V) \mid ({\varnothing}, A, V) \in \textsc{Nullable}(G) \, \}},
        \\
    {\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}_{i+1}(G) &=
    \big\{
(A, V \cup V_1 \cup \ldots \cup V_s)
\: \big| \:
(\{J_1, \ldots, J_s\}, A, V) \in \textsc{Nullable}(G), \\
&\hspace*{4cm}
\exists \: V_1, \ldots, V_s \subseteq N:
(J_i, V_i) \in {\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}_i(G) \big\}.\end{aligned}$$ Let ${\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G) = \bigcup_{i \geqslant 0} {\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}_i(G)$.

\[lemma:left\_nullable\] Let $G = (\Sigma, N, R, S)$ be a grammar, let $A \in N$ and $v \in \Sigma^*$. Then ${{\varepsilon}\langle {\varepsilon}\rangle v} \in L_G(A)$ if and only if there is a pair $(A, \{K_1, \ldots, K_t\})$ in ${\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$, such that ${{\varepsilon}\langle v \rangle {\varepsilon}} \in L_G(K_i)$ for all $i$.

There is a symmetrically defined set ${\ensuremath{ {{\rhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G) \subseteq 2^N \times N$, which characterizes the generation of ${\varepsilon}$ in an empty right context. With the generation of the empty string represented in these three sets, a grammar with two-sided contexts is transformed to the normal form as follows. First, it is convenient to simplify the rules of the grammar, so that every concatenation is of the form $BC$, with $B, C \in N$, and the context operators are only applied to individual nonterminals. For this, base conjuncts $\alpha$ with ${\ensuremath{ |\alpha| }} > 2$ and context operators ${{\lhd} \alpha}$, ${{\trianglelefteqslant} \alpha}$, ${{\trianglerighteqslant} \alpha}$ and ${{\rhd} \alpha}$ with ${\ensuremath{ |\alpha| }} > 1$ are shortened by introducing new nonterminals.

\[lemma:almost\_normal\_form\] For every grammar $G_0 = (\Sigma, N_0, R_0, S_0)$, there exists and can be effectively constructed another grammar $G = (\Sigma, N, R, S)$ generating the same language, with all rules of the form:

\[eq:rules\_almost\_normal\_form\] $$\begin{aligned}
\label{eq:almost_a} A &\to a\\
\label{eq:almost_BC} A &\to BC\\
\label{eq:almost_B_D_E_F_H}
    A &\to  B_1 {\mathop{\&}}\ldots {\mathop{\&}}B_k {\mathop{\&}}{{\lhd} D_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\lhd} D_m} {\mathop{\&}}{{\trianglelefteqslant} E_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglelefteqslant} E_n} {\mathop{\&}}{{\trianglerighteqslant} F_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglerighteqslant} F_{m'}} {\mathop{\&}}{{\rhd} H_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\rhd} H_{n'}}\\
\label{eq:almost_e} A &\to {\varepsilon},\end{aligned}$$

with $a \in \Sigma$ and $A, B, C, D_i, E_i, F_i, H_i \in N$.

\[Construction:epsilon\_elimination\] Let $G = (\Sigma, N, R, S)$ be a grammar with two-sided contexts, with all rules of the form (\[eq:rules\_almost\_normal\_form\]). Consider the sets $\textsc{Nullable}(G)$, ${\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$ and ${\ensuremath{ {{\rhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$, and construct another grammar with two-sided contexts $G' = (\Sigma, N, R', S)$, with the following rules.

1.  All rules of the form (\[eq:almost\_a\]) in $R$ are added to $R'$.

2.  Every rule of the form (\[eq:almost\_BC\]) in $R$ is added to $R'$, along with the following extra rules, where a nullable nonterminal is omitted and the fact that it generates ${\varepsilon}$ is expressed by context operators. $$\begin{aligned}
    A &\to B {\mathop{\&}}{{\trianglelefteqslant} J_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglelefteqslant} J_s} {\mathop{\&}}{{\rhd} K_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\rhd} K_t},
    \quad \text{for $(\{J_1, \ldots, J_s\}, C, \{K_1, \ldots, K_t\}) \in \textsc{Nullable}(G)$} \\
    A &\to B {\mathop{\&}}{{\trianglelefteqslant} J_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglelefteqslant} J_s} {\mathop{\&}}{{\rhd} {\varepsilon}},
    \quad \text{for $(\{J_1, \ldots, J_s\}, C) \in {\ensuremath{ {{\rhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$ with $s \geqslant 1$} \\
    A &\to C {\mathop{\&}}{{\lhd} J_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\lhd} J_s} {\mathop{\&}}{{\trianglerighteqslant} K_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglerighteqslant} K_t},
    \quad \text{for $(\{J_1, \ldots, J_s\}, B, \{K_1, \ldots, K_t\}) \in \textsc{Nullable}(G)$} \\
    A &\to C {\mathop{\&}}{{\trianglerighteqslant} K_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglerighteqslant} K_t} {\mathop{\&}}{{\lhd} {\varepsilon}},
    \quad \text{for $(B, \{K_1, \ldots, K_t\}) \in {\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$
    with $t \geqslant 1$}\end{aligned}$$ In the first case, $C$ defines ${\varepsilon}$ in left contexts $J_i$ and right contexts $K_i$, and this restriction is implemented by context operators in the new rule. Since the left context of $C$ includes $B$, extended context operators (${{\trianglelefteqslant} J_i}$) are used on the left, whereas the right context operators are proper (${{\rhd} K_i}$).

    The second case considers the possibility of a nullable nonterminal $C$, which defines ${\varepsilon}$ in an empty right context. This condition is simulated by the conjunct ${{\rhd} {\varepsilon}}$ and extended left contexts ${{\trianglelefteqslant} J_i}$.

    The two last rules handle symmetrical cases, when the nonterminal $B$ defines the empty string.

3.  Every rule of the form (\[eq:almost\_B\_D\_E\_F\_H\]) is preserved in $R'$. In the original grammar, this rule (\[eq:almost\_B\_D\_E\_F\_H\]) may generate strings in empty contexts, as long as symbols in the context operators (${{\lhd} D_i}$, ${{\rhd} H_i}$) are nullable. For any collection of pairs $(D_1, V_1)$, …, $(D_m, V_m) \in {\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$, with $m \geqslant 1$, add the rule $$A \to
        B_1 {\mathop{\&}}\ldots {\mathop{\&}}B_k {\mathop{\&}}E_1 {\mathop{\&}}\ldots {\mathop{\&}}E_n {\mathop{\&}}{{\trianglerighteqslant} K_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglerighteqslant} K_t} {\mathop{\&}}{{\trianglerighteqslant} F_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglerighteqslant} F_{m'}} {\mathop{\&}}{{\rhd} H_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\rhd} H_{n'}}
        {\mathop{\&}}{{\lhd} {\varepsilon}},$$ where $\{K_1, \ldots, K_t\} = \bigcup_{i=1}^{m} V_i$. Nonterminals $D_1$, …, $D_m$ define ${\varepsilon}$ in the right contexts given in the set ${\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$. This is represented by conjuncts ${{\lhd} {\varepsilon}}$ and ${{\trianglerighteqslant} K_i}$. Extended left contexts ${{\trianglelefteqslant} E_i}$ are replaced with base conjuncts $E_i$, because in the empty left context they have the same effect.

    Symmetrically, if $(U_1, H_1)$, …, $(U_{n'}, H_{n'}) \in {\ensuremath{ {{\rhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$, with $n' \geqslant 1$, then there is a rule $$A \to
        B_1 {\mathop{\&}}\ldots {\mathop{\&}}B_k {\mathop{\&}}F_1 {\mathop{\&}}\ldots {\mathop{\&}}F_{m'} {\mathop{\&}}{{\lhd} D_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\lhd} D_m} {\mathop{\&}}{{\trianglelefteqslant} E_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglelefteqslant} E_n} {\mathop{\&}}{{\trianglelefteqslant} K_1} {\mathop{\&}}\ldots {\mathop{\&}}{{\trianglelefteqslant} K_t} {\mathop{\&}}{{\rhd} {\varepsilon}},$$ where $\{K_1, \ldots, K_t\} = \bigcup_{i=1}^{n'} U_i$.

    Finally, if with $m$, $n' \geqslant 1$ and $(D_1, V_1)$, …, $(D_m, V_m) \in {\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$, $(U_1, H_1)$, …, $(U_{n'}, H_{n'}) \in {\ensuremath{ {{\rhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$, then the set $R'$ contains a rule $$A \to
        B_1 {\mathop{\&}}\ldots {\mathop{\&}}B_k {\mathop{\&}}E_1 {\mathop{\&}}\ldots {\mathop{\&}}E_n {\mathop{\&}}F_1 {\mathop{\&}}\ldots {\mathop{\&}}F_{m'} {\mathop{\&}}K_1 {\mathop{\&}}\ldots {\mathop{\&}}K_t {\mathop{\&}}{{\lhd} {\varepsilon}} {\mathop{\&}}{{\rhd} {\varepsilon}},$$ where $\{K_1, \ldots, K_t\} = \bigcup_{i=1}^{m} V_i \cup \bigcup_{j=1}^{n'} U_j$. In this case, both left and right contexts of a string are empty. All the symbols $D_i$ and $H_i$ define ${\varepsilon}$ in the contexts specified in ${\ensuremath{ {{\lhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$ and ${\ensuremath{ {{\rhd} {\varepsilon}}\text{-}\textsc{Nullable} }}(G)$. These contexts apply to the entire string and are explicitly stated as $K_1 {\mathop{\&}}\ldots {\mathop{\&}}K_t$ in the new rule. The null contexts ${{\lhd} {\varepsilon}}$, ${{\rhd} {\varepsilon}}$ limit the applicability of this rule to the whole string. Again, as in the two previous cases, the base conjuncts are used instead of extended context operators.

\[epsilon\_conjunct\_elimination\_lemma\] Let $G = (\Sigma, N, R, S)$ be a grammar with two-sided contexts. Then the grammar $G' = (\Sigma, N', R', S)$ obtained by Construction \[Construction:epsilon\_elimination\] generates the language $L(G') = L(G) \setminus \{{\varepsilon}\}$.

The above construction eliminates the empty string in all base conjuncts, but the resulting grammar may still contain null context specifications (${{\lhd} {\varepsilon}}$ and ${{\rhd} {\varepsilon}}$), which state that the current substring is a prefix or a suffix of the whole string. These operators are eliminated by the following simple transformation. First, define a new nonterminal symbol $U$ that generates all non-empty strings in the empty left context. This is done by the following three rules: $$\begin{aligned}
    U &\to U a
        && \text{(for all $a \in \Sigma$)} \\
    U &\to a {\mathop{\&}}{{\trianglelefteqslant} X}
        && \text{(for all $a \in \Sigma$)} \\
    X &\to a
        && \text{(for all $a \in \Sigma$)}\end{aligned}$$ Another symbol $V$ generates all non-empty strings in the empty right context; it is defined by symmetric rules. Then it remains to replace left and right null context operators (${{\lhd} {\varepsilon}}$, ${{\rhd} {\varepsilon}}$) with $U$ and $V$, respectively.

The third stage of the transformation to the normal form is removing the *unit conjuncts* in rules of the form $A \to B {\mathop{\&}}\ldots$ Already for conjunctive grammars [@Conjunctive], the only known transformation involves substituting all rules for $B$ into all rules for $A$; in the worst case, this results in an exponential blowup. The same construction applies verbatim to grammars with contexts.

This three-stage transformation proves the following theorem.

\[thm\_normal\_form\] For each grammar with two-sided contexts $G=(\Sigma,N,R,S)$ there exists and can be effectively constructed a grammar with two-sided contexts $G'=(\Sigma,N',R',S)$ in the binary normal form, such that $L(G)=L(G') \setminus \{{\varepsilon}\}$.

Parsing algorithm {#section_parsing_algorithm}
=================

Let $G=(\Sigma,N,R,S)$ be a grammar with two-sided contexts in the binary normal form, and let $w=a_1 \ldots a_n \in \Sigma^+$, with $n \geqslant 1$ and $a_i \in \Sigma$, be an input string to be parsed. For every substring of $w$ delimited by two positions $i,j$, with $0 \leqslant i < j \leqslant n$, consider the set of nonterminal symbols generating this substring. $$T_{i,j} = {\big\{ \: A \; \big| \; A \in N, \;
{a_1 \ldots a_i \langle a_{i+1} \ldots a_j \rangle a_{j+1} \ldots a_n} \in L_G(A) \: \big\}}$$ In particular, the whole string $w$ is in $L(G)$ if and only if $S \in T_{0,n}$.

In ordinary context-free grammars, a substring $a_{i+1} \ldots a_j$ is generated by $A$ if there is a rule $A \to BC$ and a partition of the substring into $a_{i+1} \ldots a_k$ generated by $B$ and $a_{k+1} \ldots a_j$ generated by $C$, as illustrated in Figure \[f:dependencies\_with\_contexts\](left). Accordingly, each set $T_{i,j}$ depends only on the sets $T_{i', j'}$ with $j'-i'<j-i$, and hence all these sets may be constructed inductively, beginning with shorter substrings and eventually reaching the set $T_{0,n}$: this is the Cocke–Kasami–Younger parsing algorithm. For conjunctive grammars, all dependencies are the same, and generally the same parsing algorithm applies [@Conjunctive]. In grammars with only left contexts, each set $T_{i,j}$ additionally depends on the sets $T_{0,i}$ and $T_{0,j}$ via the conjuncts of the form ${{\lhd} D}$ and ${{\trianglelefteqslant} E}$, respectively, which still allows constructing these sets progressively for $j=1, \ldots, n$ [@grammars_with_contexts].

The more complicated structure of logical dependencies in grammars with two-sided contexts is shown in Figure \[f:dependencies\_with\_contexts\](right). The following example demonstrates how these dependencies may form circles.

![How the membership of $A$ in $T_{i,j}$ depends on other data, for rules (a) $A \to BC$ and (b) $A \to BC {\mathop{\&}}{{\lhd} D} {\mathop{\&}}{{\trianglelefteqslant} E} {\mathop{\&}}{{\trianglerighteqslant} F} {\mathop{\&}}{{\rhd} H}$.[]{data-label="f:dependencies_with_contexts"}](dependencies_with_contexts_two_sided)

Consider the grammar with the rules $$\begin{aligned}
S &\to AB\\ A &\to a {\mathop{\&}}{{\rhd} B}\\ B &\to b {\mathop{\&}}{{\lhd} C}\\
C &\to a $$ and the input string $w=ab$. It is immediately seen that $C \in T_{0,1}$. From this, one can infer that $B \in T_{1,2}$, and that knowledge can in turn be used to show that $A \in T_{0,1}$. These data imply that $S \in T_{0,2}$. Thus, none of the sets $T_{0,1}$ and $T_{1,2}$ can be fully constructed before approaching the other.

The proposed algorithm for constructing the sets $T_{i,j}$ works as follows. At the first pass, it makes all deductions $\vdash_{G} {A\big({a_1 \ldots a_i \langle a_{i+1} \ldots a_j \rangle a_{j+1} \ldots a_n}\big)}$ that do not involve any contexts, and accordingly puts $A$ to the corresponding $T_{i,j}$. This pass progressively considers longer and longer substrings, as done by the Cocke–Kasami–Younger algorithm for ordinary grammars. During this first pass, some symbols may be added to any sets $T_{0,j}$ and $T_{i,n}$, and thus it becomes known that some contexts are true. This triggers another pass over all entries $T_{i,j}$, from shorter substrings to longer ones, this time using the known true contexts in the deductions. This pass may result in adding more elements to $T_{0,j}$ and $T_{i,n}$, which will require yet another pass, and so on. Since a new pass is needed only if a new element is added to any of $2n-1$ subsets of $N$, the total number of passes is at most $(2n-1) \cdot |N| + 1$.

These calculations are implemented in Algorithm \[alg:parsing\_cky\], which basically deduces all true statements about all substrings of the input string. For succinctness, the algorithm uses the following notation for multiple context operators. For a set $\mathcal{X} = \{X_1, \ldots, X_\ell\}$, with $X_i \in N$, and for an operator $Q \in \{{{\lhd} }, {{\trianglelefteqslant} }, {{\trianglerighteqslant} }, {{\rhd} }\}$, denote $Q \mathcal{X} := Q X_1 {\mathop{\&}}\ldots {\mathop{\&}}Q X_\ell$.

\[alg:parsing\_cky\] Let $G=(\Sigma,N,R,S)$ be a grammar with contexts in the binary normal form. Let $w=a_1 \ldots a_n \in \Sigma^+$ (with $n \geqslant 1$ and $a_i \in \Sigma$) be the input string. Let $T_{i,j}$ with $0 \leqslant i < j \leqslant n$ be variables, each representing a subset of $N$, and let $T_{i,j}={\varnothing}$ be their initial values.

\[cubic\_time\_parsing\_\_loop\_while\_changes\] \[cubic\_time\_parsing\_\_loop\_j\] \[cubic\_time\_parsing\_\_a\_j\] $T_{j-1,j} = T_{j-1,j} \cup \{A\}$ \[cubic\_time\_parsing\_\_T\_jminus1\_j\] \[cubic\_time\_parsing\_\_loop\_i\] let $P = {\varnothing}$ ($P \subseteq N \times N$) \[cubic\_time\_parsing\_\_loop\_k\] $P = P \cup (T_{i,k} \times T_{k,j})$ \[cubic\_time\_parsing\_\_cartesian\_product\] \[cubic\_time\_parsing\_\_loop\_T\_i\_j\] $T_{i,j} = T_{i,j} \cup \{A\}$ \[cubic\_time\_parsing\_\_T\_i\_j\]

\[cubic\_time\_parsing\_theorem\] For every grammar with two-sided contexts $G$ in the binary normal form, Algorithm \[alg:parsing\_cky\], given an input string $w=a_1 \ldots a_n$, constructs the sets $T_{i,j}$ and determines the membership of $w$ in $L(G)$, and does so in time $\mathcal{O}(|G|^2 \cdot n^4)$, using space $\mathcal{O}(|G| \cdot n^2)$.

While this paper was under preparation, Rabkin [@Rabkin] developed a more efficient and more sophisticated parsing algorithm for grammars with two-sided contexts, with the running time $\mathcal{O}(|G| \cdot n^3)$, using space $\mathcal{O}(|G| \cdot n^2)$. Like Algorithm \[alg:parsing\_cky\], Rabkin’s algorithm works by proving all true statements about the substrings of the given string, but does so using the superior method of Dowling and Gallier [@DowlingGallier]. Nevertheless, Algorithm \[alg:parsing\_cky\] retains some value as the elementary parsing method for grammars with two-sided contexts—just like the Cocke–Kasami–Younger algorithm for ordinary grammars remains useful, in spite of the asymptotically superior Valiant’s algorithm [@Valiant].

Conclusion
==========

This paper has developed a formal representation for the idea of phrase-structure rules applicable in a context, featured in the early work of Chomsky [@Chomsky]. This idea did not receive adequate treatment at the time, due to the unsuitable string-rewriting approach. The logical approach, adapted from Rounds [@Rounds] and his predecessors, brings it to life.

There are many theoretical questions to research about the new model: for instance, one can study the limitations of their expressive power, their closure properties, efficient parsing algorithms and subfamilies that admit more efficient parsing. Another possibility for further studies is investigating Boolean and stochastic variants of grammars with contexts, following the recent related work [@EsikKuich; @Kountouriotis_et_al; @Ziervogel].

On a broader scope, there must have been other good ideas in the theory of formal grammars that were inadequately formalized before. They may be worth being re-investigated using the logical approach.

[99]{} T. Aizikowitz, M. Kaminski, [“LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata”]{}, *Computer Science in Russia* (CSR 2011, St. Petersburg, Russia, 14–18 June 2011), LNCS 6651, 345–358, [DOI: [[10.1007/978-3-642-20712-9\_27](http://dx.doi.org/10.1007/978-3-642-20712-9_27)]{}]{}.

M. Barash, [“Programming language specification by a grammar with contexts”]{}, In: S. Bensch, F. Drewes, R. Freund, F. Otto (Eds.), *Fifth Workshop on Non-Classical Models of Automata and Applications* (NCMA 2013, Ume[å]{}, Sweden, 13–14 August, 2013), <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS> 294, [Ö]{}sterreichische Computer Gesellschaft (2013), 51–67, <http://users.utu.fi/mikbar/kieli>.

M. Barash, A. Okhotin, [“Defining contexts in context-free grammars”]{}, *Language and Automata Theory and Applications* (LATA 2012, A Coruña, Spain, 5–9 March 2012), LNCS 7183, 106–118, [DOI: [[10.1007/978-3-642-28332-1\_10](http://dx.doi.org/10.1007/978-3-642-28332-1_10)]{}]{}.

M. Barash, A. Okhotin, [“An extension of context-free grammars with one-sided context specifications”]{}, *Information and Computation*, in press, [DOI: [[10.1016/j.ic.2014.03.003](http://dx.doi.org/10.1016/j.ic.2014.03.003)]{}]{}.

M. Barash, A. Okhotin, [“Linear grammars with one-sided contexts and their automaton representation”]{}, *LATIN 2014: Theoretical Informatics* (Montevideo, Uruguay, 31 March–4 April 2014), LNCS 8392, 190–201, [DOI: [[10.1007/978-3-642-54423-1\_17](http://dx.doi.org/10.1007/978-3-642-54423-1_17)]{}]{}.

N. Chomsky, [“On certain formal properties of grammars”]{}, *Information and Control*, 2:2 (1959), 137–167, [DOI: [[10.1016/S0019-9958(59)90362-6](http://dx.doi.org/10.1016/S0019-9958(59)90362-6)]{}]{}.

W. F. Dowling, J. H. Gallier, [“Linear-time algorithms for testing the satisfiability of propositional Horn formulae”]{}, *Journal of Logic Programming*, 1:3 (1984), 267–284, [DOI: [[10.1016/0743-1066(84)90014-1](http://dx.doi.org/10.1016/0743-1066(84)90014-1)]{}]{}.

Z. Ésik, W. Kuich, [“Boolean fuzzy sets”]{}, *International Journal of Foundations of Computer Science*, 18:6 (2007), 1197–1207, [DOI: [[10.1142/S0129054107005248](http://dx.doi.org/10.1142/S0129054107005248)]{}]{}.

S. Ginsburg, H. G. Rice, [“Two families of languages related to ALGOL”]{}, *Journal of the ACM*, 9 (1962), 350–371, [DOI: [[10.1145/321127.321132](http://dx.doi.org/10.1145/321127.321132)]{}]{}.

A. Jeż, [“Conjunctive grammars can generate non-regular unary languages”]{}, *International Journal of Foundations of Computer Science*, 19:3 (2008), 597–615, [DOI: [[10.1142/S012905410800584X](http://dx.doi.org/10.1142/S012905410800584X)]{}]{}.

R. Kowalski, *Logic for Problem Solving*, North-Holland, Amsterdam, 1979.

V. Kountouriotis, Ch. Nomikos, P. Rondogiannis, [“Well-founded semantics for Boolean grammars”]{}, *Information and Computation*, 207:9 (2009), 945–967, [DOI: [[10.1016/j.ic.2009.05.002](http://dx.doi.org/10.1016/j.ic.2009.05.002)]{}]{}.

A. Okhotin, “Conjunctive grammars”, *Journal of Automata, Languages and Combinatorics*, 6:4 (2001), 519–535.

A. Okhotin, [“Conjunctive grammars and systems of language equations”]{}, *Programming and Computer Software*, 28:5 (2002), 243–249, [DOI: [[10.1023/A:1020213411126](http://dx.doi.org/10.1023/A:1020213411126)]{}]{}.

A. Okhotin, [“Boolean grammars”]{}, *Information and Computation*, 194:1 (2004), 19–48, [DOI: [[10.1016/j.ic.2004.03.006](http://dx.doi.org/10.1016/j.ic.2004.03.006)]{}]{}.

A. Okhotin, [“Conjunctive and Boolean grammars: the true general case of the context-free grammars”]{}, *Computer Science Review*, 9 (2013), 27–59, [DOI: [[10.1016/j.cosrev.2013.06.001](http://dx.doi.org/10.1016/j.cosrev.2013.06.001)]{}]{}.

A. Okhotin, [“Improved normal form for grammars with one-sided contexts”]{}, *Descriptional Complexity of Formal Systems* (DCFS 2013, London, Ontario, Canada, 22-25 July 2013), LNCS 8031, 205–216, [DOI: [[10.1007/978-3-642-39310-5\_20](http://dx.doi.org/10.1007/978-3-642-39310-5_20)]{}]{}.

A. Okhotin, [“Parsing by matrix multiplication generalized to Boolean grammars”]{}, *Theoretical Computer Science*, 516 (2014), 101–120, [DOI: [[10.1016/j.tcs.2013.09.011](http://dx.doi.org/10.1016/j.tcs.2013.09.011)]{}]{}.

F. C. N. Pereira, D. H. D. Warren, [“Parsing as deduction”]{}, *21st Annual Meeting of the Association for Computational Linguistics* (ACL 1983, Cambridge, Massachusetts, USA, 15–17 June 1983), 137–144.

M. Rabkin, [“Recognizing two-sided contexts in cubic time”]{}, *Computer Science—Theory and Applications* (CSR 2014, Moscow, Russia, 6–12 June 2014), LNCS 8476, to appear.

W. C. Rounds, [“LFP: A logic for linguistic descriptions and an analysis of its complexity”]{}, *Computational Linguistics*, 14:4 (1988), 1–9.

I. H. Sudborough, [“A note on tape-bounded complexity classes and linear context-free languages”]{}, *Journal of the ACM*, 22:4 (1975), 499–500, [DOI: [[10.1145/321906.321913](http://dx.doi.org/10.1145/321906.321913)]{}]{}.

L. G. Valiant, [“General context-free recognition in less than cubic time”]{}, *Journal of Computer and System Sciences*, 10:2 (1975), 308–314, [DOI: [[10.1016/S0022-0000(75)80046-8](http://dx.doi.org/10.1016/S0022-0000(75)80046-8)]{}]{}.

R. Zier-Vogel, M. Domaratzki, “RNA pseudoknot prediction through stochastic conjunctive grammars”, *Computability in Europe 2013. Informal Proceedings*, 80–89.

[^1]: Supported by the Academy of Finland under grant 257857.