Wyniki wyszukiwania - BazTech

1

Smart Tile Self-Assembly and Replication

Kari L., Simjour A.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

239--260

EN

We propose the concept of self-assembly of smart tiles, i.e., tiles which possess a local computational device in addition to having edge glues that can be activated or deactivated by signals. The local tile computational device can range from its being absent, to being a counter, a simple look-up table, a finite state machine, all the way to being a Turing machine. Thus, this model offers a general framework to discuss and compare various tile self-assembly systems. We demonstrate the potential of self-assembly with smart tiles to efficiently perform robotic tasks such as the replication of convex shapes. The smart tile assembly system that we propose for convex shape replication does not make any assumption on the glues and signals of the interior tiles of the input supertile, and uses a scaffold to assemble a replica adjacent to the input supertile.

2

A Formal Language Model of DNA Polymerase Enzymatic Activity

Enaganti S. K., Kari L., Kopecki S.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

179--192

EN

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.

3

Pseudopower Avoidance

Chiniforooshan E., Kari L., Xu Z.

Fundamenta Informaticae

|

2012

|

Vol. 114, nr 1

55-72

EN

Repetition avoidance has been intensely studied since Thue’s work in the early 1900's. In this paper, we consider another type of repetition, called pseudopower, inspired by theWatson-Crick complementarity property of DNA sequences. A DNA single strand can be viewed as a string over the four-letter alphabet {A,C,G, T }, whereinA is the complement of T , while C is the complement of G. Such a DNA single strand will bind to a reverse complement DNA single strand, called its Watson-Crick complement, to form a helical double-stranded DNA molecule. The Watson-Crick complement of a DNA strand is deducible from, and thus informationally equivalent to, the original strand. We use this fact to generalize the notion of the power of a word by relaxing the meaning of "sameness" to include the image through an antimorphic involution, the model of DNA Watson- Crick complementarity. Given a finite alphabet &Sigma: an antimorphic involution is a function Θ : Σ*→Σ* which is an involution, i.e., Θ2 equals the identity, and an antimorphism, i.e., Θ(uv) = Θ(v)Θ(u), for all u∈Σ* For a positive integer k, we call a word w a pseudo-kth-power with respect to Θ if it can be written as w = u1 . . . uk, where for 1 ≤ i, j ≤ k we have either ui = uj or ui = Θ(uj). The classical kth-power of a word is a special case of a pseudo-kth-power, where all the repeating units are identical. We first classify the alphabets Σ and the antimorphic involutions . for which there exist arbitrarily long pseudo-kth-power-free words. Then we present efficient algorithms to test whether a finite word w is pseudo-kth-power-free.

4

On the Regularity of Iterated Hairpin Completion of a Single Word

Kari L., Seki S., Kopecki S.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

201-215

EN

Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = xaya, and outputs w' = xayax, where x denotes the Watson- Crick complement of x. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words a and a that initiate hairpin completion and how they are scattered, we classify the set of all words w. For some basic classes of words w containing small numbers of occurrences of a and a, we prove that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of a and a, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.

5

K-Comma Codes and Their Generalizations

Cui B., Kari L., Seki S.

Fundamenta Informaticae

|

2011

|

Vol. 107, nr 1

1-18

EN

In this paper, we introduce the notion of k-comma codes - a proper generalization of the notion of comma-free codes. For a given positive integer k, a k-comma code is a set L over an alphabet Σ with the property that LΣ^kL ∩Σ^+LΣ^+ = ∅. Informally, in a k-comma code, no codeword can be a subword of the catenation of two other codewords separated by a "comma" of length k. A k-comma code is indeed a code, that is, any sequence of codewords is uniquely decipherable. We extend this notion to that of k-spacer codes, with commas of length less than or equal to a given k. We obtain several basic properties of k-comma codes and their generalizations, k-comma intercodes, and some relationships between the families of k-comma intercodes and other classical families of codes, such as infix codes and bifix codes. Moreover, we introduce the notion of n-k-comma intercodes, and obtain, for each k ≥ 0, several hierarchical relationships among the families of n-k-comma intercodes, as well as a characterization of the family of 1-k-comma intercodes.

