Arrow Research search

Author name cluster

Robert Mercaş

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.

13 papers
1 author row

Possible papers

13

TCS Journal 2025 Journal Article

Ternary is still good for Parikh matrices

  • Robert Mercaş
  • Wen Chean Teh

The focus of this work is the study of Parikh matrices with emphasis on two concrete problems. In the first part of our presentation we show that a conjecture by Dick at al. in 2021 only stands in the case of ternary alphabets, while providing counterexamples for larger alphabets. In particular, we show that the only type of distinguishability in the case of 3-letter alphabets is the trivial one. The second part of the paper builds on the notion of Parikh matrices for projections of words, discussed in the former part of this work, and answers, once more in the case of a ternary alphabet, a question posed by Atanasiu et al. in 2022 with regards to the minimal Hamming distance in between words sharing a congruency class.

Details DOI

TCS Journal 2021 Journal Article

Reducing the ambiguity of Parikh matrices

  • Jeffery Dick
  • Laura K. Hutchinson
  • Robert Mercaş
  • Daniel Reidenbach

The Parikh matrix mapping allows us to describe words using matrices. Whilst compact, this description comes with a level of ambiguity since a single matrix may describe multiple words. In this paper, we investigate how considering the Parikh matrices of various transformations of a given word can decrease that ambiguity. More specifically, for any word, we study the Parikh matrix of its projection to a smaller alphabet as well as that of its Lyndon conjugate. Our results demonstrate that ambiguity can often be reduced using these concepts, and we give conditions on when they succeed.

Details DOI

I&C Journal 2018 Journal Article

Alignment-free sequence comparison using absent words

  • Panagiotis Charalampopoulos
  • Maxime Crochemore
  • Gabriele Fici
  • Robert Mercaş
  • Solon P. Pissis

Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as q-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an absent word of some sequence if it does not occur in the sequence. An absent word is minimal if all its proper factors occur in the sequence. Here we present the first linear-time and linear-space algorithm to compare two sequences by considering all their minimal absent words. In the process, we present results of combinatorial interest, and also extend the proposed techniques to compare circular sequences. We also present an algorithm that, given a word x of length n, computes the largest integer for which all factors of x of that length occur in some minimal absent word of x in time and space O ( n ). Finally, we show that the known asymptotic upper bound on the number of minimal absent words of a word is tight.

Details DOI

TCS Journal 2018 Journal Article

Revisiting Shinohara's algorithm for computing descriptive patterns

  • Henning Fernau
  • Florin Manea
  • Robert Mercaş
  • Markus L. Schmid

A pattern α is a word consisting of constants and variables and it describes the pattern language L ( α ) of all words that can be obtained by uniformly replacing the variables with constant words. In 1982, Shinohara presents an algorithm that computes a pattern that is descriptive for a finite set S of words, i. e. , its pattern language contains S in the closest possible way among all pattern languages. We generalise Shinohara's algorithm to subclasses of patterns and characterise those subclasses for which it is applicable. Furthermore, within this set of pattern classes, we characterise those for which Shinohara's algorithm has a polynomial running time (under the assumption P ≠ NP ). Moreover, we also investigate the complexity of the consistency problem of patterns, i. e. , finding a pattern that separates two given finite sets of words.

Details DOI

TCS Journal 2016 Journal Article

On the density of Lyndon roots in factors

  • Maxime Crochemore
  • Robert Mercaş

This work takes another look at the number of runs that a string may contain and provides an alternative proof for the bound. We also propose another stronger conjecture that states the following: for a fixed order on the alphabet, within every factor of a word there are at most as many occurrences of Lyndon roots corresponding to runs in the word as the length of the factor. Only first occurrences of roots in each run are considered.

Details DOI

I&C Journal 2014 Journal Article

The pseudopalindromic completion of regular languages

  • Szilárd Zsolt Fazekas
  • Florin Manea
  • Robert Mercaş
  • Kayoko Shikishima-Tsuji

Pseudopalindromes are words that are fixed points for some antimorphic involution. In this paper we discuss a newer word operation, that of pseudopalindromic completion, in which symbols are added to either side of the word such that the new obtained words are pseudopalindromes. This notion represents a particular type of hairpin completion, where the length of the hairpin is at most one. We give precise descriptions of regular languages that are closed under this operation and show that the regularity of the closure under the operation is decidable.

Details DOI

TCS Journal 2012 Journal Article

