Currently displaying 1 – 5 of 5

Showing per page

Order by Relevance | Title | Year of publication

Normalization of edit sequences for text synchronization

Rafael C. CarrascoAlexander Sánchez Díaz — 2011

RAIRO - Theoretical Informatics and Applications

It often occurs that local copies of a text are modified by users but that the local modifications are not synchronized (thus allowing the merged text to become the source for later editions) until later when, for instance the network connection is reestablished. Since text editions usually affect a small fraction of the whole content, the history of edit operations provides a compact representation of the modified file. In this paper, we define a normal form for these records which will...

Normalization of edit sequences for text synchronization

Rafael C. CarrascoAlexander Sánchez Díaz — 2011

RAIRO - Theoretical Informatics and Applications

It often occurs that local copies of a text are modified by users but that the local modifications are not synchronized (thus allowing the merged text to become the source for later editions) until later when, for instance the network connection is reestablished. Since text editions usually affect a small fraction of the whole content, the history of edit operations provides a compact representation of the modified file. In this paper, we define a normal form for these records which will...

A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata

Rafael C. CarrascoJan Daciuk — 2009

RAIRO - Theoretical Informatics and Applications

We describe a technique that maps unranked trees to arbitrary hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to other hashing techniques based on automata, our procedure builds a pseudo-minimal DTA for this purpose. A pseudo-minimal automaton may be larger than the minimal one accepting the same language but, in turn, it contains proper elements (states or transitions which are unique) for every input accepted by the automaton. Therefore, pseudo-minimal DTA...

Learning deterministic regular grammars from stochastic samples in polynomial time

Rafael C. CarrascoJose Oncina — 2010

RAIRO - Theoretical Informatics and Applications

In this paper, the identification of stochastic regular languages is addressed. For this purpose, we propose a class of algorithms which allow for the identification of the structure of the minimal stochastic automaton generating the language. It is shown that the time needed grows only linearly with the size of the sample set and a measure of the complexity of the task is provided. Experimentally, our implementation proves very fast for application purposes.

Page 1

Download Results (CSV)