Wyniki wyszukiwania - BazTech

1

Oritatami System : a Survey and the Impossibility of Simple Simulation at Small Delays

Rogers T. A., Seki S.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

359--372

EN

RNA sequences start folding immediately as they are synthesized by RNA polymerase (cotranscriptional folding). The oritatami system (OS) is a novel mathematical model to study computational aspects of cotranscriptional folding. In this paper, we first provide a survey throughout existing research topics and results on oritatami systems and offer research directions of significance. Simulation of an oritatami system in a different ratio (delay) of transcription speed to the speed of folding is one of them. We will introduce a simple notion of simulation, and prove that there is an OS of delay δ that cannot be simulated by any oritatami system at larger delay.

2

Semilinear Sets and Counter Machines : a Brief Survey

Ibarra O. H., Seki S.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

61--76

EN

Semilinear sets are one of the most important concepts in theoretical computer science, as illustrated by the fact that the set of nonnegative integer solutions to any system of Diophantine equations is semilinear. Parikh’s theorem enables us to represent any semilinear set as a pushdown automaton (PDA).We summarize recent results on the descriptional complexity of conversions among different representations of a semilinear set: as a vector set (conventional), a finite automaton (FA), a PDA, etc.. We also discuss semilinearity-preserving operations like union, intersection, and complement. We use Parikh’s theorem to enlarge the class of finite-state machines that can represent semilinear sets. In particular, we give a simpler proof of a known result that characterizes semilinear sets in terms of machines with reversal-bounded counters. We then investigate the power of such a machine with only one counter in the context of a long-standing conjecture about repetition on words.

3

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.

4

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.

5

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.