Pure 2D context-free grammar (P2DCFG) with an independent mode of array rewriting, was recently introduced and named as IP2DCFG. Here we consider a variant of IP2DCFG, called (l/u)IP2DCFG, by requiring rewriting of the leftmost (respy. uppermost) symbol in every row (respy. column) of an array, with the symbol having a rewriting rule in a given set of pure context-free rules. We introduce an array P system with (l/u)IP2DCFG kind of rules and array rewriting in its membranes. When two membranes are used in the array P system, the array generative power is increased compared to using a single membrane.

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.

Crowd and evacuation management have been active areas of research and study in the recent past. Various developments continue to take place in the process of efficient evacuation of crowds in mass gatherings. This article is intended to provide a review of intelligent evacuation management systems covering the aspects of crowd monitoring, crowd disaster prediction, evacuation modelling, and evacuation path guidelines. Soft computing approaches play a vital role in the design and deployment of intelligent evacuation applications pertaining to crowd control management. While the review deals with video and nonvideo based aspects of crowd monitoring and crowd disaster prediction, evacuation techniques are reviewed via the theme of soft computing, along with a brief review on the evacuation navigation path. We believe that this review will assist researchers in developing reliable automated evacuation systems that will help in ensuring the safety of the evacuees especially during emergency evacuation scenarios.

It is known that the Common Algorithmic Problem (CAP) has the nice property that several other NP-complete problems can be reduced to it in linear time. The decision version of this problem is known to be efficiently solved by a family of recognizer

The two areas of grammar systems and P systems, which have provided interesting computational models in the study of formal string language theory have been in the recent past effectively linked in [4] by incorporating into P systems, a communication mode called t–mode of cooperating distributed grammar systems. On the other hand cooperating array grammar systems [5] and array P systems [1] have been developed in the context of two-dimensional picture description. In this paper, motivated by the study of [4], these two systems are studied by linking them through the t–communication mode, thus bringing out the picture description power of these systems.

In this paper we consider hexagonal arrays on triangular grids and introduce hexagonal local picture languages and hexagonal tiling systems defining hexagonal recognizable picture languages, motivated by an analogous study of rectangular arrays by Giammarresi and Restivo. We also introduce hexagonal Wang tiles to define hexagonal Wang systems (HWS) as a formalism to describe hexagonal picture languages. It is noticed that the family of hexagonal picture languages defined by hexagonal Wang systems and the family recognized by hexagonal tiling systems coincide. Analogous to hv-domino systems describing rectangular arrays, we define xyz-domino systems and prove that recognizable hexagonal picture languages are characterized as projections of xyz-local picture languages.

In this paper, splicing on images of rectangular arrays is introduced as a simple and effective extension of the operation of splicing on strings extensively studied in the context of DNA computing. A comparison of the resulting class of splicing array languages with the local two-dimensional array languages and two-dimensional right linear languages is made. Certain closure properties are obtained. Furthermore, the notion of self cross-over of strings is extended to arrays with respect to the splicing of arrays introduced here.

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.

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.