Author name cluster

Mihaela Păun

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.

4 papers

1 author row

TCS Journal 2024 Journal Article

Jump complexity of finite automata with translucent letters

Victor Mitrana
Andrei Păun
Mihaela Păun
José Ramón Sánchez Couso

We define the jump complexity of a finite automaton with translucent letters as a function that computes the smallest upper bound on the number of jumps needed by the automaton in order to accept each word of length n, for any positive integer n. We prove that a sufficient condition for a finite automaton with translucent letters to accept a regular language is to have a jump complexity bounded by a constant. Along the same lines, we show that there are languages which require a jump complexity in Ω ( n ) of any finite automaton with translucent letters accepting one of these languages. We also show that there exist nondeterministic finite automata with translucent letters of jump complexity in O ( log ⁡ n ) and O ( n ) that accept non-regular languages. Several open problems and directions for further developments are finally discussed.

Details DOI

TCS Journal 2017 Journal Article

Improvements on contours based segmentation for DNA microarray image processing

Yang Li
Andrei Păun
Mihaela Păun

In this paper we present an improvement of the Segment Based Contours (SBC) method by implementing a higher order of finite difference schemes in the partial differential equation used in our mathematical model. Two methods are presented: one is a 4th order method and the other a 8th order method. The 4th order method could be applied to segment both the cDNA microarray images and the Affymetrix GeneChips, while the 8th order method could only be applied to processing the cDNA microarray images, due to the limitation of the current image resolution. Additionally, we provide both the mathematical derivations for the partial differential equations (their 4th or 8th order approximations) as well as the validation trough simulations of the microarray images by using real images as seeds for the Nykter's 2006 methodology. We conclude by showing that both the 4th order method as well as the 8th order one are superior to the SBC and the widely used GOGAC method implemented in the Affymetrix standard processing package for microarrays.

Details DOI

TCS Journal 2015 Journal Article

Segmenting microarray images using a contour-based method

Mihaela Păun
Yang Li
Yuan Cheng
Iris Tusa
Andrei Păun

In this work we describe a new segmentation technique for the Affymetrix microarray images. We prove that our method can offer better predictions on the gene levels as opposed to the standard Affymetrix segmentation implemented in the Affymetrix GeneChip Operating Software (GCOS). To check the accuracy and show the benefits of the new segmentation method we use a previously implemented methodology to simulate microarray images with realistic features. Using such an “artificial” image provides us with the actual levels for each spot and each gene investigated in the microarray. Using this information we then proceed to segment the same image twice (with GCOS and our new method). The two segmentations will produce two sets of gene levels that are then compared to the known gene levels (known since the moment of generating the “artificial” image). Using this methodology we are able to show statistically (using 50 replicates of the same steps of generating the image, segmenting, comparing the results) that in some cases our new method greatly outperforms the GCOS implemented segmentation method, while in the rest of the cases performs in similar fashion.

Details DOI

TCS Journal 2009 Journal Article

On the Hopcroft’s minimization technique for DFA and DFCA

Andrei Păun
Mihaela Păun
Alfonso Rodríguez-Patón

We show that the absolute worst case time complexity for Hopcroft’s minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires O ( n log n ) steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a FIFO mode for the list of the splitting sets in the algorithm. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also for the case of cover automata and an algorithm based on the Hopcroft’s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by S. Yu.

Details DOI