Fundamenta Informaticae - Volume 64, issue 1-4

Authors: Krishna, Shankara Narayanan | Rama, R. | Ramesh, H.

Article Type: Research Article

Abstract: In this paper, we continue the study of contextual and rewriting P systems. In contextual P systems, we improve a universality result avoiding the extended feature and by using rules of small weight. In rewriting P systems, we have two (rather surprising) universality results, both of them using three membranes, for non-extended systems with replicated rewriting and with leftmost rewriting, respectively.

Keywords: P systems, contextual grammars, replicated rewriting, leftmost rewriting, recursively enumerable languages

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 241-253, 2005

Authors: Kudlek, Manfred

Article Type: Research Article

Abstract: A generalization of contextual grammars by adding probabilities is introduced, enriching the generative power of such grammars. An example exhibits a non-contextual, even not context-free language.

Keywords: Contextual grammar, probabilistic grammar, multiset

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 255-260, 2005

Authors: Manca, Vincenzo

Article Type: Research Article

Abstract: The double stranded structure of DNA molecules is investigated in an abstract setting. Only the general structure of bilinear strings is taken into account regardless of specific physical and biochemical aspects of DNA molecules. In this context, the principles which DNA processes are based on are formulated in an abstract form. Surprisingly enough, some intrinsic features of DNA molecules turn out to be implied by these general principles.

Keywords: DNA structure, bilinearity, complementarity, antiparallelism, DNA helix, DNA computing

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 261-273, 2005

Authors: Mardare, Radu | Priami, Corrado

Article Type: Research Article

Abstract: Our paper proposes a technique for performing logical analysis over the calculi for communication and mobility, i.e., Ambient Calculus type of calculi. We show how this analysis can be used in the case of biological models in order to obtain significant information for biologists. The technique is based on set theoretical models we developed for ambient processes by using the power of Hypersets Theory. These models are further used as possible worlds in a Kripke structure organized for …a propositional branching temporal logic. Providing the temporal logical structure for the accessibility relation between ambient processes, we open the perspective of reusing model checking algorithms developed for temporal logics in analyzing any phenomena that can be described by these calculi. Show more

Keywords: Hypersets, process algebra, ambient calculus, temporal logics, model checking

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 275-289, 2005

Authors: Margenstern, Maurice | Verlan, Sergey | Rogozhin, Yurii

Article Type: Research Article

Abstract: Time-varying distributed H systems are a well known model of molecular computing. In this article we present an overview of this model, its history, related results, and open problems.

Keywords: Biomolecular computing, splicing systems, formal grammars

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 291-306, 2005

Authors: Mitrana, Victor

Article Type: Research Article

Abstract: This work is a continuation of [9]. We extend the multi-dimensional external contextual grammars introduced in the aforementioned work with the possibility of adjoining contexts in a selective way. An investigation of some mathematical properties (computational power and recognition complexity) of these new variants of contextual grammars is done via a constant comparison with the corresponding properties of classic Marcus external contextual grammars with or without choice.

Keywords: External contextual grammars, multi-dimensional external contextual grammars, range concatenation grammars

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 307-316, 2005

Authors: Mutyam, Madhu | Krithivasan, Kamala | Reddy, A. Siddhartha

Article Type: Research Article

Abstract: Insertion grammars have been introduced in [1] and their computational power has been studied in several places. In [7] it is proved that insertion grammars with weight at least 7 can characterize recursively enumerable languages (modulo a weak coding and an inverse morphism), and the question was formulated whether or not this result can be improved. In this paper, we come up with a positive answer to this question, by decreasing the weight of the insertion …grammar used to 5. We also give a characterization of recursively enumerable languages in terms of right quotients of insertion languages. Show more

Keywords: Insertion grammar, contextual grammar, recursively enumerable languages, Penttonen normal form, Kuroda normal form

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 317-324, 2005

Authors: Novotný, Miroslav

Article Type: Research Article

