Fundamenta Informaticae - Volume 73, issue 1-2

Authors: Halava, Vesa | Harju, Tero | Karhumäki, Juhani

Article Type: Research Article

Abstract: In the infinite Post Correspondence Probleman instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word α such that h(α)=g(α). In the general case this problemwas shown to be undecidable by K. Ruohonen (1985). Recently, it was proved that the infinite PCP is undecidable already when the domain alphabet of the morphisms consists of at least 9 letters. Here we show that the …problem is undecidable for instances where the morphisms have a domain of 6 letters, when we restrict to solutions of ω-languages of the form R^{ω} where R is a given regular language. Show more

Keywords: Post Correspondence Problem, infinite word, semi-Thue system, regular language, undecidability

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 119-125, 2006

Authors: Honkala, Juha

Article Type: Research Article

Abstract: We show that it is undecidable whether or not a given N-rational series assumes all nonnegative values. As a consequence we see that it is undecidable whether the image of a given N-rational series equals the image of a given N-rational sequence. We discuss also related results concerning DT0L and D0L length sets.

Keywords: N-rational series, decidability

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 127-132, 2006

Authors: Ibarra, Oscar H. | Woodworth, Sara | Yen, Hsu-Chun | Dang, Zhe

Article Type: Research Article

Abstract: The original definition of P systems calls for rules to be applied in a maximally parallel fashion. However, in some cases a sequential model may be a more reasonable assumption. Here we study the computational power of different variants of sequential P systems. Initially we look at cooperative systems operating on symbol objects and without prioritized rules, but which allow membrane dissolution and bounded creation rules. We show that they are equivalent to vector addition systems …and, hence, nonuniversal. When these systems are used as language acceptors, they are equivalent to communicating P systems which, in turn, are equivalent to partially blind multicounter machines. In contrast, if such cooperative systems are allowed to create an unbounded number of new membranes (i.e., with unbounded membrane creation rules) during the course of the computation, then they become universal. We then consider systems with prioritized rules operating on symbol objects. We show two types of results: there are sequential P systems that are universal and sequential P systems that are nonuniversal. In particular, both communicating and cooperative P systems are universal, even if restricted to 1-deterministic systems with one membrane. However, the reachability problem for multi-membrane catalytic P systems with prioritized rules is NP-complete and, hence, these systems are nonuniversal. Show more

Keywords: Sequential P system, 1-deterministic P system, communicating P system, catalytic system, vector addition system, partially blind counter machine

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 133-152, 2006

Authors: Ilie, Lucian | Popescu, Cristian

Article Type: Research Article

Abstract: Viruses compress their genome to reduce space. One of the main techniques is overlapping genes. We model this process by the shortest common superstring problem. We give an algorithm for computing optimal solutions which is slow in the number of strings but fast (linear) in their total length. This algorithm is used for a number of viruses with relatively few genes. When the number of genes is larger, we compute approximate solutions using the greedy algorithm …which gives an upper bound for the optimal solution. We give also a lower bound for the shortest common superstring problem. The results obtained are then compared with what happens in nature. Remarkably, the compression obtained by viruses is very close to the one achieved by modern computers. Show more

Keywords: Virus, viral genome, genome compression, overlapping genes, shortest common superstring problem, approximate solution, lower bound

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 153-164, 2006

Authors: Kari, Lila | Losseva, Elena

Article Type: Research Article

Abstract: We introduce a type of substitution operation inspired by errors occurring in biologically encoded information. We derive the closure properties of language families in the Chomsky hierarchy under these substitution operations. Moreover, we consider some language equations involving these operations and investigate decidability of the existence of solutions to such equations.

Keywords: Formal languages, Chomshy hierarchy, block substitution

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 165-178, 2006

Authors: Langille, Miika | Petre, Ion

Article Type: Research Article

Abstract: We investigate in this paper a simple intramolecular model for gene assembly in ciliates. Unlike the general intramolecular model, the folds that a micronuclear chromosome may form to assemble the genes is very restricted (minimal) here: between any two pointers there may be at most one coding block. It has been known that the general model is universal, being able to assemble any gene pattern (to sort any signed permutation). The simple model on the other …hand is not universal: there exist signed permutations that cannot be sorted in this model. Remarkably though, all known micronuclear gene patterns in ciliates can indeed be assembled in the simple model. We prove in this paper that while the general model is non-deterministic, the simple model is "weakly deterministic": any gene pattern either has only successful or only unsuccessful sorting strategies. Moreover, although different strategies may lead to different permutations for the same input, these final results have the same structure. Show more

Keywords: Gene assembly, signed permutations, simple operations, determinism

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 179-190, 2006

Authors: Manea, Florin | Mitrana, Victor | Voinescu, Daniel-Claudian

Article Type: Research Article

Abstract: In this paper we continue the study on synchronized shuffle started in [5] by introducing the condition that the two words which are to be shuffled have to synchronize on a predefined set of backbones. As far as the language-theoretic properties of this operation are concerned, we prove that in a trio the closure under shuffle is equivalent to the closure under synchronized shuffle on a regular set of backbones. Based on this result we show …that a set of backbones is regular if and only if the synchronized shuffle of every two regular languages on that set is also regular. Some relationships between this operation and the synchronized shuffle operations introduced in [5] are presented and some open problem are finally discussed. Show more

Keywords: Shuffle, synchronized shuffle, backbone, synchronized shuffle on backbones, formal languages

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 191-202, 2006

Authors: Marcus, Solomon

Article Type: Research Article

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 203-204, 2006

