Search

A new class of graphs G(w), called Parikh word representable graphs (PWRG), corresponding to words $w$ that are finite sequence of symbols, was considered in the recent past. Several properties of these graphs have been established. In this paper, we consider these graphs corresponding to binary core words of the form $aub$ over a binary alphabet {a,b}. We derive formulas for computing the Wiener index of the PWRG of a binary core word. Sharp bounds are established on the value of this index in terms of different parameters related to binary words over {a,b} and the corresponding PWRGs. Certain other Wiener-type indices that are variants of Wiener index are also considered. Formulas for computing these indices in the case of PWRG of a binary core word are obtained.

Spiking neural P systems with rules on synapses (RSSNP systems) are a class of computation models which are inspired by the information processing and communication manner of neurons. In this work, we consider labeled RSSNP systems (lRSSNP systems), where each rule is assigned either with a label chosen from an alphabet Σ or with the empty label λ. A string over an alphabet is accepted by an lRSSNP system if the string is processed from left to right by the system in the sense that in a step only rules labeled with the processed symbol or with λ are used (not both), and the system reaches a final configuration in the moment when the whole string is processed. The set of all accepted strings is categorized as the restricted (computations are done with the application of the rules labeled with symbols from the given alphabet) control language and the unrestricted (rules labeled with λ are allowed in the computations) control language of the system. We study the language accepting power of lRSSNP systems using only standard spiking rules by comparing the family of control languages of lRSSNP systems with the families of languages in the Chomsky hierarchy. It is proved that restricted lRSSNP systems can accept no more than context-sensitive languages, and unrestricted lRSSNP systems can accept recursively enumerable languages.

An operation on strings, called flat splicing was introduced, inspired by a splicing operation on circular strings considered in the study of modelling of the recombinant behaviour of DNA molecules. A simple kind of flat splicing, called alphabetic flat splicing, allows insertion of a word with a specified start symbol and/or a specified end symbol, between two pre-determined symbols in a given word. In this work, we consider a P system with only alphabetic flat splicing rules as the evolution rules and strings of symbols as objects in its regions. We examine the language generative power of the resulting alphabetic flat splicing P systems (AFS P systems, for short). In particular, we show that AFS P systems with two membranes are more powerful in generative power than AFS P systems with a single membrane. We also construct AFS P systems with at most three membranes to generate languages that do not belong to certain other language classes and show an application to generation of chain code pictures.

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 the bio-inspired area of membrane computing, a novel computing model with a generic name of P system was introduced around the year 2000. Among its several variants, string or array language generating P systems involving rewriting rules have been considered. A new picture array model of array generating P system with a restricted type of picture insertion rules and picture array objects in its regions, is introduced here. The generative power of such a system is investigated by comparing with the generative power of certain related picture array grammar models introduced and studied in two-dimensional picture language theory. It is shown that this new model of array P system can generate picture array languages which cannot be generated by many other array grammar models. The theoretical model developed is for handling the application problem of generation of patterns encoded as picture arrays over a finite set of symbols. As an application, certain floor-design patterns are generated using such an array P system.

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.

A variety of two-dimensional array grammar models generating picture array languages have been introduced and investigated, utilizing and extending the well-established notions and techniques of formal string language theory. On the other hand the versatile computing model with a generic name of P system in the area of membrane computing, has turned out to be a rich framework for different kinds of problems in a variety of fields. Picture array generation in the field of two-dimensional (2D) languages is one such area where P systems with array objects and array rewriting, referred to as array P systems, have been fruitfully employed in increasing the generating power of the 2D grammar models. A variety of array P systems have been proposed in the literature. The objective of this survey is to review and describe the salient features of the major types of array P systems, which have served as the basis for developing other kinds of array P systems. Applications of these array P systems are also briefly described besides indicating possible new directions of investigation.

An increased number of bio-inspired face recognition systems have emerged in recent decades owing to their intelligent problem-solving ability, flexibility, scalability, and adaptive nature. Hence, this survey aims to present a detailed overview of bio-inspired approaches pertaining to the advancement of face recognition. Based on a well-classified taxonomy, relevant bio-inspired techniques and their merits and demerits in countering potential problems vital to face recognition are analyzed. A synthesis of various approaches in terms of key governing principles and their associated performance analysis are systematically portrayed. Finally, some intuitive future directions are suggested on how bio-inspired approaches can contribute to the advancement of face biometrics in the years to come.

