Pattern avoidance in partial words over a ternary alphabet

Adam Gągol

Displaying similar documents to “Pattern avoidance in partial words over a ternary alphabet”

On the joint entropy of $d$ -wise-independent variables

Dmitry Gavinsky, Pavel Pudlák (2016)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

How low can the joint entropy of $n$ $d$ -wise independent (for $d \geq 2$ ) discrete random variables be, subject to given constraints on the individual distributions (say, no value may be taken by a variable with probability greater than $p$ , for $p < 1$ )? This question has been posed and partially answered in a recent work of Babai [Entropy versus pairwise independence (preliminary version), http://people.cs.uchicago.edu/ laci/papers/13augEntropy.pdf, 2013]. In this paper we improve some...

Topological disjointness from entropy zero systems

Wen Huang, Kyewon Koh Park, Xiangdong Ye (2007)

Bulletin de la Société Mathématique de France

Similarity:

The properties of topological dynamical systems $(X, T)$ which are disjoint from all minimal systems of zero entropy, $ℳ_{0}$ , are investigated. Unlike the measurable case, it is known that topological $K$ -systems make up a proper subset of the systems which are disjoint from $ℳ_{0}$ . We show that $(X, T)$ has an invariant measure with full support, and if in addition $(X, T)$ is transitive, then $(X, T)$ is weakly mixing. A transitive diagonal system with only one minimal point is constructed. As a consequence, there exists...

On some nonlinear nonhomogeneous elliptic unilateral problems involving noncontrollable lower order terms with measure right hand side

C. Yazough, E. Azroul, H. Redwane (2013)

Applicationes Mathematicae

Similarity:

We prove the existence of entropy solutions to unilateral problems associated to equations of the type $A u - d i v (ϕ (u)) = μ \in L ¹ (Ω) + W^{- 1, p^{'} (\cdot)} (Ω)$ , where A is a Leray-Lions operator acting from $W ₀^{1, p (\cdot)} (Ω)$ into its dual $W^{- 1, p (\cdot)} (Ω)$ and $ϕ \in C ⁰ (ℝ, ℝ^{N})$ .

On the directional entropy of ℤ²-actions generated by cellular automata

M. Courbage, B. Kamiński (2002)

Studia Mathematica

Similarity:

We show that for any cellular automaton (CA) ℤ²-action Φ on the space of all doubly infinite sequences with values in a finite set A, determined by an automaton rule $F = F_{[l, r]}$ , l,r ∈ ℤ, l ≤ r, and any Φ-invariant Borel probability measure, the directional entropy $h_{v ⃗} (Φ)$ , v⃗= (x,y) ∈ ℝ², is bounded above by $m a x (| z_{l} |, | z_{r} |) l o g A$ if $z_{l} z_{r} \geq 0$ and by $| z_{r} - z_{l} |$ in the opposite case, where $z_{l} = x + l y$ , $z_{r} = x + r y$ . We also show that in the class of permutative CA-actions the bounds are attained if the measure considered is uniform Bernoulli.

ε-Entropy and moduli of smoothness in $L^{p}$ -spaces

A. Kamont (1992)

Studia Mathematica

Similarity:

The asymptotic behaviour of ε-entropy of classes of Lipschitz functions in $L^{p} (^{d})$ is obtained. Moreover, the asymptotics of ε-entropy of classes of Lipschitz functions in $L^{p} (ℝ^{d})$ whose tail function decreases as $O (λ^{- γ})$ is obtained. In case p = 1 the relation between the ε-entropy of a given class of probability densities on $ℝ^{d}$ and the minimax risk for that class is discussed.

Measures of maximal entropy for random $β$ -expansions

Karma Dajani, Martijn de Vries (2005)

Journal of the European Mathematical Society

Similarity:

Let $β > 1$ be a non-integer. We consider $β$ -expansions of the form $\sum_{i = 1}^{\infty} d_{i} / β^{i}$ , where the digits ${(d_{i})}_{i \geq 1}$ are generated by means of a Borel map $K_{β}$ defined on ${0, 1}^{ℕ} \times [0, ⌊ β ⌋ / (β - 1)]$ . We show that $K_{β}$ has a unique mixing measure $ν_{β}$ of maximal entropy with marginal measure an infinite convolution of Bernoulli measures. Furthermore, under the measure $ν_{β}$ the digits ${(d_{i})}_{i \geq 1}$ form a uniform Bernoulli process. In case 1 has a finite greedy expansion with positive coefficients, the measure of maximal entropy is Markov. We also discuss the uniqueness...

Interaction between cellularity of Alexandroff spaces and entropy of generalized shift maps

Fatemah Ayatollah Zadeh Shirazi, Sahar Karimzadeh Dolatabad, Sara Shamloo (2016)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In the following text for a discrete finite nonempty set $K$ and a self-map $ϕ : X \to X$ we investigate interaction between different entropies of generalized shift $σ_{ϕ} : K^{X} \to K^{X}$ , ${(x_{α})}_{α \in X} \mapsto {(x_{ϕ (α)})}_{α \in X}$ and cellularities of some Alexandroff topologies on $X$ .

Jumps of entropy for $C^{r}$ interval maps

David Burguet (2015)

Fundamenta Mathematicae

Similarity:

We study the jumps of topological entropy for $C^{r}$ interval or circle maps. We prove in particular that the topological entropy is continuous at any $f \in C^{r} ([0, 1])$ with $h_{t o p} (f) > (l o g ⁺ | | f^{'} {| |}_{\infty}) / r$ . To this end we study the continuity of the entropy of the Buzzi-Hofbauer diagrams associated to $C^{r}$ interval maps.

Hyperbolic measure of maximal entropy for generic rational maps of $ℙ^{k}$

Gabriel Vigny (2014)

Annales de l’institut Fourier

Similarity:

Let $f$ be a dominant rational map of $ℙ^{k}$ such that there exists $s < k$ with $λ_{s} (f) > λ_{l} (f)$ for all $l$ . Under mild hypotheses, we show that, for $A$ outside a pluripolar set of $Aut (ℙ^{k})$ , the map $f \circ A$ admits a hyperbolic measure of maximal entropy $log λ_{s} (f)$ with explicit bounds on the Lyapunov exponents. In particular, the result is true for polynomial maps hence for the homogeneous extension of $f$ to $ℙ^{k + 1}$ . This provides many examples where non uniform hyperbolic dynamics is established. One of the key tools is to approximate...

Invariant densities for random $β$ -expansions

Karma Dajani, Martijn de Vries (2007)

Journal of the European Mathematical Society

Similarity:

Let $β > 1$ be a non-integer. We consider expansions of the form $\sum_{i = 1}^{\infty} d_{i} / β^{i}$ , where the digits ${(d_{i})}_{i \geq 1}$ are generated by means of a Borel map $K_{β}$ defined on ${0, 1}^{ℕ} \times [0, ⌊ β ⌋ (β - 1)]$ . We show existence and uniqueness of a $K_{β}$ -invariant probability measure, absolutely continuous with respect to $m_{p} \otimes λ$ , where $m_{p}$ is the Bernoulli measure on ${0, 1}^{ℕ}$ with parameter $p$ ( $0 < p < 1$ ) and $λ$ is the normalized Lebesgue measure on $[0, ⌊ β ⌋ (β - 1)]$ . Furthermore, this measure is of the form $m_{p} \otimes μ_{β, p}$ , where $μ_{β, p}$ is equivalent to $λ$ . We prove that the measure of maximal entropy and $m_{p} \otimes λ$ are mutually...

Comparison of two methods for approximation of probability distributions with prescribed marginals

Albert Pérez, Milan Studený (2007)

Kybernetika

Similarity:

Let $P$ be a discrete multidimensional probability distribution over a finite set of variables $N$ which is only partially specified by the requirement that it has prescribed given marginals ${P_{A}; A \in 𝒮}$ , where $𝒮$ is a class of subsets of $N$ with $⋃ 𝒮 = N$ . The paper deals with the problem of approximating $P$ on the basis of those given marginals. The divergence of an approximation $\hat{P}$ from $P$ is measured by the relative entropy $H (P | \hat{P})$ . Two methods for approximating $P$ are compared. One of them uses formerly introduced...

Coincidence for substitutions of Pisot type

Marcy Barge, Beverly Diamond (2002)

Bulletin de la Société Mathématique de France

Similarity:

Let $ϕ$ be a substitution of Pisot type on the alphabet $𝒜 = {1, 2, ..., d}$ ; $ϕ$ satisfies theif for every $i, j \in 𝒜$ , there are integers $k, n$ such that $ϕ^{n} (i)$ and $ϕ^{n} (j)$ have the same $k$ -th letter, and the prefixes of length $k - 1$ of $ϕ^{n} (i)$ and $ϕ^{n} (j)$ have the same image under the abelianization map. We prove that the strong coincidence condition is satisfied if $d = 2$ and provide a partial result for $d \geq 2$ .