Search results for "Suffix"
showing 5 items of 75 documents
Les locutions espagnoles : observation de quelques schémas productifs
2019
International audience
On the suffix automaton with mismatches
2007
International audience; 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 value of the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches.
A trie-based approach for compacting automata
2004
International audience; 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., as it uses less nodes, still with arcs labeled by single characters.
The asymmetric Path-conflation pattern of GO and COME verbs in Aymara
2019
This paper investigates the basic motion verbs sara ‘go’ and juta ‘come’ in Aymara, an indigenous language of the Andes, within the framework of Talmy’s lexical typology (Talmy 2000). In a crosslinguistic perspective, ‘come’ and ‘go’ are assumed to be deictically complementary and have been represented as a kind of Path-conflating verbs, i.e. verbs that include the deictic component of Path in their lexical semantics, which is respectively the direction ‘toward the speaker’ vs that ‘not toward the speaker’. Data from Aymara show in fact that ‘come’ and ‘go’ exhibit an asymmetrical Path-conflation pattern: ‘come’ does inherently entail deictic motion toward the speaker, whereas ‘go’ indicate…
Recursion at the crossroads of sequence modeling, random trees, stochastic algorithms and martingales
2013
This monograph synthesizes several studies spanning from dynamical systems in the statistical analysis of sequences, to analysis of algorithms in random trees and discrete stochastic processes. These works find applications in various fields ranging from biological sequences to linear regression models, branching processes, through functional statistics and estimates of risk indicators for insurances. All the established results use, in one way or another, the recursive property of the structure under study, by highlighting invariants such as martingales, which are at the heart of this monograph, as tools as well as objects of study.