Nataša Jonoska

TCS Journal 2017 Journal Article

A graph isomorphism condition and equivalence of reaction systems

• Daniela Genova
• Hendrik Jan Hoogeboom
• Nataša Jonoska

We consider global dynamics of reaction systems as introduced by Ehrenfeucht and Rozenberg. The dynamics is represented by a directed graph, the so-called transition graph, and two reaction systems are considered equivalent if their corresponding transition graphs are isomorphic. We introduce the notion of a skeleton (a one-out graph) that uniquely determines a directed graph. We provide the necessary and sufficient conditions for two skeletons to define isomorphic graphs. This provides a necessary and sufficient condition for two reactions systems to be equivalent, as well as a characterization of the directed graphs that correspond to the global dynamics of reaction systems.

I&C Journal 2015 Journal Article

Existence of constants in regular splicing languages

• Paola Bonizzoni
• Nataša Jonoska

In spite of wide investigations of finite splicing systems in formal language theory, basic questions, such as their characterization, remain unsolved. It has been conjectured that a necessary condition for a regular language L to be a splicing language is that L must have a constant in the Schützenberger sense. We prove this longstanding conjecture to be true. The result is based on properties of strongly connected components of the minimal deterministic finite state automaton for a regular splicing language. Using constants of the corresponding languages, we also provide properties of transitive automata and path-automata.

TCS Journal 2012 Journal Article

Forbidding and enforcing on graphs

• Daniela Genova
• Nataša Jonoska

We define classes of graphs based on forbidding and enforcing boundary conditions. Forbidding conditions prevent a graph to have certain combinations of subgraphs and enforcing conditions impose certain subgraph structures. We say that a class of graphs is an fe-class if the class can be defined through forbidding and enforcing conditions (fe-system). We investigate properties of fe-systems and characterize familiar classes of graphs such as paths and cycles, trees, bi-partite, complete, Eulerian, and k -regular graphs as fe-classes.

TCS Journal 2012 Journal Article

Rewriting rule chains modeling DNA rearrangement pathways

• Angela Angeleska
• Nataša Jonoska
• Masahico Saito

We introduce a model that describes rearrangement pathways of DNA recombination events. The recombination processes may happen in a succession, possibly with some recombination events performed simultaneously, but others in a prescribed order. These events are modeled by three rewriting rules applied on a set of formal linear and circular words. We define a partial order on these sets in such a way that two sets are related by this order when molecules represented by one are produced by recombination events from the other. We apply our model to experimental data obtained for DNA rearrangement of the actin I gene in O. trifallax ciliates, and we predict possible pathways of gene rearrangement compatible with the data.

TCS Journal 2009 Journal Article

Complexity classes for self-assembling flexible tiles

• Nataša Jonoska
• Gregory L. McColm

We present a theoretical model for self-assembling DNA tiles with flexible branches. We encode an instance of a “problem” as a pot of such tiles for which a “solution” is an assembled complete complex without any free sticky ends. Using the number of tiles in an assembled complex as a measure of complexity we show how NTIME classes (such as NP and NEXP) can be represented with corresponding classes of the model.

TCS Journal 2009 Journal Article

Finite state automata representing two-dimensional subshifts

• Nataša Jonoska
• Joni B. Pirnot

A new type of two-dimensional automaton has been defined to recognize a class of two-dimensional shifts of finite type having the property that every admissible block found within the related local picture language can be extended to a point of the subshift. Here it is shown that this automaton accurately represents the image of the represented two-dimensional shift of finite type under a block code. It is then shown that these automata can be used to check for a certain type of two-dimensional transitivity in the factor language of the corresponding shift space and how this relates to periodicity in the two-dimensional case. The paper closes with a notion of “follower sets” that are used to reduce the size of the automata representing two-dimensional sofic shifts.

TCS Journal 2009 Journal Article

On existence of reporter strands in DNA-based graph structures

• Nataša Jonoska
• Nadrian C. Seeman
• Gang Wu

Through self-assembly of branched junction molecules many different DNA structures (graphs) can be assembled. We show that every multigraph can be assembled by DNA such that there is a single strand that traces each edge in the graph at least once. This strand corresponds to a boundary component of a two-dimensional orientable surface that has the given graph as a deformation retract. This boundary component traverses every edge at least once, and it defines a circular path in the graph that “preserves the graph structure” and traverses each edge.

TCS Journal 2009 Journal Article

Preface

• Nataša Jonoska
• Jarkko Kari

TCS Journal 2009 Journal Article

Preface

• Nataša Jonoska
• Jarkko Kari

TCS Journal 2001 Journal Article

Multiplicities of covers for sofic shifts

• Doris Fiebig
• Ulf-Rainer Fiebig
• Nataša Jonoska

We consider a transitive sofic shift T and a SFT cover f: S→T. We define the multiplicity of the cover (S, f) to be the largest number of preimages of a point. The intrinsic multiplicity of T is the minimum of the multiplicities over all covers of T, denoted by m(T). Is m(T) computable? We do not answer this question. However the attempt to solve this problem led us to find sharp estimates for the intrinsic multiplicity, sharpen a result of Williams, and solve a problem posed by Trow.

TCS Journal 1996 Journal Article

Sofic shifts with synchronizing presentations

• Nataša Jonoska

A sofic shift S is a symbolic dynamical system that can be viewed as a set of all bi-infinite sequences obtained by reading the labels of all bi-infinite paths in a finite directed labeled graph G. The presentation G is synchronizing if for every vertex v there is a word x v such that every path in G labeled with x v has v as a terminal vertex. We present an example of a subshift of finite type that has no unique minimal deterministic presentation and we show that if a sofic shift has a synchronizing, deterministic presentation (sdp), then it has a unique minimal one. Irreducible sofic shifts, subshifts of finite type and nonwandering systems have synchronizing, deterministic presentations. We give an intrinsic characterization of a sofic shift S that has an sdp in terms of the syntactic monoid M(S) of the factor language F(S) of S. Another characterization of sofic shifts with sdp's is given in terms of the predecessor sets. We show that a sofic shift can have at most one bi-synchronizing presentation.