Arrow Research search

Author name cluster

Ion Petre

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers
1 author row

Possible papers

22

TCS Journal 2016 Journal Article

Complete characterization for the fit-preserving data refinement of mass-action reaction networks

  • Cristian Gratie
  • Ion Petre

The data refinement of reaction-based models consists in substituting species from the original model with several subspecies in the refined one. Fit-preserving refinement, where the goal is to capture the same species dynamics as the original model, helps reduce the computational cost of model fitting by reusing previously fit rate constants. In this paper we give a complete characterization of fit-preserving refinement, as necessary and sufficient linear constraints on the reaction rate constants. Our result is applicable for mass-action reaction networks with uniquely identifiable rate constants. We demonstrate our result on the well-known Brusselator model.

Details DOI

TCS Journal 2016 Journal Article

Complexity of model checking for reaction systems

  • Sepinoud Azimi
  • Cristian Gratie
  • Sergiu Ivanov
  • Luca Manzoni
  • Ion Petre
  • Antonio E. Porreca

Reaction systems are a new mathematical formalism inspired by the living cell and driven by only two basic mechanisms: facilitation and inhibition. As a modeling framework, they differ from the traditional approaches based on ODEs and CTMCs in two fundamental aspects: their qualitative character and the non-permanency of resources. In this article we introduce to reaction systems several notions of central interest in biomodeling: mass conservation, invariants, steady states, stationary processes, elementary fluxes, and periodicity. We prove that the decision problems related to these properties span a number of complexity classes from P to NP - and coNP -complete to PSPACE -complete.

Details DOI

TCS Journal 2015 Journal Article

Dependency graphs and mass conservation in reaction systems

  • Sepinoud Azimi
  • Cristian Gratie
  • Sergiu Ivanov
  • Ion Petre

Reaction systems is a new mathematical formalism inspired by the biological cell, which focuses on an abstract set-based representation of chemical reactions via facilitation and inhibition. In this article we focus on the property of mass conservation for reaction systems. We show that conservation of sets gives rise to a relation between the species, which we capture in the concept of the conservation dependency graph. We then describe an application of this relation to the problem of listing all conserved sets. We further give a sufficient negative polynomial criterion which can be used for proving that a set is not conserved. Finally, we present a simulator of reaction systems, which also includes an implementation of the algorithm for listing the conserved sets of a given reaction system.

Details DOI

TCS Journal 2012 Journal Article

Matrix insertion–deletion systems

  • Ion Petre
  • Sergey Verlan

We investigate in this article the operations of insertion and deletion working in a matrix-controlled manner. We show that this allows to us strictly increase the computational power: in the case of systems that are not computationally complete (with total size equal to 4), the computational completeness can be obtained by introducing the matrix control and using only binary matrices.

Details DOI

TCS Journal 2012 Journal Article

Preface

  • Giorgio Ausiello
  • Hendrik Jan Hoogeboom
  • Juhani Karhumäki
  • Ion Petre
  • Arto Salomaa
Details DOI

TCS Journal 2012 Journal Article

Simple gene assembly as a rewriting of directed overlap-inclusion graphs

  • Sepinoud Azimi
  • Tero Harju
  • Miika Langille
  • Ion Petre

The simple intramolecular model for gene assembly in ciliates consists of three molecular operations, simple ld, simple hi and simple dlad. Mathematical models in terms of signed permutations and signed strings proved limited in capturing some of the combinatorial details of the simple gene assembly process. Brijder and Hoogeboom introduced a new model in terms of overlap-inclusion graphs which could describe two of the three operations of the model and their combinatorial properties. To capture the third operation, we extended their framework to directed overlap-inclusion (DOI) graphs in Azimi et al. (2011) [1]. In this paper we introduce DOI graph-based rewriting rules that capture all three operations of the simple gene assembly model and prove that they are equivalent to the string-based formalization of the model.

Details DOI

TCS Journal 2010 Journal Article

Accepting splicing systems

  • Victor Mitrana
  • Ion Petre
  • Vladimir Rogojin

