Search results for "Suffix"
showing 10 items of 75 documents
Enumeration and Structure of Trapezoidal Words
2013
Trapezoidal words are words having at most $n+1$ distinct factors of length $n$ for every $n\ge 0$. They therefore encompass finite Sturmian words. We give combinatorial characterizations of trapezoidal words and exhibit a formula for their enumeration. We then separate trapezoidal words into two disjoint classes: open and closed. A trapezoidal word is closed if it has a factor that occurs only as a prefix and as a suffix; otherwise it is open. We investigate open and closed trapezoidal words, in relation with their special factors. We prove that Sturmian palindromes are closed trapezoidal words and that a closed trapezoidal word is a Sturmian palindrome if and only if its longest repeated …
A Classification of Trapezoidal Words
2011
Trapezoidal words are finite words having at most n+1 distinct factors of length n, for every n>=0. They encompass finite Sturmian words. We distinguish trapezoidal words into two disjoint subsets: open and closed trapezoidal words. A trapezoidal word is closed if its longest repeated prefix has exactly two occurrences in the word, the second one being a suffix of the word. Otherwise it is open. We show that open trapezoidal words are all primitive and that closed trapezoidal words are all Sturmian. We then show that trapezoidal palindromes are closed (and therefore Sturmian). This allows us to characterize the special factors of Sturmian palindromes. We end with several open problems.
The rightmost equal-cost position problem.
2013
LZ77-based compression schemes compress the input text by replacing factors in the text with an encoded reference to a previous occurrence formed by the couple (length, offset). For a given factor, the smallest is the offset, the smallest is the resulting compression ratio. This is optimally achieved by using the rightmost occurrence of a factor in the previous text. Given a cost function, for instance the minimum number of bits used to represent an integer, we define the Rightmost Equal-Cost Position (REP) problem as the problem of finding one of the occurrences of a factor whose cost is equal to the cost of the rightmost one. We present the Multi-Layer Suffix Tree data structure that, for…
Open and Closed Prefixes of Sturmian Words
2013
A word is closed if it contains a proper factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We deal with the sequence of open and closed prefixes of Sturmian words and prove that this sequence characterizes every finite or infinite Sturmian word up to isomorphisms of the alphabet. We then characterize the combinatorial structure of the sequence of open and closed prefixes of standard Sturmian words. We prove that every standard Sturmian word, after swapping its first letter, can be written as an infinite product of squares of reversed standard words.
Minimal change list for Lucas strings and some graph theoretic consequences
2005
AbstractWe give a minimal change list for the set of order p length-n Lucas strings, i.e., the set of length-n binary strings with no p consecutive 1's nor a 1ℓ prefix and a 1m suffix with ℓ+m⩾p. The construction of this list proves also that the order p n-dimensional Lucas cube has a Hamiltonian path if and only if n is not a multiple of p+1, and its second power always has a Hamiltonian path.
From Nerode's congruence to Suffix Automata with mismatches
2009
AbstractIn this paper we focus on the minimal deterministic finite automaton Sk that recognizes the set of suffixes of a word w up to k errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with Sk. This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of Sk to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the…
What drives morphological change?
2014
This paper investigates the role of syntactic, semantic, and lexical factors in the diachronic development of German nominalization patterns. Drawing on an extensive corpus analysis of Early New High German and New High German texts, it is shown that (a) deverbal nominals in the suffix -ung tend to develop more reified meaning variants, which is reflected in the syntactic patterns in which the word-formation products preferentially occur, and (b) infinitival nominalization becomes more productive and is established as the new default word-formation pattern deriving nouns from verbs. These considerations fit in neatly with a cognitively-oriented theory of word-formation change situated in th…
Schema Unification and Morphological Productivity: A Diachronic Perspective
2018
Unified schemas which allow for deriving multiply complex word-formation products are a central concept in Construction Morphology (CxM). Based on examples such as un-V-able formations in English, it has been argued in the framework of Construction Morphology that unified schemas (in this case: [un[V-able]A]A) can be conceived of as short cuts in coining new complex words. In this paper, we explore three prospective cases of schema unification and discuss what kind of evidence supports the assumption of unified schemas. The first two case studies are diachronic in nature. Drawing on corpus analyses of data from the Early New High German period (1350–1650) and from the early stages of New Hi…
Two Reflected Gray Code-Based Orders on Some Restricted Growth Sequences
2014
We consider two order relations: that induced by the m-ary reflected Gray code and a suffix partitioned variation of it. We show that both of them when applied to some sets of restricted growth sequences still yield Gray codes. These sets of sequences are: subexcedant and ascent sequences, restricted growth functions and staircase words. In particular, we give the first suffix partitioned Gray codes for restricted growth f unctions and ascent sequences; these latter sequences code various combinatorial classes as interval orders, upper triangular matrices without zero rows and zero columns whose non-negative integer entries sum up to n, and certain pattern-avoiding permutations. For each Gr…
Créativité et expressivité: le cas des "diminutifs" espagnols.
2022
Toute unité lexicale peut être considérée comme subjective, puisque les langues ne font jamais que contraindre l’individu à certains modes d’interprétations lors de sa production discursive. Mais cette subjectivité langagière collective n’est pas la subjectivité individuelle dont fait preuve l’énonciateur procédant à une création lexicale. Dans le cadre de la langue espagnole, il est un cas de dérivation d’une grande productivité : la formation diminutive. La richesse de celle-ci s’observe à ...