Publications for Robert Mercas
Download all publications as Word document
Journal Articles
Fazekas, SZ,
Mercas, R, Wu, O (2022)
Complexities for jumps and sweeps,
Journal of Automata, Languages and Combinatorics, 27(1-3), pp.131-149, ISSN: 1430-189X. DOI:
10.25596/jalc-2022-131.
Dick, J, Hutchinson, LK, Mercaş, R, Reidenbach, D (2021)
Reducing the ambiguity of Parikh matrices,
Theoretical Computer Science, 860, pp.23-40, ISSN: 0304-3975. DOI:
10.1016/j.tcs.2021.01.025.
Fernau, H, Manea, F,
Mercas, R, Schmid, M (2020)
Pattern matching with variables: Efficient algorithms and complexity results,
ACM Transactions on Computation Theory, 12(1), 6, ISSN: 1942-3454. DOI:
10.1145/3369935.
Fazekas, SZ,
Mercas, R, Reidenbach, D (2020)
On the prefix-suffix duplication reduction,
International Journal of Foundations of Computer Science, 31(1), pp.91-102, ISSN: 0129-0541. DOI:
10.1142/S0129054120400067.
Gawrychowski, P, Manea, F,
Mercas, R, Nowotka, D (2018)
Hide and seek with repetitions,
Journal of Computer and System Sciences, 101, pp.42-67, ISSN: 0022-0000. DOI:
10.1016/j.jcss.2018.10.004.
Charalampopoulos, P, Crochemore, M, Fici, G,
Mercas, R, Pissis, SP (2018)
Alignment-free sequence comparison using absent words,
Information and Computation, ISSN: 1090-2651.
Charalampopoulos, P, Crochemore, M, Fici, G,
Mercas, R, Pissis, SP (2018) Alignment-free sequence comparison using absent words,
Information and Computation, 262, pp.57-68, ISSN: 0890-5401.
Fernau, H, Manea, F,
Mercas, R, Schmid, ML (2018)
Revisiting Shinohara's algorithm for computing descriptive patterns,
Theoretical Computer Science, ISSN: 0304-3975. DOI:
10.1016/j.tcs.2018.04.035.
Mercaş, R (2017)
On the aperiodic avoidability of binary patterns with variables and reversals,
Theoretical Computer Science, 682, pp.180-189, ISSN: 0304-3975. DOI:
10.1016/j.tcs.2016.12.022.
Mercas, R and Nowotka, D (2017)
A note on Thue games,
Information Processing Letters, 118(February), pp.75-77, ISSN: 1872-6119. DOI:
10.1016/j.ipl.2016.10.004.
Mercas, R and Pisanti, N (2017)
Preface,
Journal of Discrete Algorithms, ISSN: 1570-8667. DOI:
10.1016/j.jda.2016.12.002.
Badkobeh, G, Crochemore, M, Mercaş, R (2017)
Counting maximal-exponent factors in words,
Theoretical Computer Science, 658, pp.27-35, ISSN: 0304-3975. DOI:
10.1016/j.tcs.2016.02.035.
Grossi, R, Iliopoulos, CS,
Mercas, R, Pisanti, N, Pissis, SP, Retha, A, Vayani, F (2016)
Circular sequence comparison: Algorithms and applications,
Algorithms for Molecular Biology, 11(1), DOI:
10.1186/s13015-016-0076-6.
Crochemore, M and Mercaş, R (2016)
On the density of Lyndon roots in factors,
Theoretical Computer Science, 656, pp.234-240, ISSN: 0304-3975. DOI:
10.1016/j.tcs.2016.02.015.
Crochemore, M and
Mercas, R (2016)
On the density of Lyndon roots in factors,
Theor. Comput. Sci, 656, pp.234-240, DOI:
10.1016/j.tcs.2016.02.015.
Ehlers, T, Manea, F, Mercaş, R, Nowotka, D (2015)
k-Abelian pattern matching,
Journal of Discrete Algorithms, 34, pp.37-48, ISSN: 1570-8667. DOI:
10.1016/j.jda.2015.05.004.
Mercas, R (2015) A note on the avoidability of binary patterns with variables and reversals,
CoRR, abs/1508.04571.
DASSOW, J, MANEA, F, MERCAŞ, R, MÜLLER, M (2014)
INNER PALINDROMIC CLOSURE,
International Journal of Foundations of Computer Science, 25(08), pp.1049-1063, ISSN: 0129-0541. DOI:
10.1142/s0129054114400231.
Manea, F, Mercaş, R, Tiseanu, C (2014)
An algorithmic toolbox for periodic partial words,
Discrete Applied Mathematics, 179, pp.174-192, ISSN: 0166-218X. DOI:
10.1016/j.dam.2014.07.017.
Fazekas, SZ, Manea, F, Mercaş, R, Shikishima-Tsuji, K (2014)
The pseudopalindromic completion of regular languages,
Information and Computation, 239, pp.222-236, ISSN: 0890-5401. DOI:
10.1016/j.ic.2014.09.001.
Mercaş, R and Saarela, A (2014)
5-Abelian cubes are avoidable on binary alphabets,
RAIRO - Theoretical Informatics and Applications, 48(4), pp.467-478, ISSN: 0988-3754. DOI:
10.1051/ita/2014020.
Dassow, J, Manea, F, Mercaş, R (2014)
Regular languages of partial words,
Information Sciences, 268, pp.290-304, ISSN: 0020-0255. DOI:
10.1016/j.ins.2013.12.032.
Mercas, R, Ochem, P, Samsonov, AV, Shur, AM (2014)
Binary patterns in binary cube-free words: avoidability and growth,
RAIRO - Theoretical Informatics and Applications, 48(4), pp.369-389, ISSN: 0988-3754. DOI:
10.1051/ita/2014015.
FAZEKAS, SZ and MERCAŞ, R (2013)
A NOTE ON THE DECIDABILITY OF SUBWORD INEQUALITIES,
International Journal of Foundations of Computer Science, 24(04), pp.445-452, ISSN: 0129-0541. DOI:
10.1142/s0129054113500135.
Blanchet-Sadri, F, Mercaş, R, Rashin, A, Willett, E (2012)
Periodicity algorithms and a conjecture on overlaps in partial words,
Theoretical Computer Science, 443, pp.35-45, ISSN: 0304-3975. DOI:
10.1016/j.tcs.2012.03.034.
Blanchet-Sadri, F and Mercaş, R (2012)
The three-squares lemma for partial words with one hole,
Theoretical Computer Science, 428, pp.1-9, ISSN: 0304-3975. DOI:
10.1016/j.tcs.2012.01.012.
Blanchet-Sadri, F, Mercaş, R, Simmons, S, Weissenstein, E (2012)
Erratum to: Avoidable binary patterns in partial words,
Acta Informatica, 49(1), pp.53-54, ISSN: 0001-5903. DOI:
10.1007/s00236-011-0149-4.
Manea, F,
Mercas, R, Mitrana, V (2012)
Hairpin lengthening and shortening of regular languages,
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7300 LNAI, pp.145-159, ISSN: 0302-9743. DOI:
10.1007/978-3-642-31644-9_10.
Blanchet-Sadri, F, Kim, JI, Mercaş, R, Severa, W, Simmons, S, Xu, D (2012)
Avoiding abelian squares in partial words,
Journal of Combinatorial Theory, Series A, 119(1), pp.257-270, ISSN: 0097-3165. DOI:
10.1016/j.jcta.2011.08.008.
Blanchet-Sadri, F, Choi, I, Mercaş, R (2011)
Avoiding large squares in partial words,
Theoretical Computer Science, 412(29), pp.3752-3758, ISSN: 0304-3975. DOI:
10.1016/j.tcs.2011.04.009.
Blanchet-Sadri, F, Mercaş, R, Simmons, S, Weissenstein, E (2011)
Avoidable binary patterns in partial words,
Acta Informatica, 48(1), pp.25-41, ISSN: 0001-5903. DOI:
10.1007/s00236-010-0129-0.
Allen, E, Blanchet-Sadri, F, Byrum, C, Cucuringu, M, Mercaş, R (2011)
Counting bordered partial words by critical positions,
Electronic Journal of Combinatorics, 18(1), DOI:
10.37236/625.
Choffrut, C and
Mercas, R (2010)
Contextual partial commutations,
Discrete Mathematics and Theoretical Computer Science, 12(4), pp.59-72, ISSN: 1462-7264.
Blanchet-Sadri, F and Mercaş, R (2009)
A note on the number of squares in a partial word with one hole,
RAIRO - Theoretical Informatics and Applications, 43(4), pp.767-774, ISSN: 0988-3754. DOI:
10.1051/ita/2009019.
Blanchet-Sadri, F, Davis, CD, Dodge, J, Mercaş, R, Moorefield, M (2009)
Unbordered partial words,
Discrete Applied Mathematics, 157(5), pp.890-900, ISSN: 0166-218X. DOI:
10.1016/j.dam.2008.04.004.
Blanchet-Sadri, F, Mercaş, R, Scott, G (2009)
A generalization of Thue freeness for partial words,
Theoretical Computer Science, 410(8-10), pp.793-800, ISSN: 0304-3975. DOI:
10.1016/j.tcs.2008.11.006.
Blanchet-Sadri, F, Mercaş, R, Scott, G (2009) Counting distinct squares in partial words,
Acta Cybernetica, 19(2), pp.465-477, ISSN: 0324-721X.
Manea, F and Mercaş, R (2007)
Freeness of partial words,
Theoretical Computer Science, 389(1-2), pp.265-277, ISSN: 0304-3975. DOI:
10.1016/j.tcs.2007.09.028.
Conferences
Fazekas, SZ and
Mercas, R (2023)
Sweep complexity revisited. In Nagy, B (ed)
International Conference on Implementation and Application of Automata (CIAA 2023); Implementation and Application of Automata: 27th International Conference, CIAA 2023, Famagusta, North Cyprus, September 19–22, 2023, Proceedings, Famagusta, Cyprus, pp.116-127, ISBN: 9783031402463. DOI:
10.1007/978-3-031-40247-0_8.
Frid, A and
Mercas, R (2023)
Preface. In
Combinatorics on Words: 14th International Conference (WORDS 2023), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Umeå, Sweden, pp.v-vi, ISBN: 9783031331794. DOI:
10.1007/978-3-031-33180-0.
Fazekas, SZ and Mercaş, R (2022)
Clusters of Repetition Roots Forming Prefix Chains. In
24th International Conference on Descriptional Complexity of Formal systems, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Debrecen, Hungary, pp.43-56, ISBN: 9783031132568. DOI:
10.1007/978-3-031-13257-5_4.
Hutchinson, L,
Mercas, R, Reidenbach, D (2022)
A toolkit for Parikh matrices. In Caron, P and Mignot, L (ed)
International Conference on Implementation and Application of Automata (CIAA 2022); Implementation and Application of Automata: 26th International Conference, CIAA 2022, Rouen, France, June 28 – July 1, 2022, Proceedings, Lecture Notes in Computer Science, Rouen, France, pp.116-127, ISBN: 9783031074684. DOI:
10.1007/978-3-031-07469-1_9.
Fazekas, SZ and
Mercas, R (2021)
Clusters of Repetition Roots: Single Chains. In T, B, R, D, J, G, G, G, T, J, C, P, F, S, PWH, W (ed)
SOFSEM, bozen-bolzano, italy, pp.400-409, ISBN: 978-3-030-67730-5.
Dick, J, Hutchinson, L,
Mercas, R, Reidenbach, D (2020)
Reducing the ambiguity of Parikh matrices. In Zandron, ALCM-VDSC (ed)
14th International Conference on Language and Automata Theory and Applications (LATA 2020); Language and Automata Theory and Applications (LATA 2020), Milan, Italy, pp.397-411, ISBN: 9783030406073. DOI:
10.1007/978-3-030-40608-0_28.
(2019) Combinatorics on Words - 12th International Conference, WORDS 2019, Loughborough, UK, September 9-13, 2019, Proceedings. In
Mercas, R and Reidenbach, D (ed)
, WORDS,ISBN: 978-3-030-28795-5.
Mercas, R (2017)
On the Number of Factors with Maximal-Exponent in Words. In
DEVELOPMENTS IN LANGUAGE THEORY, DEVELOPMENTS IN LANGUAGE THEORY, DLT 2017, Liege, Belgium,ISBN: 978-3-319-62808-0.
Crochemore, M, Fici, G, Mercaş, R, Pissis, SP (2016)
Linear-time sequence comparison using minimal absent words & applications. In Kranakis, E, Navarro, G, Chávez, E (ed)
LATIN, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Ensenada, Mexico, pp.334-346, ISBN: 9783662495285. DOI:
10.1007/978-3-662-49529-2_25.
Fernau, H, Manea, F, Mercaş, R, Schmid, ML (2015)
Pattern matching with variables: Fast algorithms and new hardness results. In
, Leibniz International Proceedings in Informatics, LIPIcs, pp.302-315, DOI:
10.4230/LIPIcs.STACS.2015.302.
Grossi, R, Iliopoulos, CS, Mercaş, R, Pisanti, N, Pissis, SP, Retha, A, Vayani, F (2015)
Circular Sequence Comparison with q-grams. In
, pp.203-216, ISBN: 9783662482209. DOI:
10.1007/978-3-662-48221-6_15.
Ehlers, T, Manea, F, Mercaş, R, Nowotka, D (2014)
K-abelian pattern matching. In
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp.178-190, DOI:
10.1007/978-3-319-09698-8_16.
Gawrychowski, P, Manea, F,
Mercas, R, Nowotka, D, Tiseanu, C (2013)
Finding pseudo-repetitions. In
, Leibniz International Proceedings in Informatics, LIPIcs, pp.257-268, DOI:
10.4230/LIPIcs.STACS.2013.257.
Dassow, J, Manea, F, Mercaş, R, Müller, M (2013)
Inner palindromic closure. In
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp.155-166, DOI:
10.1007/978-3-642-38771-5_15.
Mercaş, R and Saarela, A (2013)
3-Abelian cubes are avoidable on binary alphabets. In
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp.374-383, DOI:
10.1007/978-3-642-38771-5_33.
Choffrut, C and Mercaş, R (2013)
The lexicographic cross-section of the plactic monoid is regular. In
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp.83-94, DOI:
10.1007/978-3-642-40579-2_11.
Fazekas, SZ, Mercaş, R, Shikishima-Tsuji, K (2012)
Hairpin completion with bounded stem-loop. In
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp.428-439, DOI:
10.1007/978-3-642-31653-1_38.
Dassow, J, Manea, F, Mercaş, R (2012)
Connecting partial words and regular languages. In
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp.151-161, DOI:
10.1007/978-3-642-30870-3_16.
Manea, F, Mercaş, R, Nowotka, D (2012)
Fine and Wilf’s Theorem and Pseudo-repetitions. In
, pp.668-680, ISBN: 9783642325885. DOI:
10.1007/978-3-642-32589-2_58.
Manea, F, Mercaş, R, Tiseanu, C (2011)
Periodicity Algorithms for Partial Words. In
, pp.472-484, ISBN: 9783642229923. DOI:
10.1007/978-3-642-22993-0_43.
Blanchet-Sadri, F, Kim, JI, Mercaş, R, Severa, W, Simmons, S (2010)
Abelian Square-Free Partial Words. In
, pp.94-105, ISBN: 9783642130885. DOI:
10.1007/978-3-642-13089-2_8.
Blanchet-Sadri, F, Mercaş, R, Simmons, S, Weissenstein, E (2010)
Avoidable Binary Patterns in Partial Words. In
, pp.106-117, ISBN: 9783642130885. DOI:
10.1007/978-3-642-13089-2_9.
Bel-Enguix, G, Jiménez-López, MD, Mercaş, R, Perekrestenko, A (2009) Networks of evolutionary processors as natural language parsers. In
, ICAART 2009 - Proceedings of the 1st International Conference on Agents and Artificial Intelligence, pp.619-625.
Blanchet-Sadri, F, Allen, E, Byrum, C, Mercaş, R (2009)
How Many Holes Can an Unbordered Partial Word Contain?. In
, pp.176-187, ISBN: 9783642009815. DOI:
10.1007/978-3-642-00982-2_15.
Blanchet-Sadri, F, Mercaş, R, Rashin, A, Willett, E (2009)
An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms. In
, pp.188-199, ISBN: 9783642009815. DOI:
10.1007/978-3-642-00982-2_16.
Ortega, A, del Rosal, E, Pérez, D, Mercaş, R, Perekrestenko, A, Alfonseca, M (2009)
PNEPs, NEPs for Context Free Parsing: Application to Natural Language Processing. In
, pp.472-479, ISBN: 9783642024771. DOI:
10.1007/978-3-642-02478-8_59.
Blanchet-Sadri, F,
Mercas, R, Scott, G (2008)
Counting Distinct Squares in Partial Words. In Csuhaj-Varjú, E and Ésik, Z (ed)
, AFL, pp.122-133, ISBN: 978-963-311-367-7.
