Search results for "Prefix"
showing 7 items of 57 documents
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.
Normal, Abby Normal, Prefix Normal
2014
A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present results about the number \(\textit{pnw}(n)\) of prefix normal words of length n, showing that \(\textit{pnw}(n) =\Omega\left(2^{n - c\sqrt{n\ln n}}\right)\) for some c and \(\textit{pnw}(n) = O \left(\frac{2^n (\ln n)^2}{n}\right)\). We introduce efficient algorithms for testing the prefix normal property and a “mechanical algorithm” for computing prefix normal forms. We also include games which can be played with prefix normal words. In these games Alice wishes t…
Reversive constructions in Latin: the case of re- (and dis-)
2019
This paper proposes a cognitive account on re- and dis- verbs based on the scrutiny of the Plautine corpus and Cato’s De agricultura. Re- and dis- exhibit significant differences as to the manner in which they come to a reversive function, and these differences can be traced back to the basic conceptual import of the two prefixes: while dis- is schematically connected with the idea of separation into two parts, re- basically refers to a rearward/reditive trajectory, connecting a point that has already been reached to the starting point. On the basis of this description, I analyze the semantic network of re- and dis- and the role of their conceptual structure in the spread from spatial to re…
Statistical properties of general Markov dynamical sources: applications to information theory
2004
In \textitDynamical sources in information theory: fundamental intervals and word prefixes, B. Vallée studies statistical properties of words generated by dynamical sources. This is done using generalized Ruelle operators. The aim of this article is to generalize sources for which the results hold. First, we avoid the use of Grotendieck theory and Fredholm determinants, this allows dynamical sources that cannot be extended to a complex disk or that are not analytic. Second, we consider Markov sources: the language generated by the source over an alphabet \textbfM is not necessarily \textbfM^*.
On Prefix Normal Words
2011
We present a new class of binary words: the prefix normal words. They are defined by the property that for any given length $k$, no factor of length $k$ has more $a$'s than the prefix of the same length. These words arise in the context of indexing for jumbled pattern matching (a.k.a. permutation matching or Parikh vector matching), where the aim is to decide whether a string has a factor with a given multiplicity of characters, i.e., with a given Parikh vector. Using prefix normal words, we give the first non-trivial characterization of binary words having the same set of Parikh vectors of factors. We prove that the language of prefix normal words is not context-free and is strictly contai…
Primární substantiva jako základ pro prefixální derivaci
2018
This article discusses a data set of about 50 derived words built with different international and Slavic prefixes. Base words fo r derivation are nouns which denote human beings in Czech and Polish languages. These base words form thefollowing subclasses: names ofaffinity (otec - ojciec father', dcera - córka 'daughter', tchyne - teściowa 'mother-in-lawj; physical and mental qualities (baba - baba 'old woman', brunet - brunet 'brunette', dlte - dziecko 'child'); knighthood(król-król 'king', clsar-cesarz 'emperorj andadministrative titles (rektor-rektor 'president', sekretar- sekretarz 'secretaryj; professions (kuryr - kurier 'messenger', kustod - kustosz 'custodian', lektor - lektor 'lectu…
Aspecte i prefixació verbal en català antic
2021
The paper examines aspectual and selectional properties of Old Catalan prefixed verbs in comparison with their non prefixed counterparts. We ground our analysis on Talmy’s (1985, 2000) notion of verb framed and satellite framed languages and on Mateu (2002, 2003) and Mateu & Rigau (2002) theory of lexical structure, and we argue that telicity and other aspectual properties associated with prefixed verbs are by effects derived from the semantic value of the prefix together with the lexical structure they give rise to. Taking as a case in point the a- prefix of verbs such as «acórrer», we analyse the prefix as a path which relates a figure (the grammatical subject) to a ground (the argument i…