In this paper, we propose a novel approach to splicing systems, namely we consider them as accepting devices. Two ways of iterating the splicing operation and two variants of accepting splicing system are investigated. Altogether, we obtain four models, which are compared with each other as well as with the generating splicing systems from the computational power point of view. Several decision problems concerning the accepting splicing systems are discussed.

Details DOI

TCS Journal 2010 Journal Article

Computing the graph-based parallel complexity of gene assembly

  • Artiom Alhazov
  • Chang Li
  • Ion Petre

We consider a graph-theoretical formalization of the process of gene assembly in ciliates introduced in Ehrenfeucht et al. (2003) [3], where a gene is modeled as a signed graph. The gene assembly, based on three types of operations only, is then modeled as a graph reduction process (to the empty graph). Motivated by the robustness of the gene assembly process, the notions of parallel reduction and parallel complexity of signed graphs have been considered in Harju et al. (2006) [7]. We describe in this paper an exact algorithm for computing the parallel complexity of a given signed graph and for finding an optimal parallel reduction for it. Checking the parallel applicability of a given set of operations and scanning all possible selections amount to a high computational complexity. We also briefly discuss a faster approximate algorithm that however, cannot guarantee finding the optimal reduction.

Details DOI

TCS Journal 2010 Journal Article

Extended strings and graphs for simple gene assembly

  • Robert Brijder
  • Miika Langille
  • Ion Petre

The simple intramolecular model for gene assembly in ciliates is particularly interesting because it can predict the correct assembly of all available experimental data, although it is not universal. The simple model also has a confluence property that is not shared by the general model. A previous formalization of the simple model through sorting of signed permutations is unsatisfactory because it effectively ignores one operation of the model and thus, it cannot be used to answer questions about parallelism in the model, or about measures of complexity. We propose in this paper a string-based model in which a gene is represented through its sequence of pointers and markers and its assembly is represented as a string rewriting process. We prove that this string-based model is equivalent to the permutation-based model as far as gene assembly is concerned, while it tracks all operations of the simple model. We also consider overlap graphs for these strings and prove the results with respect to the overlap of markers.

Details DOI

TCS Journal 2009 Journal Article

The parallel complexity of signed graphs: Decidability results and an improved algorithm

  • Artiom Alhazov
  • Ion Petre
  • Vladimir Rogojin

We consider a graph-based model for the process of gene assembly in ciliates, as proposed in [A. Ehrenfeucht, T. Harju, I. Petre, D. M. Prescott, G. Rozenberg, Computation in Living Cells: Gene Assembly in Ciliates, Springer, 2003]. The model consists of three operations, each reducing the order of the signed graph. Reducing the graph to the empty graph through a sequence of operations corresponds to assembling a gene. We investigate parallel reductions of a given signed graph, where the graph is reduced through a sequence of parallel steps. A parallel step consists of operations such that any of their sequential compositions are applicable to the current graph. We improve the basic exhaustive search algorithm reported in [A. Alhazov, C. Li, I. Petre, Computing the graph-based parallel complexity of gene assembly, Theoretical Computer Science, 2008 (in press)] to compute the parallel complexity of signed graphs. On the one hand, we reduce the number of sets of operations which should be checked for parallel applicability. On the other hand, we speed up the parallel applicability check procedure. We prove also that deciding whether a given parallel composition of operations is applicable to a given signed graph is a coNP problem. Deciding whether the parallel complexity (the length of a shortest parallel reduction) of a signed graph is bounded by a given constant is in NP NP.

Details DOI

I&C Journal 2008 Journal Article

Decision problem for shuffled genes

  • Ion Petre
  • Vladimir Rogojin

We consider a permutation-based model for the gene assembly process in ciliates. We give a procedure to decide whether a given micronuclear molecule may be assembled by using only simple dlad operations. We solve the problem based on a notion of dependency graph.

Details DOI

TCS Journal 2008 Journal Article

Parikh matrices and amiable words

  • Adrian Atanasiu
  • Radu Atanasiu
  • Ion Petre

