Fundamenta Informaticae - Volume 138, issue 1-2

Authors: Ivanov, Sergiu | Verlan, Sergey

Article Type: Research Article

Abstract: In this article we introduce the operations of insertion and deletion working in random context and semi-conditional modes. We show that conditional application of insertion and deletion rules strictly increases the computational power. In the case of semi-conditional insertion-deletion systems, context-free insertion and deletion rules of one symbol are sufficient to achieve computational completeness. In the random context case, our results expose asymmetry between the computational power of insertion and deletion rules: semi-conditional systems of size (2, 0, 0; 1, 1, 0) (with context-free two-symbol insertion rules, and one-symbol deletion rules with one-symbol left context) are computationally complete, while systems …of size (1, 1, 0; 2, 0, 0) (and, more generally, of size (1, 1, 0; p, 1, 1)) are not. Show more

Keywords: Insertion-deletion, random-context, computational (in)completeness

DOI: 10.3233/FI-2015-1203

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 127-144, 2015

Authors: Rogojin, Vladimir | Petre, Ion

Article Type: Research Article

Abstract: We consider in this paper the assembly of micronuclear genes in stichotrichous ciliates to their macronuclear form. We represent the micronuclear genes and all their intermediate forms from micro- to macro- as signed permutations, where integer i stands for the i-th MDS of the macronuclear gene and ī stands for the inverted form of that MDS; the macronuclear assembled gene is represented as the sorted permutation 1 2 . . . n, while its micronuclear form is an arbitrary signed permutation. We focus on the elementary gene assembly model consisting of two operations on signed permutations: eh (elementary hairpin inverting) …and ed (elementary double recombination); gene assembly is modeled in this framework as a permutation sorting process. The general problem we investigate is to give a characterization of all signed permutations that can be sorted by the elementary operations. We make progress towards a full solution for this problem by relating sequences of eh and ed operations applicable to a given permutation to paths in the dependency graph associated to that permutation. Show more

DOI: 10.3233/FI-2015-1204

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 145-158, 2015

Authors: Choffrut, Christian | Grigorieff, Serge

Article Type: Research Article

Abstract: We consider the first-order theory of the monoid P(A*) of languages over a finite or infinite alphabet A (with at least two letters) endowed solely with concatenation lifted to sets: no set theoretical predicate or function, no constant. Coding a word u by the submonoid u* it generates, we prove that the operation (u*, v*) → (uv)* and the predicate {(u*,X) | ε ∈ X, u ∈ X} are definable in 〈P(A*); ·,=〉. This allows to interpret the second-order theory of 〈A*; ·,=〉 in the first-order theory of 〈P(A*); ·,=〉 and prove the undecidability of the Π8 fragment of …this last theory. These results involve technical difficulties witnessed by the logical complexity of the obtained definitions: the above mentioned predicates are respectively Δ5 and Δ7 . Show more

DOI: 10.3233/FI-2015-1205

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 159-177, 2015

Authors: Enaganti, Srujan Kumar | Kari, Lila | Kopecki, Steffen

Article Type: Research Article

Abstract: We propose and investigate a formal language operation inspired by the naturally occurring phenomenon of DNA primer extension by a DNA-template-directed DNA Polymerase enzyme. Given two DNA strings u and v, where the shorter string v (called primer) is Watson-Crick complementary and can thus bind to a substring of the longer string u (called template) the result of the primer extension is a DNA string that is complementary to a suffix of the template which starts at the binding position of the primer. The operation of DNA primer extension can be abstracted as a binary operation on two formal languages: …a template language L1 and a primer language L2 . We call this language operation L1 -directed extension of L2 and study the closure properties of various language classes, including the classes in the Chomsky hierarchy, under directed extension. Furthermore, we answer the question under what conditions can a given language of target strings be generated from a given template language when the primer language is unknown. We use the canonic inverse of directed extension in order to obtain the optimal solution (the minimal primer language) to this question. Show more

DOI: 10.3233/FI-2015-1206

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 179-192, 2015

Authors: Csuhaj-Varjú, Erzsébet | Gheorghe, Marian | Stannett, Mike | Vaszil, György

Article Type: Research Article

Abstract: In this paper we investigate the use of general topological spaces in connection with a generalised variant of membrane systems. We provide an approach which produces a fine grain description of local operations occurring simultaneously in sets of compartments of the system by restricting the interactions between objects. This restriction is given by open sets of a topology and multisets of objects associated with them, which dynamically change during the functioning of the system and which together define a notion of vicinity for the objects taking part in the interactions.

Keywords: Membrane systems, computational power, topology, open sets

DOI: 10.3233/FI-2015-1207

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 193-205, 2015

Authors: Muravitsky, Alexei Y.

Article Type: Research Article

Abstract: We propose a framework in terms of domain theory for semantic information models. We show how an artificial agent (the computer) can operate within such a model in a multiple attitude environment (fuzziness) where information is conveyed. We illustrate our approach by two examples — taking as the set of the degrees of reliability Kleene's 3-valued strong logic and Belnap-Dunn's 4-valued logic.

Keywords: semantic information, complete semilattice, domain, upper powerdomain, Scott-continuous function

DOI: 10.3233/FI-2015-1208

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 207-225, 2015

Authors: Alhazov, Artiom | Freund, Rudolf

Article Type: Research Article

Abstract: Computational completeness is known for P systems with two catalysts and purely catalytic P systems with three catalysts as well as for P systems with one bi-stable catalyst. We complete this picture by showing computational completeness for purely catalytic P systems with one bi-stable catalyst and one catalyst. Moreover, we present some concrete universal P systems, e.g., for P systems with one multi-stable catalyst and for P systems with multiple catalysts. Furthermore, we optimize the descriptional complexity of Minsky's reduction from register machines with an arbitrary number of registers to register machines with only two registers. In that way, we …are able to transform the universal machines U22 and U20 of Korec into weakly universal register machines with only two decrementable registers, one even with unencoded output. Based on these universal register machines, we then construct small universal P systems with one bi-stable catalyst and one catalyst as well as small universal purely catalytic P systems with three catalysts. With respect to the number of rules, the smallest universal P systems can be obtained with multi-stable catalysts and with multiple catalysts. The number of rules in all these systems can be further reduced by adding the concept of toxic objects (a specified subset of objects), where all computation branches not evolving all toxic objects in every computation step do not yield a result. Show more

DOI: 10.3233/FI-2015-1209

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 227-250, 2015

Authors: Woods, Damien | Neary, Turlough

Article Type: Research Article

Abstract: In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don't yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii's other contributions to the field, including his work with Manfred …Kudlek on small circular Post machines. Show more

DOI: 10.3233/FI-2015-1210

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 251-258, 2015

Authors: Sutner, K.

Article Type: Research Article

Abstract: We discuss simple functional transductions defined by invertible Mealy automata under iteration and in particular the question when the orbit relation defined by iteration is rational. We identify a class of these automata that has relatively complicated orbits, yet some of them are still orbit rational and discuss a number of decision problems associated with these devices.

DOI: 10.3233/FI-2015-1211

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 259-272, 2015

Article Type: Research Article

DOI: 10.3233/FI-2015-1212

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 273-284, 2015