Search

In the recent years, several new classes of contextual grammars have been introduced to give an appropriate model description to natural languages. With this aim, some new families of contextual languages have been introduced based on maximal and depth-first conditions and analyzed in the framework of so-called mildly context sensitive languages. However, the relationship among these families of languages have not yet been analyzed in detail. In this paper, we investigate the relationship between the families of languages whose grammars are based on maximal and depth-first conditions. We prove an interesting result that all these families of languages are incomparable to each other, but they are not disjoint. [ABSTRACT FROM AUTHOR]

The concept of a Parikh matrix or an extended Parikh mapping of words introduced by Mateescu et al (2001) is formulated here for two-dimensional (2D) arrays. A polynomial time algorithm is proposed to reconstruct an unknown 2D-array over { 0,1 } from its image under the extended Parikh mapping along a single direction. On the other hand the problem of reconstructing a 2D-array over { 0,1 } from its image under the extended Parikh mapping along three or more directions is shown to be NP-hard. Also a polynomial time algorithm to reconstruct a 2D-array over {0,1} with a maximum number of ones close to the main diagonal of the array is presented by reducing the problem to Min-cost Max-flow problem. [ABSTRACT FROM AUTHOR]

The aim of this paper is to study the reconstruction of binary images from two projections using a priori images that are similar to the unknown image. Reconstruction of images from a few projections is preferred to reduce radiation hazards. It is well known that the problem of reconstructing images from a few projections is ill-posed. To handle the ill-posedness of the problem, a priori information such as convexity, connectivity and periodicity are used to limit the number of possible solutions. We use a priori images that are similar to the unknown image, to reduce the class of images having the same two projections. The a priori similar images may be obtained in many ways such as by considering images of neighboring slices or images of the same slice, taken in previous time instances. In this paper, we give a polynomial time algorithm to reconstruct binary image from two projections such that the reconstructed image is optimally close to the a priori similar images. We obtain a solution to our problem by reducing our problem to min cost integral max flow problem. [ABSTRACT FROM AUTHOR]

We define the projection of a tiling as a matrix P = (pij) where pi1 is number of t1,2 tiles in row i and pi2 is the number of t2,1 tiles in row i. We give an efficient algorithm to tile a 2D-square grid with only t1,2, t2,1, t1,1 tiles such that the projection of this tiling is the same as the given projection. [ABSTRACT FROM AUTHOR]

In this paper we consider networks of evolutionary processors with splicing rules and forbidding context (NEPFS) as language generating and computational devices. Such a network consists of several processors placed on the nodes of a virtual graph and are able to perform splicing (which is a biologically motivated operation) on the words present in that node, according to the splicing rules present there. Before applying the splicing operation on words, we check for the absence of certain symbols (forbidding context) in the strings on which the rule is applied. Each node is associated with an input and output filter. When the filters are based on random context conditions, one gets the computational power of Turing machines with networks of size two. We also show how these networks can be used to solve NP-complete problems in linear time. [ABSTRACT FROM AUTHOR]

This paper considers a computational model using the pep-tide-antibody interactions. These interactions which are carried out in parallel can be used to solve NP-complete problems. In this paper we show how to use peptide experiments to solve the Hamiltonian Path Problem (HPP) and a particular version of Set Cover problem called Exact Cover by 3-Sets problem. We also prove that this of model of computation is computationally complete. [ABSTRACT FROM AUTHOR]