|
Florin MANEA, Gheorghe ŞTEFĂNESCU
Gemma BEL-ENGUIX, Maria Dolores JIMÉNEZ-LÓPEZ, Carlos MARTÍN-VIDE Abstract. In this paper, a new/alternative approach to language representation is presented. In our model, languages are formed by interactions of a finite number of grammars each of them generating just a finite language. We consider languages as infinite objects which emerge from interactions of “smaller” finite language generators. The approach we introduce here can build a bridge between two opposite views in present-day linguistics – one that regards natural languages as infinite objects, and the second one that regards them as finite objects. The basic notion we used here is called a colony. Colonies as well-formalized language generating devices were proposed in [33]. Components of a colony are regular grammars generating finite languages and operating on a shared string of symbols. The aim of this contribution is to connect both colonies and the philosophy behind them with the opposition between two conceptions of natural language: the work in theoretical linguistics, where many scholars agree that the set of sentences in a human language must be denumerably infinite, and the work in corpus-based computational linguistics, where the focus is often on language as a finite set. We intend to show that it is possible to formally reconcile these two so apparently different conceptions of natural language.
Paolo BOTTONI, Anna LABELLA Abstract. We explore a variant of a recently introduced operation on images, which provides an adequate basis for modeling computations in which concurrent agents cooperatively construct (pointed) pictures. In this setting, concurrent agents generate languages of multi-dimensional words on partially ordered alphabets through a simple operation of overlapping, constrained by the order imposed on the alphabet. The overlapping operation is proved to be a powerful tool for picture generation in general. The operation is parametric with respect to the composition law, and we show how some simple requests on the behavior of this law provide a meet-semilattice structure to the class of pointed pictures. This feature allows their use in building a model for concurrent processes in the spirit of process algebras.
Gabriel CIOBANU, Solomon MARCUS, Gheorghe PĂUN Abstract. We examine the computing power and complexity of P systems which use two strategies of applying the rules. One strategy is to maximize the number of objects used in rules and the other is to maximize the number of rules applied in each membrane. For P systems with cooperative multiset rewriting rules, P systems with active membranes, and P systems with symport/antiport rules we prove the computational universality for both these types of parallelism. The computational complexity of the maximum consuming systems is studied for systems with cooperative rules of two types, by using two known combinatorial NP-complete problems, namely the knapsack problem and the integer linear programming.
Erzsébet CSUHAJ-VARJÚ, Tomáš MASOPUST, György VASZIL Abstract. This paper studies cooperating distributed grammar systems working in the terminal derivation mode where the components are variants of permitting grammars. It proves that although the family of permitting languages is strictly included in the family of random context languages, the families of random context languages and languages generated by permitting cooperating distributed grammar systems in the above mentioned derivation mode coincide. Moreover, if the components are so-called left-permitting grammars, then cooperating distributed grammar systems in the terminal mode characterize the class of context-sensitive languages, or if erasing rules are allowed, the class of recursively enumerable languages. Descriptional complexity results are also presented. It is shown that the number of permitting components can be bounded, in the case of left-permitting components with erasing rules even together with the number of nonterminals.
Jürgen DASSOW, Sherzod TURAEV Abstract. Essentially, a Petri net controlled grammar is a context-free grammar equipped with a Petri net and a function which maps transitions of the net to rules of the grammar. The language consists of all terminal words that can be obtained by applying of a sequence of productions which is the image of an occurrence sequence of the Petri net under the function. We study the generative power of such grammars on the type of the function which can be a bijection or a coding or a weak coding and with respect to three types of admitted sets of occurrence sequences. We show that the generative power does not depend on the type of the function. Moreover, the restriction to occurrence sequences, which transform the initial marking to a marking in a given finite set of markings, leads to a more powerful class of grammars than the allowance of all occurrence sequences. Furthermore, we present some new characterizations of the family of matrix languages in terms of Petri net controlled grammars.
Mihai IONESCU, Cătălin Ionuţ TÂRNĂUCĂ, Cristina TÂRNĂUCĂ Abstract. We continue the study of the human phenomena of sleep and wakefulness by means of spiking neural P systems [8], advancing towards a biologically-sophisticated model (we have only “natural” features). More precisely, we propose a system where each neuron of [8] (some of which make use of extended rules) is replaced by a sub-system without modifying the global output. Hence, we can claim that the study of the neuronal dreaming process is more “realistic” in our setting.
Peter LEUPOLD, Remco LOOS, Florin MANEA Abstract. In this paper we address the size complexity of Accepting Hybrid Networks of Evolutionary Processors (AHNEPs) that recognize regular and context-free languages. We present AHNEPs of small constant size for both classes. We show that any regular language can be accepted by an AHNEP of size 6, while AHNEPs of size 9 suffice for all context-free languages, moreover accepting them in linear time. Both bounds constitute significant improvements of the best known upper bounds.
Luis Fernando DE MINGO, Nuria GÓMEZ, Juan CASTELLANOS Abstract. This paper presents some connectionist models that are widely used to solve NP-problems. This paper shows some ideas about how to incorporate a learning stage, based on self-organizing algorithms, in networks of evolutionary processors. T. Kohonen and P. Somervuo have shown that self organizing maps (SOM) are not restricted to numerical data. This paper proposes a symbolic measure that is used to implement a string self organizing map based on SOM algorithm. Such measure between two strings is a new string. Computation over strings is performed using a priority relationship among symbols, in this case, symbolic measure is able to generate new symbols. A complementary operation is defined in order to apply such measure to DNA strands. Finally, an algorithm is proposed in order to be able to implement a string self organizing map. This paper discusses the possibility of defining networks of evolutionary processors to rely on similarity instead of distance and shows examples of such networks for symbol strings.
Shenghua NI, Pan WANG, Mihaela PĂUN, Weizhong DAI, Andrei PĂUN Abstract. The segmentation of the picture (and, implicitly, the segmentation method used) is one of the three important steps in microarray image processing, together with spot gridding and information extraction. It directly affects the accuracy of gene expression analysis in the data mining process that follows. In 2001 a segmentation method for arbitrary pictures using the Active Contours Without Edges (ACWE) technique to detect the objects boundaries was proposed. In this paper we present a segmentation method based on ACWE with applications in cDNA segmenting. Because of the targeted nature of the method proposed we were able to perform several adjustments to the original method and use it in the cDNA microarray image processing area. We present various experiment results showing that the ACWE method is better than the other segmentation methods used in the cDNA microarray and that the results obtained match more closely (than the older methods) the biological cycle through correct gene expression measurements.
Alexandru SOFRONIA, Alexandru POPA, Gheorghe ŞTEFĂNESCU Abstract. A new approach to the design of massively parallel and interactive programming languages has been recently proposed using rv-systems (interactive systems with registers and voices) and Agapia programming. In this paper we present a few theoretical results on FISs (finite interactive systems), the underlying mechanism used for specifying control and interaction in these systems. First, we give a proof for the undecidability of the emptiness problem for FISs, by reduction to the Post Correspondence Problem. Next, we use the construction in this proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recognized by a FIS. Finally, we present a simple proof of the equivalence between FISs and tile systems, making explicit that they precisely capture recognizable two-dimensional languages. |