Authors: Mateescu, Alexandru | Freund, Rudolf

Article Type: Research Article

Abstract: We investigate the problem of finding monoids that recognize languages of the form L_1 ⋈_T L_2 where T is an arbitrary set of routes. We present a uniform method based on routes to find such monoids. Many classical operations from the theory of formal languages, such as catenation, bi-catenation, simple splicing, shuffle, literal shuffle, and insertion are shown to be just particular instances of the operation ⋈_T …. Show more

Keywords: Monoid, route, Schützenberger product, shuffle

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 205-211, 2006

Authors: Păun, Gheorghe | Păun, Radu

Article Type: Research Article

Abstract: With inspiration from the economic reality, where numbers are basic entities to work with, we propose a genuinely new kind of P systems, where numerical variables evolve, starting from initial values, by means of production functions and repartition protocols. We prove that non-deterministic systems of this type, using polynomial production functions, characterize the Turing computable sets of natural numbers, while deterministic systems, with polynomial production functions having non-negative coefficients, compute strictly more …than semilinear sets of natural numbers. A series of research topics to be addressed in this framework are mentioned. Show more

Keywords: Membrane computing, economics, Turing computability, universality

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 213-227, 2006

Authors: Paz, Azaria

Article Type: Research Article

Abstract: The relationship between graphoid independency relations (defined in the text) and such relations induced by Probabilistic Distributions (PD) with binary random variables is investigated. It is shown that there are axioms that are sound for a subset of PD-induced relations with binary variables and are independent of the Graphoid axioms (cannot be logically derived from those axioms).

Keywords: Graphoids, probabilistic distributions, independency relations

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 229-236, 2006

Authors: Santean, Nicolae | Yu, Sheng

Article Type: Research Article

Abstract: Bimachines are important conceptual tools used for the characterization of rational word functions (realized by single-valued transducers). Despite the attention received in the past, these sequential machines are far from being exhaustively studied. A natural question which has not been addressed so far is what family of transductions are realized by bimachines that operate nondeterministically. We show that these machines characterize input-unambiguous (IU) rational transductions, i.e., those transductions that can be written …as a composition of rational functions and finite substitutions. Two more families of rational transductions are defined and related in a natural way to IU transductions: input-deterministic transductions and rational transductions with finite codomain (FC). We have shown that FC transductions are recognizable and that they can be expressed as finite union of subsequential functions. Moreover, they can be realized by nondeterministic bimachines. Finally, we have defined the so called restricted nondeterministic bimachines and shown that, surprisingly, they are more powerful than nondeterministic bimachines: they characterize exactly the family of finitely ambiguous rational transductions. Show more

Keywords: Finite transducer, unambiguous automaton, nondeterministic bimachine, rational function, finite substitution

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 237-264, 2006

Authors: Şerbănuţă, Virgil Nicolae | Şerbănuţă, Traian Florin

Article Type: Research Article

Abstract: We deal with the notion of M-unambiguity [5] in connection with the Parikh matrix mapping introduced by Mateescu and others in [7]. M-unambiguity is studied both in terms of words and matrices and several sufficient criteria for M-unambiguity are provided in both cases, nontrivially generalizing the criteria based on the γ-property introduced by Salomaa in [15]. Also, the notion of M-unambiguity with respect to a word is defined in connection with the extended Parikh matrix morphism …[16] and some of the M-unambiguity criteria are lifted from the classical setting to the extended one. This paper is a revised and extended version of [17]. Show more

Keywords: Subword, scattered subword, Parikh matrix, ambiguity

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 265-283, 2006

Authors: Stefanescu, Gheorghe

Article Type: Research Article

Abstract: We present a model and a core programming language appropriate for modeling and programming interactive computing systems. The model consists of rv-systems (interactive systems with registers and voices); it includes register machines, is space-time invariant, is compositional, may describe computations extending in both time and space, and is applicable to open, interactive systems. To achieve modularity in space the model uses voices (a voice is the time dual of a register) – they provide a high …level organization of temporal data and are used to describe interaction interfaces of processes. The programming language uses novel techniques for syntax and semantics to support computation in space paradigm. We describe rv-programs and base their syntax and operational semantics on FIS-es (finite interactive systems) and their grid languages (a FIS is a kind of 2-dimensional automaton specifying both control and interaction used in rv-programs). We also present specification techniques for rv-systems, using relations between input registers and voices and their output counterparts. The paper includes simple specifications for an OO-system and for an interactive game. Show more

Keywords: Interactive systems, programming languages, syntax, semantics, temporal specifications, registers, voices, object-oriented systems, finite interactive systems, rv-systems, rv-programs, grids, space-time duality

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 285-305, 2006

Authors: Vaida, Dragoş

Article Type: Research Article

Abstract: This note begins a study of some elementary properties related to the order structures applied in the algebraic approach to processes semantics. The support examples come from the partially additive semantics developed by Steenstrup (1985) and Manes and Arbib (1986) and from process algebra of Baeten and Weijland (1990). The main sources for the algebraic theory are F.A. Smith (1966) and Golan (1999). We show that different properties can be extended to partially additive distributive algebras …more general than sum-ordered partial semirings. One establishes that the support examples constitute multilattices, in the sense of Benado (1955). By the examples, the ordering considered, and the references, this preliminary study is related to Rudeanu et al. (2004) and to the algebraic approach to languages due to Mateescu, e.g., (1996), (1989), (1994). Show more

Keywords: Partial additive semantics, process algebra, semirings

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 307-319, 2006