Using the fact that the Parikh matrix mapping is not an injective mapping, the paper investigates some properties of the set of words with the same Parikh matrix; these words are called “amiable”. The presented results extend the results obtained in [A. Atanasiu, Binary amiable words, Int. J. Found. Comput. Sci. 18 (2) (2007) 387–400] for the binary case. In particular it is shown that all the words having the same Parikh matrix can be obtained one from another by applying only two types of transformations. Moreover, the mirrors of two amiable words are also amiable (thus forming a symmetrical class of words).

Details DOI

TCS Journal 2008 Journal Article

Sequential vs. parallel complexity in simple gene assembly

  • Miika Langille
  • Ion Petre

We investigate some differences between the general intramolecular model for gene assembly and its restricted simple model. Although both models satisfactorily sort all current experimental data, we show that the general model offers assembly strategies for a given string that vary in both assembly length and the operations used, while the simple model will always use the same number of each type of operation to sort a gene. When simple operations are applied in parallel this is given a new twist. We prove that for any n ≥ 1, there exists a string having maximally parallel assemblies of any length between n and 2 n.

Details DOI

TCS Journal 2007 Journal Article

Self-assembly of strings and languages

  • Erzsébet Csuhaj-Varjú
  • Ion Petre
  • György Vaszil

Self-assembly is the process in which simple objects autonomously aggregate into large structures and it has become one of the major tools for nano-scale engineering. We propose in this paper a string-based framework inspired by the principle of self-assembly: two strings with a common overlap, say u v and v w, yield a string u v w; we say that string u v w has been assembled from strings u v and v w. The operation may be extended in a natural way also to sets of strings. We answer several questions: what is the assembly power of a given set of strings, can a given set of strings be generated through assembly and if so, what is a minimal generator for it?

Details DOI

TCS Journal 2005 Journal Article

Commutation with codes

  • Juhani Karhumäki
  • Michel Latteux
  • Ion Petre

The centralizer of a set of words X is the largest set of words C ( X ) commuting with X: X C ( X ) = C ( X ) X. It has been a long standing open question due to [J. H. Conway, Regular Algebra and Finite Machines, Chapman & Hall, London (1971). ], whether the centralizer of any rational set is rational. While the answer turned out to be negative in general, see [M. Kunc, Proc. of ICALP 2004, Lecture Notes in Computer Science, Vol. 3142, Springer, Berlin, 2004, pp. 870–881. ], we prove here that the situation is different for codes: the centralizer of any rational code is rational and if the code is finite, then the centralizer is finitely generated. This result has been previously proved only for binary and ternary sets of words in a series of papers by the authors and for prefix codes in an ingenious paper by [B. Ratoandromanana, RAIRO Inform. Theor. 23(4) (1989) 425–444. ]—many of the techniques we use in this paper follow her ideas. We also give in this paper an elementary proof for the prefix case.

Details DOI

TCS Journal 2003 Journal Article

Formal systems for gene assembly in ciliates

  • Andrzej Ehrenfeucht
  • Tero Harju
  • Ion Petre
  • David M. Prescott
  • Grzegorz Rozenberg

DNA processing in ciliates, a very ancient group of organisms, is among the most sophisticated DNA processing in living organisms. It has a quite clear computational structure and even uses explicitly the linked list data structure! Particularly interesting from the computational point of view is the process of gene assembly from its micronuclear to its macronuclear form. We investigate here the string rewriting and the graph rewriting models of this process, involving three molecular operations, which together form a universal set of operations in the sense that they can assembly any macronuclear gene from its micronuclear form. In particular we prove that although the graph rewriting system is more “abstract” than the string rewriting system, no “essential information” is lost, in the sense that one can translate assembly strategies from one system into the other.

Details DOI

TCS Journal 2002 Journal Article

Conway's problem for three-word sets

  • Juhani Karhumäki
  • Ion Petre

We prove two results on commutation of languages. First, we show that the maximal language commuting with a three-element language, i. e. its centralizer, is rational, thus giving an affirmative answer to a special case of a problem proposed by Conway in 1971. Second, we characterize all languages commuting with a three-element code. The characterization is similar to the one proved by Bergman for polynomials over noncommuting variables (see Trans. Am. Math. Soc. 137 (1969) 327 and Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2000): A language commutes with a three-element code X if and only if it is a union of powers of X.

Details DOI
v2026.09.13