The problem of reconstruction of a binary image in the field of discrete tomography is a classic instance of seeking solution applying mathematical techniques. Here two such binary image reconstruction problems are considered given some numerical information on the image. Algorithms are developed for solving these problems and correctness of the algorithms are discussed.

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 P systems with active membranes with three electrical charges working in the maximally parallel way. We here work with a variant of P systems with active membranes without polarizations and present a uniform solution to CAP in the minimally parallel mode.

Rewriting P systems, as language generating devices, are one of the earliest classes of P systems with structured strings as objects and the rewriting rules as evolution rules. Flat splicing is an operation on strings, inspired by a splicing operation on circular strings. In this work, we consider a variant of rewriting P systems with only regular or linear rewriting rules and alphabetic flat splicing rules, and the language generative power of rewriting P systems with flat splicing rules in comparison with flat splicing systems and Chomsky hierarchy is investigated.

The biologically inspired model, known as P system, has proved to be a general framework for investigating several problems related to computing in different fields. Two-dimensional picture array languages is one such area in which different kinds of P systems have been constructed for picture array generation. Incorporating the feature of permitting symbols in the rules, a new variety of array P system is constructed here for generating picture languages consisting of picture arrays. The advantage of this approach is that there is a reduction in the number of membranes used in the construction, in comparison to the existing array P system models.

Contextual array grammars, with selectors not having empty cells, are considered. A P system model, called contextual array P system, that makes use of array objects and contextual array rules, is introduced and its generative power for the description of picture arrays is examined. A main result of the paper is that there is a proper infinite hierarchy with respect to the classes of languages described by contextual array P systems. Such a hierarchy holds as well in the case when the selector is also endowed with the #?sensing ability.

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.

Array P systems were introduced by Paun Gh. which is linking the two areas of membrane computing and picture grammars. Puzzle grammars were introduced by us for generating connected picture arrays in the two-dimensional plane, motivated by the problem of tiling the plane. On the other hand, incorporating into arrays the developmental type of generation used in the well-known biologically motivated L systems, Siromoney and Siromoney proposed a very general rectangular array generating model, called extended controlled tabled L array system (ECTLAS). In this paper we introduce two variations of the array P system, called BPG array P system and parallel array P system. The former has in the regions array objects and basic puzzle grammar rules (BPG), which are a specific kind of puzzle grammar rules. In the latter, the regions have rectangular array objects and tables of context-free rules. We examine these two types of P systems for their array generative power.

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 langauges 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.

In the bio-inspired area of membrane computing, P system is a versatile model providing a rich framework for many computational problems. Array P system and its variant with parallel rewriting facilitate the study of picture languages within this area of membrane computing. Here another variant of array P system, called tabled parallel array P system (TPAP), is introduced, by endowing it with the features of parallel rewriting and tables of array-rewriting rules. The generative power of TPAP as well as the ability of this system in describing picture patterns are investigated.

Computational topology within the context of digital imagery has gained a considerable role in several applications like structural pattern recognition and digital image processing. Membrane computing, which is a new computational model inspired from the structure and functioning of biological cells, has been adapted as a rich framework for handling many problems. In this paper, we present a membrane computing software for automatically computing homology groups of 2D digital images in a logarithmic number of steps.

Considering a large variety of approaches in generating picture languages, the notion of pure two-dimensional context-free grammar P2DCFG represents a simple yet expressive non-isometric language generator of picture arrays. In the present paper, we introduce a new variant of P2DCFGs that generates picture arrays in a leftmost way. We concentrate our attention on determining their generative power by comparing it with the power of other picture generators. We also examine the power of these generators that regulate rewriting by control languages.

Algebraic properties of a relation on ω-words based on the notion of shuffle over ω-trajectories are obtained.

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.

A subclass of linear languages, called uniquely terminating code linear languages (utCLL), is introduced, motivated by the study of Makinen (1997), and an inference algorithm for utCLL is provided. The algorithm is extended to a corresponding subclass of equal matrix languages.

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.

