Wyniki wyszukiwania - BazTech

1

Characterizing DNA Bond Shapes Using Trajectories

Domaratzki M.

Fundamenta Informaticae

|

2008

|

Vol. 87, nr 3-4

269-285

EN

We consider the use of DNA trajectories to characterize DNA bond shapes. This is an extension of recent work on the bond-free properties of a language. Using a new definition of bondfreeness, we show that we can increase the types of DNA bond shapes which are expressible. This is motivated by the types of bond shapes frequently found in DNA computing. We examine the algebraic properties of sets of DNA trajectories. In particular, we consider rotation of trajectories and weakening of the bonding conditions expressed by a set of DNA trajectories. We also consider decidability results for bond-freeness with respect to our definition.

2

Interpreted Trajectories

Domaratzki M., Rozenberg G., Salomaa K.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

81-97

EN

We introduce generalized trajectories where the individual symbols are interpreted as operations performed on the operand words. The various previously considered trajectory-based operations can all be expressed in this formalism. It is shown that the generalized operations can simulate Turing machine computations. We consider the equivalence problem and a notion of unambiguity that is sufficient to make equivalence decidable for regular sets of trajectories under nonincreasing interpretations.

3

Trajectory-Based Embedding Relations

Domaratzki M.

Fundamenta Informaticae

|

2004

|

Vol. 59, nr 4

349--363

EN

We generalize the embedding order to shuffle on trajectories and examine its properties. We give general characterizations of reflexivity, transitivity, anti-symmetry and other properties of binary relations, and investigate the associated decision problems. We also examine the property of convexity of a language with respect to these generalized embedding relations.

4

One-Visit Caterpillar Tree Automata

Okhotin A., Salomaa K., Domaratzki M.

Fundamenta Informaticae

|

2002

|

Vol. 52, nr 4

361-375

EN

We study caterpillar tree automata [3] that are restricted to enter any subtree at most one time (or k times). We show that, somewhat surprisingly, the deterministic one-visit automata can already, for instance, evaluate trees where the nodes represent some non-associative operations. We show that there exist regular tree languages that cannot be accepted by a one-visit automaton, thus proving a weakened form of a conjecture of Brüggemann-Klein and Wood [3]. We establish that the k-visit property is decidable.