Abstract: The concept of a contextual grammar is slightly generalized here; the generalized grammars called contextual hypergrammars admit to introduce the so called reducing operators. Using some results concerning these operators a construction is described assigning a contextual grammar G_n (V,L) to any language (V,L) and to any nonnegative integer n. This construction has the following property: The language (V,L) is generated by a contextual grammar if and only if there exists a nonnegative …integer n_0 such that G_n =G_{n_0} (V,L) for any n ≥ n_0 . Show more

Keywords: Contextual hypergrammar, contextual grammar, reducing operator

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 325-340, 2005

Authors: Okhotin, Alexander | Salomaa, Kai

Article Type: Research Article

Abstract: A uniformcontextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the nonuniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.

Keywords: Contextual grammar, trajectory, regular language, context-free language

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 341-351, 2005

Authors: Păun, Gheorghe | Pérez-Jiménez, Mario J. | Pazos, Juan | Rodríguez-Patón, Alfonso

Article Type: Research Article

Abstract: The operations of symport and antiport, directly inspired frombiology, are already known to be rather powerful when used in the framework of P systems. In this paper we confirm this observation with a quite surprising result: P systems with symport/antiport rules using only three objects can simulate any counter machine, while systems with only two objects can simulate any blind counter machine. In the first case, the universality (of generating sets of numbers) is obtained also …for a small number of membranes, four. Show more

Keywords: Membrane computing, Turing computability, register machine, symport/antiport

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 353-367, 2005

Authors: Pawlak, Zdzisław

Article Type: Research Article

Abstract: This paper concerns a new approach to intelligent data analysis based on information flow distribution study in a flow graph. Branches of a flow graph are interpreted as decision rules, whereas a flow graph is supposed to describe a decision algorithm. We propose to model decision processes as flow graphs and analyze decisions in terms of flow spreading in a graph.

Keywords: Flow graphs, data mining, information flow, intelligent data analysis, Bayes' rule

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 369-377, 2005

Authors: Polkowski, Lech | Semeniuk-Polkowska, Maria

Article Type: Research Article

Abstract: In this paper, dedicated to Professor Solomon Marcus on the occasion of His 80th birthday, we discuss the idea of intensional many-valued logic reflecting the logical content of rough set approach to analysis and treatment of uncertainty. In constructing the variety of logics presented in the paper, we make use of a certain kind of tolerance (similarity) relations called rough mereological tolerances. A study of tolerance relations that arise in rough set environments was initiated in …1994, with the paper [23], in which basic ideas pertaining to tolerance relations in the rough set framework were pointed to. The analysis of the role tolerance relations may play in machine learning based on rough set-theoretic ideas was carried out by Professor Solomon Marcus in His seminal paper, written during His stay in Warsaw in December of the year 1994. At the same time the first author had first ideas related to the applicability of ideas of mereology in the rough set analysis of uncertainty. In a later analysis it has turned out that mereological approach has led to a development of a new paradigm in reasoning under uncertainty, called rough mereology, proposed by Lech Polkowski and Andrzej Skowron. Within this paradigm, one is able to construct a variety of tolerance relations. Those tolerance relations, induced by rough mereological constructs called rough inclusions, serve as a basis for constructing a variety of logics, called rough mereological logics, that are related to the inherent structure of any rough set universe. In this paper, we introduce gradually all essential and necessary notions from the area of rough set theory, mereology and rough mereology, and then we discuss tolerance relations induced by rough inclusions along with some methods for inducing rough inclusions with desired properties. The paper culminates with a discussion of intensional logics based on rough mereological tolerance relations. In this way, we explore one of so many paths in scientific research, that have been either pointed to or threaded by Professor Solomon Marcus. Show more

Keywords: rough mereology, logics for rough sets, similarity relations

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 379-390, 2005

Authors: Salomaa, Arto

Article Type: Research Article

Abstract: We investigate the number of (scattered) subword occurrences and Parikh matrices, especially the case where the matrix determines the word uniquely. A condition introduced in this paper, called γ-property, turns out to be a powerful tool for such unambiguous matrices. Interconnections with the general theory of subword histories are also pointed out.

Keywords: Subword, scattered subword, number of subwords, Parikh matrix, ambiguity

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 391-404, 2005

Authors: Scollo, Giuseppe

Article Type: Research Article

