Search results for "forbidden"
showing 10 items of 36 documents
Alignment-free sequence comparison using absent words
2018
Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an {\em absent word} of some sequence if it does not oc…
Linear-time sequence comparison using minimal absent words & applications
2016
Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realized by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as q-gram distance, are usually computed in time linear with respect to the length of the sequences. In this article, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an absent word of some sequence if it does not occur in…
A Characterization of Bispecial Sturmian Words
2012
A finite Sturmian word w over the alphabet {a,b} is left special (resp. right special) if aw and bw (resp. wa and wb) are both Sturmian words. A bispecial Sturmian word is a Sturmian word that is both left and right special. We show as a main result that bispecial Sturmian words are exactly the maximal internal factors of Christoffel words, that are words coding the digital approximations of segments in the Euclidean plane. This result is an extension of the known relation between central words and primitive Christoffel words. Our characterization allows us to give an enumerative formula for bispecial Sturmian words. We also investigate the minimal forbidden words for the set of Sturmian wo…
Mesonic enhancement of the weak axial charge and its effect on the half-lives and spectral shapes of first-forbidden J+↔J− decays
2018
The effects of the enhancement of the axial-charge matrix element γ5 were studied in medium heavy and heavy nuclei for first-forbidden J+↔J− decay transitions using the nuclear shell model. Noticeable dependence on the enhancement ϵMEC of the axial-charge matrix element, as well as on the value of the axial-vector coupling constant gA was found in the spectral shapes of $^{93}$Y, $^{95}$Sr, and $^{97}$Y. The importance of the spectrum of $^{138}$Cs in the determination of gA is discussed. Half-life analyses in the A≈95 and A≈135 regions were done, and consistent results gA≈0.90, 0.75, and 0.65, corresponding to the three enhancement scenarios ϵMEC=1.4, 1.7, and 2.0, were obtained. Connectio…
Restricted 123-avoiding Baxter permutations and the Padovan numbers
2007
AbstractBaxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.
Automata and differentiable words
2011
We exhibit the construction of a deterministic automaton that, given k > 0, recognizes the (regular) language of k-differentiable words. Our approach follows a scheme of Crochemore et al. based on minimal forbidden words. We extend this construction to the case of C\infinity-words, i.e., words differentiable arbitrary many times. We thus obtain an infinite automaton for representing the set of C\infinity-words. We derive a classification of C\infinity-words induced by the structure of the automaton. Then, we introduce a new framework for dealing with \infinity-words, based on a three letter alphabet. This allows us to define a compacted version of the automaton, that we use to prove that ev…
Graph languages defined by systems of forbidden structures: A survey
1988
This paper deals with different ways of defining graph languages. These are the so-called forbidden structures. Some results on decision problems, their complexity, and set theoretic closure properties are scetched. A normal form, the minimal systems, are given. Finally the influence of the different kinds of forbidden structures on the descriptive power of the systems is shown.
Still Going “Grey” After All These Years? Export Restraint Agreements and the WTO
2013
This chapter assesses how the dual strategy that aimed to eliminate "grey area" measures has worked out in practice, also in the light of the protectionist pressures unleashed by the current economic crisis. After providing a brief overview of the historic proliferation of these measures, it discusses whether the attempt to render ordinary safeguard measures a more attractive alternative to voluntary restraint agreements (VRAs) has worked in practice. The chapter analyses some of the intrinsic and extrinsic weaknesses of the ban itself. The chapter reviews some cases of export-restraint agreements arguably falling within the exceptions to the ban enshrined in Art. 11.1.C. This work has exam…
Cyclic Complexity of Words
2014
We introduce and study a complexity function on words $c_x(n),$ called \emph{cyclic complexity}, which counts the number of conjugacy classes of factors of length $n$ of an infinite word $x.$ We extend the well-known Morse-Hedlund theorem to the setting of cyclic complexity by showing that a word is ultimately periodic if and only if it has bounded cyclic complexity. Unlike most complexity functions, cyclic complexity distinguishes between Sturmian words of different slopes. We prove that if $x$ is a Sturmian word and $y$ is a word having the same cyclic complexity of $x,$ then up to renaming letters, $x$ and $y$ have the same set of factors. In particular, $y$ is also Sturmian of slope equ…
On the Structure of Bispecial Sturmian Words
2013
A balanced word is one in which any two factors of the same length contain the same number of each letter of the alphabet up to one. Finite binary balanced words are called Sturmian words. A Sturmian word is bispecial if it can be extended to the left and to the right with both letters remaining a Sturmian word. There is a deep relation between bispecial Sturmian words and Christoffel words, that are the digital approximations of Euclidean segments in the plane. In 1997, J. Berstel and A. de Luca proved that \emph{palindromic} bispecial Sturmian words are precisely the maximal internal factors of \emph{primitive} Christoffel words. We extend this result by showing that bispecial Sturmian wo…