Publications

As usual in my discipline, authors appear in alphabetical order.
Here is a list in pdf of all my papers, by type: You can also find a list of my papers on Google Scholar and on DBLP.

Edited Volume

Book Chapter

  • Splicing Systems from Past to Future: Old and New Challenges
    with Luc Boasson, Paola Bonizzoni, Clelia De Felice, Isabelle Fagnot, Rocco Zaccagnino and Rosalba Zizza
    • In: Discrete Mathematics and Computer Science. Papers in Memoriam Alexandru Mateescu (1952-2005). The Publishing House of the Romanian Academy, 2014. ISBN: 978-973-27-2470-5 | arXiv

Articles

  • Open and Closed Words
    • In: Bulletin of the European Association for Theoretical Computer Science EATCS (The Formal Language Theory Column), 123:140-149 (2017) | url
  • Minimal Forbidden Factors of Circular Words
    with Antonio Restivo and Laura Rizzo
    • In: WORDS '17, Proc. of the 11th International Conference on Words. Lecture Notes in Computer Science, 10432:36-48 (2017) | doi | arXiv
  • Anti-Powers in Infinite Words
    with Antonio Restivo, Manuel Silva and Luca Q. Zamboni
    • In: Journal of Combinatorial Theory, Series A, to appear | arXiv
    • Preliminary version: Anti-Powers in Infinite Words
      In: ICALP '16, Proc. of the 43rd International Colloquium on Automata, Languages and Programming. Leibniz Internat. Proc. in Informatics (LIPIcs), 55: 124:1-124:9 (2016) | doi | arXiv
    • Also reported (by M. Silva) at: 16th Mons Days of Theoretical Computer Science (2016)
    • See sequences A274543 and A275061 in OEIS.
  • Alignment-Free Sequence Comparison Using Absent Words
    with Panagiotis Charalampopoulos, Maxime Crochemore, Robert Mercaș and Solon Pissis
    • Submitted
    • Preliminary version (without Panagiotis Charalampopoulos): Linear-Time Sequence Comparison Using Minimal Absent Words & Applications
      In: LATIN '16, Proc. of the 12th Latin American Theoretical Informatics Symposium. Lecture Notes in Computer Science, 9644:334-346 (2016) | doi | arXiv
    • Also reported (by me) at: London Stringology Days / London Algorithmic Workshop (2016) | slides
  • Abelian-Square Rich Words
    with Filippo Mignosi and Jeffrey O. Shallit
    • In: Theoretical Computer Science, 684: 29-42 (2017) | doi | arXiv
    • Preliminary version: Words with the Maximum Number of Abelian Squares
      In: WORDS '15, Proc. of the 10th International Conference on Words. Lecture Notes in Computer Science, 9304:122-134 (2015) | doi | arXiv
    • Also reported (by F. Mignosi) at: London Stringology Days / London Algorithmic Workshop (2016)
    • Also reported (by me) at: Formal Languages and Automata Theory (2016)
    • See sequence A241674 in OEIS.
  • The Sequence of Open and Closed Prefixes of a Sturmian Word
    with Alessandro De Luca and Luca Q. Zamboni
    • In: Advances in Applied Mathematics, 90: 27-45 (2017) | doi | arXiv
    • Preliminary version (without Luca Q. Zamboni): Open and Closed Prefixes of Sturmian Words
      In: WORDS '13, Proc. of the 9th International Conference on Words. Lecture Notes in Computer Science, 8079: 132-142 (2013) | doi | arXiv | slides
  • On Prefix Normal Words and Prefix Normal Forms
    with Péter Burcsi, Zsuzsanna Lipták, Frank Ruskey and Joe Sawada
    • In: Theoretical Computer Science, 659: 1-13 (2017) | doi | arXiv
    • Preliminary versions: Normal, Abby Normal, Prefix Normal
      In: FUN '14, Proc. of the 7th International Conference on Fun with Algorithms. Lecture Notes in Computer Science, 8496: 74-88 (2014) | doi | arXiv
      and (without Frank Ruskey and Joe Sawada): On Prefix Normal Words.
      In: DLT '11, Proc. of the 15th Conference on Developments in Language Theory. Lecture Notes in Computer Science, 6795: 228-238 (2011) | doi | slides
    • See sequences A238110, A194850 and A238109 in OEIS.
  • Cyclic Complexity of Words
    with Julien Cassaigne, Marinella Sciortino and Luca Q. Zamboni
    • In: Journal of Combinatorial Theory, Series A, 145: 36-56 (2017) | doi | arXiv
    • Preliminary version: Cyclic Complexity of Words
      In: MFCS '14, Proc. of the 39th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, 8634: 159-170 (2014) | doi | arXiv
  • Fast Computation of Abelian Runs
    with Tomasz Kociumaka, Thierry Lecroq, Arnaud Lefebvre and Élise Prieur-Gaston
    • In: Theoretical Computer Science, 656 Part B: 256-264 (2016) | doi | arXiv
    • Also reported (by T. Lecroq) at: SeqBio 2015 | doi
    • Preliminary version (without Tomasz Kociumaka): Online Computation of Abelian Runs
      In: LATA '15, Proc. of the 9th International Conference on Language and Automata Theory and Applications. Lecture Notes in Computer Science, 8977: 391-401 (2015) | doi | arXiv
    • Also reported (by me) at: London Stringology Days / London Algorithmic Workshop (2015) | slides
  • A Note on Easy and Efficient Computation of Full Abelian Periods of a Word
    with Thierry Lecroq, Arnaud Lefebvre, Élise Prieur-Gaston, William F. Smyth
    • In: Discrete Applied Mathematics, 212: 88-95 (2016) | doi | arXiv
    • Preliminary version: Quasi-Linear Time Computation of the Abelian Periods of a Word
      In: PSC '12, Proc. of the Prague Stringology Conference 2012, pp. 103-110 (2012) | doi
  • Abelian Powers and Repetitions in Sturmian Words
    with Alessio Langiu, Thierry Lecroq, Arnaud Lefebvre, Filippo Mignosi, Jarkko Peltomäki and Élise Prieur-Gaston
    • In: Theoretical Computer Science, 635: 16-34 (2016) | doi | arXiv
    • Also reported (by F. Mignosi) at: London Stringology Days / London Algorithmic Workshop (2016)
    • Also reported (by me) at: Formal Languages and Automata Theory (2016) | slides
    • Preliminary version (without Jarkko Peltomäki): Abelian Repetitions in Sturmian Words
      In: DLT '13, Proc. of the 17th Conference on Developments in Language Theory. Lecture Notes in Computer Science, 7907: 227-238 (2013) | doi | arXiv
    • Also reported (by T. Lecroq) at: SeqBio 2013 | doi
  • On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals
    with Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
    • In: Information Processing Letters, 116: 245-251 (2016) | doi | arXiv
    • Also reported (by J. Radoszewski) at: London Stringology Days / London Algorithmic Workshop (2016)
  • On the Number of Closed Factors in a Word
    with Golnaz Badkobeh and Zsuzsanna Lipták
    • In: LATA '15, Proc. of the 9th International Conference on Language and Automata Theory and Applications. Lecture Notes in Computer Science, 8977: 381-390 (2015) | doi | arXiv | slides
    • Preliminary version (without Golnaz Badkobeh): Words with the Smallest Number of Closed Factors
      In: 14th Mons Days of Theoretical Computer Science, local proceedings (2012) | pdf | slides
    • Also reported (by me) at: ICTCS '12, 13th Italian Conference on Theoretical Computer Science (2012) | pdf
    • See sequence A226452 in OEIS.
  • Factorizations of the Fibonacci Infinite Word
    • In: Journal of Integer Sequences, 18: Article 15.9.3 (2015) | doi | arXiv
    • Many thanks to Russell Jay Hendel for his nice review.
  • Vertical Representation of C-words
    with Jean-Marc Fédou
    • In: Theoretical Computer Science, 565: 90-101 (2015) | pdf | doi | arXiv
    • Preliminary version: Vertical Representation of Smooth Factors
      In: International Conference for the 20th anniversary of LaCIM, local proceedings (2010) | pdf | slides
  • Universal Lyndon Words
    with Arturo Carpi, Štěpán Holub, Jakub Opršal and Marinella Sciortino
    • In: MFCS '14, Proc. of the 39th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, 8634: 135-146 (2014) | doi | arXiv | slides
  • On Combinatorial Generation of Prefix Normal Words
    with Péter Burcsi, Zsuzsanna Lipták, Frank Ruskey and Joe Sawada
    • In: CPM '14, Proc. of the 25th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, 8464: 60-69 (2014) | doi | arXiv | slides
    • See sequence A238109 in OEIS.
  • A Subquadratic Algorithm for Minimum Palindromic Factorization
    with Travis Gagie, Juha Kärkkäinen and Dominik Kempa
    • In: Journal of Discrete Algorithms, 28: 41-48 (2014) | doi | arXiv
  • On the Structure of Bispecial Sturmian Words
    • In: Journal of Computer and System Sciences, 80(4): 711–719 (2014) | doi | arXiv
    • Preliminary version: A Characterization of Bispecial Sturmian Words
      In: MFCS '12, Proc. of the 39th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, 7834: 212-221 (2012) | doi | arXiv | slides
    • Also reported at: ICTCS '12, 13th Italian Conference on Theoretical Computer Science (2012) | pdf
    • See sequence A180444 in OEIS.
  • Algorithms for Computing Abelian Periods of Words
    with Thierry Lecroq, Arnaud Lefebvre and Élise Prieur-Gaston
    • In: Discrete Applied Mathematics, 163: 287-297 (2014) | doi | arXiv
    • Preliminary version: Computing Abelian Periods in Words
      In: PSC '11, Proc. of the Prague Stringology Conference 2011, pp. 184-196 (2011) | doi
    • Also reported (by me) at: Workshop Algorithmique, combinatoire du texte et applications en bio-informatique (2011) | slides
    • Also reported (by T. Lecroq) at: London Stringology Days / London Algorithmic Workshop (2011)
  • Binary Jumbled String Matching for Highly Run-Length Compressible Texts
    with Golnaz Badkobeh, Steve Kroon and Zsuzsanna Lipták
    • In: Information Processing Letters, 113: 604-608 (2013) | doi | arXiv
  • On the Least Number of Palindromes Contained in an In finite Word
    with Luca Q. Zamboni
    • In: Theoretical Computer Science, 481: 1-8 (2013) | doi | arXiv
    • Preliminary version: On The Least Number of Palindromes in an In finite Word
      In: RuFiDiM '12, Proc. of the 2nd Russian-Finnish Symposium on Discrete Mathematics. TUCS Lecture Notes, 17: 63-70 (2012) | pdf
  • Enumeration and Structure of Trapezoidal Words
    with Michelangelo Bucci and Alessandro De Luca
    • In: Theoretical Computer Science, 468: 12-22 (2013) | doi | arXiv
    • Preliminary version (without Michelangelo Bucci and Alessandro De Luca): A Classification of Trapezoidal Words
      In: WORDS '11, Proc. of the 8th International Conference on Words. Electronic Proceedings in Theoretical Computer Science, 63: 129-137 (2011) | doi | arXiv | slides
    • See sequence A260881 in OEIS.
  • Topological Properties of Cellular Automata on Trees
    with Francesca Fiorenzi
    • In: AUTOMATA&JAC '12, Proc. of the 18th International Workshop on Cellular Automata and Discrete Complex Systems & 3rd International Symposium Journées Automates Cellulaires. Electronic Proceedings in Theoretical Computer Science, 90: 255-266 (2012) | doi | arXiv
  • On Approximate Jumbled Pattern Matching in Strings
    with Péter Burcsi, Ferdinando Cicalese and Zsuzsanna Lipták
    • In: Theory of Computing Systems, 50: 35-51 (2012) | doi
    • Preliminary version: On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching
      In: FUN '10, Proc. of the 5th International Conference on Fun with Algorithms. Lecture Notes in Computer Science, 6099: 89-101 (2010) | doi
  • Algorithms for Jumbled Pattern Matching in Strings
    with Péter Burcsi, Ferdinando Cicalese and Zsuzsanna Lipták
    • In: International Journal of Foundations of Computer Science, 23: 357-374 (2012) | doi | arXiv
    • Preliminary version (without Péter Burcsi): Searching for Jumbled Patterns in Strings
      In: PSC '09, Proc. of the Prague Stringology Conference 2009, pp. 105-117 (2009) | doi
    • Also reported (by me) at: Workshop Algorithmique, combinatoire du texte et applications en bio-informatique (2010) | slides
  • Automata and Differentiable Words
    with Jean-Marc Fédou
    • In: Theoretical Computer Science, 443: 46-62 (2012) | doi | arXiv
  • Special Factors and the Combinatorics of Suffix and Factor Automata
    • In: Theoretical Computer Science, 412: 3604-3615 (2011) | doi
    • Preliminary version (part about the suffix automaton): Combinatorics of Finite Words and Suffix Automata
      In: CAI '09, Proc. of the 3rd International Conference on Algebraic Informatics. Lecture Notes in Computer Science, 5725: 250-259 (2009) | doi | slides
    • Preliminary version (part about the factor automaton): Factor Automata and Special Factors.
      In: 13th Mons Days of Theoretical Computer Science, local proceedings (2010) | pdf | slides
  • On the Regularity of Circular Splicing Languages: a Survey and New Developments
    with Paola Bonizzoni, Clelia De Felice and Rosalba Zizza
    • In: Natural Computing, 9: 397-420 (2010) | doi
  • Some Remarks on Differentiable Sequences and Recursivity
    with Jean-Marc Fédou
  • On the Minimal Uncompletable Word Problem
    with Elena V. Pribavkina and Jacques Sakarovitch
    • Technical report (2010) | arXiv
  • A Characterization of Regular Circular Languages Generated by Marked Splicing Systems
    with Clelia De Felice and Rosalba Zizza
    • In: Theoretical Computer Science, 410: 4937-4960 (2009) | doi
    • Preliminary version: Marked Systems and Circular Splicing
      In: FCT '07, Proc. of the 16th International Symposium on Fundamentals of Computation Theory. Lecture Notes in Computer Science, 4639: 238-249 (2007) | doi | slides
    • Also reported (by me) at: AutoMathA '07, 1st International Conference "Automata: from Mathematics to Applications", local proceedings (2007)
  • Word Assembly through Minimal Forbidden Words
    with Filippo Mignosi, Antonio Restivo and Marinella Sciortino
    • In: Theoretical Computer Science, 359: 214-230 (2006) | doi
    • Preliminary version: Fragment Assembly through Minimal Forbidden Words
      In: 10th Mons Days of Theoretical Computer Science, local proceedings (2004) | pdf | slides
  • Presentations of Constrained Systems with Unconstrained Positions
    with Marie-Pierre Béal and Maxime Crochemore
    • In: IEEE Transactions on Information Theory, 51: 1891-1900 (2005) | doi

Theses

Coauthors