Chiara Epifanio

article

Linear-size suffix tries

Maxime Crochemore, Chiara Epifanio, Roberto Grossi, Filippo Mignosi

Theoretical Computer Science > 2016 > 638 > C > 171-178

Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n=|w|, a suffix tree for w takes O(n) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal...

chapter

On the Suffix Automaton with Mismatches

Maxime Crochemore, Chiara Epifanio, Alessandra Gabriele, Filippo Mignosi

Lecture Notes in Computer Science > Implementation and Application of Automata > Contributed Talks > 144-156

In this paper we focus on the construction of the minimal deterministic finite automaton S _k that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of S _k in order to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r, where r is the...

chapter

A Trie-Based Approach for Compacting Automata

Maxime Crochemore, Chiara Epifanio, Roberto Grossi, Filippo Mignosi

Lecture Notes in Computer Science > Combinatorial Pattern Matching > 145-158

We describe a new technique for reducing the number of nodes and symbols in automata based on tries. The technique stems from some results on anti-dictionaries for data compression and does not need to retain the input string, differently from other methods based on compact automata. The net effect is that of obtaining a lighter automaton than the directed acyclic word graph (DAWG) of Blumer et al...

chapter

Sturmian Graphs and a Conjecture of Moser

Chiara Epifanio, Filippo Mignosi, Jeffrey Shallit, Ilaria Venturini

Lecture Notes in Computer Science > Developments in Language Theory > Contributed Papers > 175-187

In this paper we define Sturmian graphs and we prove that all of them have a “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of CDAWGs of central Sturmian words. We show also that, analogously to the case of Sturmian words,...

chapter

On Lazy Representations and Sturmian Graphs

Chiara Epifanio, Christiane Frougny, Alessandra Gabriele, Filippo Mignosi, more

Lecture Notes in Computer Science > Implementation and Application of Automata > 125-134

In this paper we establish a strong relationship between the set of lazy representations and the set of paths in a Sturmian graph associated with a real number α. We prove that for any non-negative integer i the unique path weighted i in the Sturmian graph associated with α represents the lazy representation of i in the Ostrowski numeration system associated with α. Moreover, we provide several properties...

chapter

Languages with Mismatches and an Application to Approximate Indexing

Chiara Epifanio, Alessandra Gabriele, Filippo Mignosi

Lecture Notes in Computer Science > Developments in Language Theory > 224-235

In this paper we describe a factorial language, denoted by L(S,k,r), that contains all words that occur in a string S up to k mismatches every r symbols. Then we give some combinatorial properties of a parameter, called repetition index and denoted by R(S,k,r), defined as the smallest integer h≥ 1 such that all strings of this length occur at most in a unique position of the text S up to k mismatches...

article

On Sturmian graphs

Chiara Epifanio, Filippo Mignosi, Jeffrey Shallit, Ilaria Venturini

Discrete Applied Mathematics > 2007 > 155 > 8 > 1014-1030

In this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this...

article

A multidimensional critical factorization theorem

Chiara Epifanio, Filippo Mignosi

Theoretical Computer Science > 2005 > 346 > 2-3 > 265-280

The Critical Factorization Theorem is one of the principal results in combinatorics on words. It relates local periodicities of a word to its global periodicity. In this paper we give a multidimensional extension of it. More precisely, we give a new proof of the Critical Factorization Theorem, but in a weak form, where the weakness is due to the fact that we loose the tightness of the local repetition...

article

On a conjecture on bidimensional words

Chiara Epifanio, Michel Koskas, Filippo Mignosi

Theoretical Computer Science > 2003 > 299 > 1-3 > 123-150

We prove that, given a double sequence w over the alphabet A (i.e. a mapping from Z2 to A), if there exists a pair (n0,m0)∈Z2 such that pw(n0,m0)< 1 100n0m0, then w has a periodicity vector, where pw is the complexity function in rectangles of w.

INFONA - science communication portal

Search results for: Chiara Epifanio

Linear-size suffix tries

On the Suffix Automaton with Mismatches

A Trie-Based Approach for Compacting Automata

Sturmian Graphs and a Conjecture of Moser

On Lazy Representations and Sturmian Graphs

Languages with Mismatches and an Application to Approximate Indexing

On Sturmian graphs

A multidimensional critical factorization theorem

On a conjecture on bidimensional words

Filter options

Publication date

Publication type

Keywords

Data set

Journal

INFONA - science communication portal

Search results for: Chiara Epifanio

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Publication type

Keywords

Data set

Journal

Reporting an error / abuse

Sending the report failed

Accessibility options