Embedding odometers in cellular automata

Ethan M. Coven; Reem Yassawi

Displaying similar documents to “Embedding odometers in cellular automata”

Watson-Crick pushdown automata

Kingshuk Chatterjee, Kumar S. Ray (2017)

Kybernetika

Similarity:

A multi-head 1-way pushdown automaton with $k$ heads is a pushdown automaton with $k$ 1-way read heads on the input tape and a stack. It was previously shown that the deterministic variant of the model cannot accept all the context free languages. In this paper, we introduce a 2-tape, 2-head model namely Watson-Crick pushdown automata where the content of the second tape is determined using a complementarity relation, similar to Watson-Crick automata. We show computational powers of nondeterministic...

Multi-island finite automata and their even computation

Dušan Kolář, Alexander Meduna, Martin Tomko (2021)

Kybernetika

Similarity:

This paper discusses $n$ -island finite automata whose transition graphs can be expressed as $n$ -member sequences of islands $i_{1}, i_{2}, \dots, i_{n}$ , where there is a bridge leaving $i_{j}$ and entering $i_{j + 1}$ for each $1 \leq j \leq n - 1$ . It concentrates its attention on even computation defined as any sequence of moves during which these automata make the same number of moves in each of the islands. Under the assumption that these automata work only in an evenly computational way, the paper proves its main result stating that $n$ -island finite...

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.

Automata, algebraicity and distribution of sequences of powers

Jean-Paul Allouche, Jean-Marc Deshouillers, Teturo Kamae, Tadahiro Koyanagi (2001)

Annales de l’institut Fourier

Similarity:

Let $K$ be a finite field of characteristic $p$ . Let $K ((x))$ be the field of formal Laurent series $f (x)$ in $x$ with coefficients in $K$ . That is, $f (x) = \sum_{n = n_{0}}^{\infty} f_{n} x^{n}$ with $n_{0} \in 𝐙$ and $f_{n} \in K (n = n_{0}, n_{0} + 1, \dots)$ . We discuss the distribution of ${({f^{m}})}_{m = 0, 1, 2, \dots}$ for $f \in K ((x))$ , where ${f} : = \sum_{n = 0}^{\infty} f_{n} x^{n} \in K [[x]]$ denotes the nonnegative part of $f \in K ((x))$ . This is a little different from the real number case where the fractional part that excludes constant term (digit of order 0) is considered. We give an alternative proof of a result by De Mathan obtaining the generic...

Formal translation directed by $L R$ parsing

Bořivoj Melichar (1992)

Kybernetika

Similarity:

Equality sets for recursively enumerable languages

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We consider shifted equality sets of the form $E_{G} (a, g_{1}, g_{2}) = {w ∣ g_{1} (w) = a g_{2} (w)}$ , where $g_{1}$ and $g_{2}$ are nonerasing morphisms and $a$ is a letter. We are interested in the family consisting of the languages $h (E_{G} (J))$ , where $h$ is a coding and $E_{G} (J)$ is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language $L \subseteq A^{*}$ is a projection of a shifted equality set, that is, $L = π_{A} (E_{G} (a, g_{1}, g_{2}))$ for some (nonerasing) morphisms $g_{1}$ and $g_{2}$ and a letter $a$ , where $π_{A}$ deletes the letters not in $A$ . Then...

Pattern avoidance in partial words over a ternary alphabet

Adam Gągol (2015)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with $m$ distinct variables and of length at least $2^{m}$ is avoidable over a ternary alphabet and if the length is at least $3 \cdot 2^{m - 1}$ it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words – sequences, in which some characters are left “blank”. Using method of entropy compression, we obtain the partial words version of the theorem for ternary words. ...

The range of non-linear natural polynomials cannot be context-free

Dömötör Pálvölgyi (2020)

Kybernetika

Similarity:

Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i. e., $L = {f (n) ∣ n \in ℕ} \subseteq ℕ$ . We show that the base- $q$ representation of $L$ is a context-free language if and only if $f$ is linear, answering a question of Shallit. The proof is based on a new criterion for context-freeness, which is a combination of the Interchange lemma and a generalization of the Pumping lemma.

On the quartic character of quadratic units

Zhi-Hong Sun (2013)

Acta Arithmetica

Similarity:

Let ℤ be the set of integers, and let (m,n) be the greatest common divisor of integers m and n. Let p be a prime of the form 4k+1 and p = c²+d² with c,d ∈ ℤ, $d = 2^{r} d ₀$ and c ≡ d₀ ≡ 1 (mod 4). In the paper we determine ${(b + \sqrt (b ² + 4^{α}) / 2)}^{(p - 1) / 4)} (m o d p)$ for p = x²+(b²+4α)y² (b,x,y ∈ ℤ, 2∤b), and ${(2 a + \sqrt 4 a ² + 1)}^{(p - 1) / 4} (m o d p)$ for p = x²+(4a²+1)y² (a,x,y∈ℤ) on the condition that (c,x+d) = 1 or (d₀,x+c) = 1. As applications we obtain the congruence for $U_{(p - 1) / 4} (m o d p)$ and the criterion for $p | U_{(p - 1) / 8}$ (if p ≡ 1 (mod 8)), where Uₙ is the Lucas sequence given by U₀ = 0, U₁ = 1 and...