6

An Improved Bound for an Extension of Fine and Wilf's Theorem and Its Optimality

Kari L., Seki S.

Fundamenta Informaticae

|

2010

|

Vol. 101, nr 3

215-236

EN

Considering two DNA molecules which are Watson-Crick (WK) complementary to each other "equivalent" with respect to the information they encode enables us to extend the classical notions of repetition, period, and power. WK-complementarity has been modelled mathematically by an antimorphic involution Θ i.e., a function Θ such that Θ(xy) = Θ(y)Θ(x) for any x, y ∈Σ and Θ^2 is the identity. The WK-complementarity being thus modelled, any word which is a repetition of u and Θ(u) such as uu, uΘ(u)u, and uΘ(u)Θ(u)Θ(u) can be regarded repetitive in this sense, and hence, called a -power of u. Taking the notion of Θ-power into account, the Fine and Wilf's theorem was extended as "given an antimorphic involution Θ and words u, v, if aΘ-power of u and a Θ-power of v have a common prefix of length at least b(|u|, |v|) = 2|u| + |v| - gcd(|u|, |v|), then u and v are Θ-powers of a same word." In this paper, we obtain an improved bound b'(|u|, |v|) = b(|u|, |v|) - .gcd(|u|, |v|)/2.. Then we show all the cases when this bound is optimal by providing all the pairs of words (u, v) such that they are not Θ-powers of a same word, but one can construct a Θ-power of u and a Θ-power of v whose maximal common prefix is of length equal to b'(|u|, |v|)-1. Furthermore, we characterize such words in terms of Sturmian words.

7

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.

8

Block Substitutions and Their Properties

Kari L., Losseva E.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

165-178

EN

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.

9

A Formal Language Analysis of DNA Hairpin Structures

Kari L., Losseva E., Konstantindis S., Sosik P., Thierrin G.

Fundamenta Informaticae

|

2006

|

Vol. 71, nr 4

453-475

EN

The concept of hairpin structures in formal languages is motivated from the biocomputing and bioinformatics fields. Hairpin (-free) DNA structures have numerous applications to DNA computing and molecular genetics in general. A word is called hairpin-free if it cannot be written in the form xvyq(v)z, with certain additional conditions, for an involution q (a function q with the property that q2 equals the identity function). A particular involution, the so-called Watson-Crick involution, can characterize binding of two DNA strands. We study algebraic and decision properties, finiteness and descriptional complexity of hairpin (-free) languages. We show an existence of polynomial-time algorithms deciding hairpin-freeness of regular and context-free sets. Two related DNA secondary structures are considered, taking into the account imperfect bonds (bulges, mismatches) and multiple hairpins. Finally, effective methods for design of long hairpin-free DNA words are given.

10

Results on Transforming NFA into DFCA

Câmpeanu C., Kari L., Păun A.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

53-63

EN

In this paper we consider the transformation from (minimal) non-deterministic finite automata (NFAs) to deterministic finite cover automata (DFCAs). We want to compare the two equivalent accepting devices with respect to their number of states; this becomes in fact a comparison between the expression power of the nondeterministic device and the expression power of the deterministic with loops device. We prove a lower bound for the maximum state complexity of deterministic finite cover automata obtained from non-deterministic finite automata of a given state complexity n, considering the case of a binary alphabet. We show, for such binary alphabets, that the difference between maximum blow-up state complexity of DFA and DFCA can be as small as [..]compared to the number of states of the minimal DFA. Moreover, we show the structure of automata for worst case exponential blow-up complexity from NFA to DFCA. We conjecture that the lower bound given in the paper is also the upper bound. Several results clarifying some of the structure of the automata in the worst case are given (we strongly believe they will be pivotal in the upper bound proof).