Direction-independent grammars with contexts (Q1094143)

A direction-independent two-dimensional (2D) array grammar introduced by the authors [Inf. Process. Lett. 22, 295-301 (1986; Zbl 0595.68068)] applies its production rule to a subarray equivalent to the left-hand side of the rule regardless of its direction. In this paper, we first define direction-independent monotonic array grammars \((MAG_ i)\). Next, as an intermediate generating system between context-free and monotonic, we define \({}^*\)-context array grammars \((^*AG)\) and their direction- independent version \((^*AG_ i)\). Then, we investigate the generative power of direction-independent grammars with contexts. It is shown that the direction-independent restriction does not affect the generative powers of MAG. It does, however, affect the generative power of a restricted version of \({}^*AG\), i.e. connected \({}^*\)-array grammars.