Wyniki wyszukiwania - BazTech

1

Patterns and Distances in Words Related to DNA Rearrangement

Jonoska N., Nabergall L., Saito M.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

225--238

EN

We initiate studies of patterns in words that appear as subwords (not necessarily factors) of words. A pattern is a string of variables, and we say that a pattern appears in a word if each variable can be morphically mapped to a factor in the word. We define pattern indices and distances between two words relative to a given set of patterns. The distance is defined as the minimal number of ‘pattern reductions’ that transfer one word into another. Motivated by patterns detected in certain scrambled ciliate genomes, we focus on double occurrence words (words where every symbol appears twice) and patterns in those words. Specifically, we show that in double occurrence words the distance relative to patterns αα (repeat words) and ααR (return words) is computable. We also compare some pattern indices of highly scrambled genes in O. trifallax relative to random sequences.

2

Involution Solid and Join codes

Jonoska N., Kari L., Mahalingam K.

Fundamenta Informaticae

|

2008

|

Vol. 86, nr 1-2

127-142

EN

In this paper we study a generalization of the classical notions of solid codes and comma-free codes: involution solid codes (q-solid) and involution join codes (q-join). These notions are motivated by DNA strand design where Watson-Crick complementarity can be formalized as an antimorphic involution. We investigate closure properties of these codes, as well as necessary conditions for q-solid codes to be maximal. We show how the concept of q-join can be utilized such that codes that are not themselves q-comma free can be split into a union of subcodes that are q-comma free.

3

Tree operations in P systems and [lambda]-calculus

Jonoska N., Margenstern M.

Fundamenta Informaticae

|

2004

|

Vol. 59, nr 1

67-90

EN

In this paper we introduce a membrane system (named lP systems) in which the computation is performed through certain operations on the tree structure of the membranes. The objects within the membranes play the role of catalysts for the operations. The result of the computation is the final configuration of the system. We show that lP systems can simulate pure l-calculus and so they have universal computational power. We also show that NP-complete problems can be solved in polynomial time in this way by showing that 3SAT is solvable in linear time with linear input.

4

Tissue-like P Systems with Active Membranes for Picture Generation

Ceterchi R., Gramatovici R., Jonoska N., Subramanian K.G.

Fundamenta Informaticae

|

2003

|

Vol. 56, nr 4

311-328

EN

We propose a variant of tissue-like P systems with symport rules and active membranes that generates two-dimensional picture languages. The method is unconventional in that, instead of using the membranes as regions for computation/writing, it uses them to hold elements of pictures. Thus, the picture itself, and actually the whole supporting rectangular grid, is composed of membranes, each one containing (among other symbols) a letter of the picture's alphabet. The method is illustrated by its application to the generation of local and recognizable picture languages.