We consider the external variant of non-isometric d-dimensional contextual array grammars with regular control together with local selectors allowing for controlling how d-dimensional arrays are evolving by adjoining rectangular (d–1)-dimensional arrays. In the 1-dimensional case, the computational power of these non-isometric contextual array grammars with regular control and local selectors equals the computational power of isometric contextual array grammars with regular control. The string images of the languages of 1-dimensional arrays generated by these contextual array grammars exactly yield the linear languages. In the more-dimensional case, non-isometric d-dimensional contextual array grammars with regular control and local selectors can simulate the computations of (d – 1)-dimensional array grammars or Turing machines. Hence, for example, the emptiness problem for non-isometric d-dimensional contextual array grammars with regular control and local selectors for d > 1 is undecidable. We also compare the computational power of all variants of non-isometric d-dimensional contextual array grammars that we introduce to each other.

We consider d -dimensional contextual array grammars and investigate their computational power when using various control mechanisms – matrices, regular control languages, and tissue P systems, which work like regular control languages, but may end up with a final check for the non-applicability of some rules. For d ≥ 2 , d -dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. The use of tissue P systems with their final non-applicability check even yields some additional computational power. In the 1-dimensional case, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages can be characterized as the family of array images of the linear languages, which for a one-letter alphabet means that it coincides with the family of regular 1-dimensional array languages.

In this paper, the concept of local languages is extended to infinite arrays and ωω-local languages are defined. ωω-recognizable languages of infinite arrays accepted by online tesselation automata are considered. Properties of these languages are studied. The notion of Muller recognizability is extended to infinite arrays. This is related to acceptance of infinite arrays by online tesselation automata.

Cell-works which are three-dimensional cyclic edge-label controlled OL-systems, were introduced by Lindenmayer. Fracchia and Prusinkiewicz provided cell-work systems using markers to model three-dimensional cellular structures. In this paper, cell-work systems with fins are proposed, generalizing the notion of map with handles. We allow each cell of a cell-work to divide into finitely many cells at any instant of time. This generalization enables us to describe three-dimensional images and fractals. A comparison of various systems with the system introduced in this paper is made.

The emptiness problem for non-overlapping Basic puzzle grammars is shown to be decidable. An alternate proof of the decidability of the non-overlapping feature for basic puzzle grammars is given. Hierarchy among the various classes of puzzle languages is also established.

Learning of certain classes of two-dimensional picture languages is considered in this paper. Linear time algorithms that learn in the limit, from positive data the classes of local picture languages and locally testable picture languages are presented. A crucial step for obtaining the learning algorithm for local picture languages is an explicit construction of a two-dimensional on-line tessellation acceptor for a given local picture language. A polynomial time algorithm that learns the class of recognizable picture languages from positive data and restricted subset queries, is presented in contrast to the fact that this class is not learnable in the limit from positive data alone.

In this paper, we introduce a new noise model on learning sets of strings in the framework of PAC learning and consider the effect of the noise on learning. The instance domain is the set Sn of strings over a finite alphabet S, and the examples are corrupted by purely random errors affecting only the instances (and not the labels). We consider three types of errors on instances, called EDIT operation errors. EDIT operations consist of “insertion”, “deletion”, and “change” of a symbol in a string. We call such a noise where the examples are corrupted by random errors of EDIT operations on instances the EDIT noise. First we show general upper bounds on the EDIT noise rate that a learning algorithm of taking the strategy of minimizing disagreements can tolerate and a learning algorithm can tolerate. Next we present an efficient algorithm that can learn a class of decision lists over the attributes “a string w contains a pattern p?” from noisy examples under some restriction on the EDIT noise rate.

Nivat et al. proposed a class of grammars called puzzle grammars. Such models are suitable for describing and generating connected arrays consisting of unit cells. In this paper, we introduce the stochastic version of puzzle grammars. Conditions for their consistency are given. Although the simplest of puzzle grammars, called basic puzzle grammar, generates a larger class of pictures than regular array grammars, the additional generative power is restricted and it requires considerable effort to write grammars for even pictures whose complexity is not high. We propose a parallel version of the puzzle grammar model which lends itself naturally to the generation of pictures. Several examples are given to illustrate the power of this model. Its stochastic version is presented along with an application to the clustering of syntactic patterns.

A method of learning pattern languages in time polynomial in the length of the pattern is introduced. The learning of certain picture languages can then be done by considering them as an interpretation of pattern languages. The learning of Tabled Regular k-Matrix languages describing arrays of symbols is also examined.

Two methods of generating isosceles right triangles by basic puzzle grammars are presented. The methods use two different sets of tiles to tile the triangular region. This is of interest in view of the fact that the set of isosceles right triangles is a nontrivial example of a two-dimensional language which cannot be generated by any regular array grammar.

We introduce a new model for generating finite, digitized, connected pictures called puzzle grammars and study its generative power by comparison with array grammars. We note how this model generalizes the classical Chomskian grammars and study the effect of direction-independent rewriting rules. We prove that regular control does not increase the power of basic puzzle grammars. We show that for basic and context-free puzzle grammars, the membership problem is NP-complete and the emptiness problem is undecidable.

Language theoretic public key cryptosystems for strings and pictures are discussed. Two methods of constructing public key cryptosystems for the safe transmission or storage of chain code pictures are presented; the first one encrypts a chain code picture as a string and the second one as a two-dimensional array.

The Siromoney matrix model is a simple and elegant model for describing two-dimensional digital picture languages. The notion of attaching indices to nonterminals in a generative grammar, introduced and investigated by Aho. is considered in the vertical phase of a Siromoney matrix grammar (SMG). The advantage of this study is that the new model retains the simplicity and elegance of SMG but increases the generative power and enables us to describe pictures not generable by SMG. Besides certain closure properties and hierarchy results. applications of these two-dimensional grammars to describe tilings, polyominoes, distorted patterns and parquet deformations are studied.