We define an infinite Lyndon word as the limit of an increasing sequence of prefix preserving lyndon words and show that some of the interesting properties of Lyndon words generalize to the infinite case. We construct a queue automaton that recognizes the set of Lyndon words and show that it can be extended to recognize infinite Lyndon words. We discuss certain topological properties of the set of infinite Lyndon words such as homeomorphism with a subspace of the Cantor space.

Lyndon trees are introduced as a generalization of Lyndon words, and the basic properties studied. A correspondence between the sets of Lyndon words and Lyndon trees is established. A unique factorization theorem for factoring a tree in terms of Lyndon trees is proved. As an application of this result, a public key cryptosystem for trees is constructed, for which encryption and decryption are easy but cryptanalysis is hard. — Authors' Abstract

In the area of membrane computing, a new computability model, called P system, which is a distributed, highly parallel theoretical computing model, was introduced by Paun, inspired from the cell structure and its functioning. There are several application areas of these P systems. Among these one area deals with the problem of picture array generation. Ceterchi et al. began a study on linking the two areas of membrane computing and picture grammars, which were not very much linked before, by relating P systems and array-rewriting grammars generating picture languages and proposing array-rewriting P systems. In this paper we propose a theoretical model of a P System, called Tile pasting P system, for generating two-dimensional patterns that are formed by gluing square tiles and study some of its properties.

Motivated by the structure and functioning of the livingcell, a new computing model, called P System, was proposedin the area of Membrane Computing. Among severalareas of application of P systems, one area is concernedwith generation of picture array languages. Ceterchiet al. [1] initially proposed array-rewriting P systemsby extending the notion of string-rewriting P-Systems [8].On the other hand a new theoretical model of grammaticalpicture generation called pure 2D context-free picturegrammar (P2DCFPG) generating rectangular picture arraysof symbols has been introduced by Subramanian et al.[17]. Here we consider P2DCFPG type of rules in arrayrewritingP systems and examine the generating power ofthe resulting array P systems.

Array-rewriting P systems were introduced in [2] linking the two areas of membrane computing and picture grammars. Subsequently a variety of P systems with array objects and different kinds of rewriting has been introduced. Here we discuss a few prominent systems among these, point out their features and indicate possible problems for future study.

We introduce some classes of splicing languages generated with simple and semi-simple splicing rules, in both, the linear and circular cases. We investigate some of their properties.

The effect of regular control on Filamentous Systems with apical growth is examined. The resulting families of languages are classified with respect to regular, linear, context-free and pure languages.

An extended version of the parallel/sequential table matrix models called extended table matrix grammars (Ex-TMG), generating arrays of symbols, is proposed. The effect of imposing different types of control on the sequence of application of the tables is studied. The notion of assigning “terminal weights” to matrix grammars for describing parquet deformations is extended to Ex-TMGs.

The operation of composition is a device introduced by Abraham [1] to increase the generative capacity of regular matrix grammars. But not all families of grammars have their generative capacity increased by this operation. Paun [5] has proved that composition increases the generative capacity of linear grammars but not of regular, CF, CS or PS grammars. In this note, we show that the generative power of k-linear (k ⩾ 1) grammars is increased by composition. In fact, it is of interest to note that the families of compound linear and compound k-linear languages are equal. Furthermore, the family of compound linear languages is an AFL, properly contained in the family of CFLs. Certain other families of string and array grammars whose generative capacities are increased by the operation of composition are also provided.

It is shown that regular control on regular and linear kolam array grammars does not increase their generative capacity, while CF and CS controls increase their generative capacity.

Deterministic table 0L array systems with control are considered for the generation of infinite arrays. Rewriting of a rectangular array is done in parallel by a table of rules, the rightmost edge horizontally or the lowermost edge vertically downwards. The application of the tables is controlled by a control set. Cube-free and square-free infinite arrays are obtained as an application of this model. The adherence of the array language of a controlled deterministic table 0L array system is related to the adherence of its control set. The limit language equivalence problem and the adherence equivalence problem are shown to be undecidable for this system.

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 concept of splicing on images which is done in parallel is introduced. This is an extension of the operation of splicing on strings extensively studied in the context of DNA computing. Various properties of splicing on images are examined.