Abstract: The Collatz problem is comprised of two distinct, separate questions: existence of eventually periodic Collatz reductions with a nontrivial period, and existence of period-free Collatz reductions. This paper introduces a few distinct, related formalizations of the Collatz dynamics as term rewriting systems, using elementary concepts from the theory of state transition dynamics. Some of the subject systems act on finite terms, whereas others rewrite terms that are endowed with a countable, recursively defined …structure. The latter presents a convenient framework for the investigation of extensions of the Collatz dynamics to dense systems. Show more

Keywords: state transition dynamics, attractor, periodicity, quasiperiodicity, infinitary rewriting

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 405-416, 2005

Authors: Skowron, Andrzej

Article Type: Research Article

Abstract: The approximation space definition has evolved in rough set theory over the last 15 years. The aim was to build a unified framework for concept approximations. We present an overview of this evolution together with some operations on approximation spaces that are used in searching for relevant approximation spaces. Among such operations are inductive extensions and granulations of approximation spaces. We emphasize important consequences of the paper for research on approximation of vague concepts and reasoning …about them in the framework of adaptive learning. This requires developing new approach to vague concepts going beyond the traditional rough or fuzzy approaches. Show more

Keywords: vague concept approximation, reasoning about vague concepts, approximation spaces, rough sets, inductive extensions, granulation of approximation spaces, adaptive learning

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 417-431, 2005

Authors: Tatar, Doina

Article Type: Research Article

Abstract: There is a renewed interest in word sense disambiguation (WSD) as it contributes to various applications in natural language processing. In this paper we survey vector-based methods for WSD in machine learning. All the methods are corpus-based and use definition of context in the sense introduced by S. Marcus [11].

Keywords: Word sense disambiguation, machine learning, context

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 433-442, 2005

Authors: Titchener, Mark R. | Nicolescu, Radu | Staiger, Ludwig | Gulliver, Aaron | Speidel, Ulrich

Article Type: Research Article

Abstract: Lempel and Ziv (1976) proposed a computable string production-complexity. In this paper, our emphasis is on providing the rigorous development, where possible, for the theoretical aspects of a more recent and contrasting measure of string complexity. We derive expressions for complexity bounds subject to certain constraints. We derive an analytic approximation to the upper bound to linearize the complexity measure. The linearized measure enables us to propose an entropy measure, observed elsewhere to correspond …closely with the Kolmogorov-Sinai entropy in simple dynamical systems. Show more

Keywords: Formal languages, generative systems, prefix codes, complexity measures, T-codes, entropy, information

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 443-461, 2005

Authors: Tomescu, Ioan

Article Type: Research Article

Abstract: Let A be an alphabet of cardinality m, k_n be a sequence of positive integers and ω∈ A* (|ω|=k_n ). In this paper it is shown that if lim sup_{n&rarr;&infin;} k_n /ln n<1/ln m, then almost all words of length n over A contain the factor ω, but if lim sup_{n&rarr;&infin;} k_n /ln n>1/ln m, then this property is not true. Also, if lim inf_{n&rarr;&infin;} …k_n /ln n>1/ln m, then almost all words of length n over A do not contain the factor ω. Moreover, if lim_{n&rarr;&infin;} (ln n-k_n ln m)=α∈ R, then lim sup_{n&rarr;&infin;} |W(n,k_n ,ω,A)| /m^m ≤1−exp (−exp(α)) and lim inf_{n&rarr;&infin;} |W (n, k_n ,ω,A)|/m^n ≥1−exp (−(1−1/m) exp(α)), where W(n, k_n , ω, A) denotes the set of words of length n over A containing the factor ω of length k_n . Show more

Keywords: Word, factor, recurrence relation, characteristic equation, pseudo-Vandermonde determinant, autocorrelation polynomial, generating function

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 463-470, 2005

Authors: Yu, Sheng

Article Type: Research Article

Abstract: In this paper, we summarize recent results and progress in state complexity research. We analyze why many basic state complexity problems were not solved earlier, in the sixties and seventies. We also suggest several future directions for this area of research.

Keywords: State complexity, regular languages, finite languages, finite automata

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 471-480, 2005