Periodicity algorithms and a conjecture on overlaps in partial words

  • F. Blanchet-Sadri
  • Robert Mercaş
  • Abraham Rashin
  • Elara Willett

We propose an algorithm that given as input a full word w of length n, and positive integers p and d, outputs, if any exists, a maximal p -periodic partial word contained in w with the property that no two holes are within distance d (so-called d -valid). Our algorithm runs in O ( n d ) time and is used for the study of repetition-freeness of partial words. Furthermore, we construct an infinite word over a five-letter alphabet that is overlap-free even after holes are inserted in arbitrary 2-valid positions, answering affirmatively a conjecture from Blanchet-Sadri, Mercaş, and Scott.

Details DOI

TCS Journal 2012 Journal Article

The three-squares lemma for partial words with one hole

  • F. Blanchet-Sadri
  • Robert Mercaş

Partial words, or sequences over a finite alphabet that may have do-not-know symbols or holes, have been recently the subject of much investigation. Several interesting combinatorial properties have been studied such as the periodic behavior and the counting of distinct squares in partial words. In this paper, we extend the three-squares lemma on words to partial words with one hole. This result provides special information about the squares in a partial word with at most one hole, and puts restrictions on the positions at which periodic factors may occur, which is in contrast with the well known periodicity lemma of Fine and Wilf.

Details DOI

TCS Journal 2011 Journal Article

Avoiding large squares in partial words

  • F. Blanchet-Sadri
  • Ilkyoo Choi
  • Robert Mercaş

Well-known results on the avoidance of large squares in (full) words include the following: (1) Fraenkel and Simpson showed that we can construct an infinite binary word containing at most three distinct squares; (2) Entringer, Jackson and Schatz showed that there exists an infinite binary word avoiding all squares of the form x x such that | x | ≥ 3, and that the bound 3 is optimal; (3) Dekking showed that there exists an infinite cube-free binary word that avoids all squares x x with | x | ≥ 4, and that the bound of 4 is best possible. In this paper, we investigate these avoidance results in the context of partial words, or sequences that may have some undefined symbols called holes. Here, a square has the form u v with u and v compatible, and consequently, such a square is compatible with a number of full words that are squares over the given alphabet. We show that (1) holds for partial words with at most two holes. We prove that (2) extends to partial words having infinitely many holes. Regarding (3), we show that there exist binary partial words with infinitely many holes that avoid cubes and have only eleven full word squares compatible with factors of it. Moreover, this number is optimal, and all such squares x x satisfy | x | ≤ 4.

Details DOI

TCS Journal 2009 Journal Article

A generalization of Thue freeness for partial words

  • F. Blanchet-Sadri
  • Robert Mercaş
  • Geoffrey Scott

This paper approaches the combinatorial problem of Thue freeness for partial words. Partial words are sequences over a finite alphabet that may contain a number of “holes”. First, we give an infinite word over a three-letter alphabet which avoids squares of length greater than two even after we replace an infinite number of positions with holes. Then, we give an infinite word over an eight-letter alphabet that avoids longer squares even after an arbitrary selection of its positions are replaced with holes, and show that the alphabet size is optimal. We find similar results for overlap-free partial words.

Details DOI

TCS Journal 2007 Journal Article

Freeness of partial words

  • Florin Manea
  • Robert Mercaş

The paper approaches the classical combinatorial problem of freeness of words, in the more general case of partial words. First, we propose an algorithm that tests efficiently whether a partial word is k -free or not, for a given k. Then, we show that there exist arbitrarily many k -free infinite partial words, over a binary alphabet, containing an infinite number of holes, for k ≥ 3. Moreover, we present an efficient algorithm for the construction of a cube-free partial word with a given number of holes, over a binary alphabet. In the final section of the paper, we show that there exists an infinite word, over a four-symbol alphabet, in which we can substitute randomly one symbol with a hole, and still obtain a cube-free word; we show that such a word does not exist for alphabets with fewer symbols. Further, we prove that in this word we can replace arbitrarily many symbols with holes, such that each two consecutive holes are separated by at least two symbols, and obtain a cube-free partial word. This result seems interesting because any partial word containing two holes with less than two symbols between them is not cube-free. Finally, we modify the previously presented algorithm to construct, over a four-symbol alphabet, a cube-free partial word with exactly n holes, having minimal length, among all the possible cube-free partial words with at least n holes.

Details DOI
v2026.09.13