Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDirect definition of a ternary infinite square-free sequence
77
0
0.0
(
0
)
Added by
Tetsuo Kurosaki
Publication date
2007
fields
Informatics Engineering
and research's language is
English
Authors
Tetsuo Kurosaki
Ask ChatGPT about the research
No Arabic abstract
We propose a new ternary infinite (even full-infinite) square-free sequence. The sequence is defined both by an iterative method and by a direct definition. Both definitions are analogous to those of the Thue-Morse sequence. The direct definition is given by a deterministic finite automaton with output. In short, the sequence is automatic.
rate research
Read More
Partly in service of exploring the formal basis for Georgetown Universitys AvesTerra database structure, we formalize a recursive hypergraph data structure, which we call an ubergraph.
Distance-preserving mappings (DPMs) are mappings from the set of all q-ary vectors of a fixed length to the set of permutations of the same or longer length such that every two distinct vectors are mapped to permutations with the same or even larger Hamming distance than that of the vectors. In this paper, we propose a construction of DPMs from ternary vectors. The constructed DPMs improve the lower bounds on the maximal size of permutation arrays.
Let $S_{N}(P)$ be the poset obtained by adding a dummy vertex on each diagonal edge of the $N$s of a finite poset $P$. We show that $S_{N}(S_{N}(P))$ is $N$-free. It follows that this poset is the smallest $N$-free barycentric subdivision of the diagram of $P$, poset whose existence was proved by P.A. Grillet. This is also the poset obtained by the algorithm starting with $P_0:=P$ and consisting at step $m$ of adding a dummy vertex on a diagonal edge of some $N$ in $P_m$, proving that the result of this algorithm does not depend upon the particular choice of the diagonal edge choosen at each step. These results are linked to drawing of posets.
We consider a search problem on a $2$-dimensional infinite grid with a single mobile agent. The goal of the agent is to find her way home, which is located in a grid cell chosen by an adversary. Initially, the agent is provided with an infinite sequence of instructions, that dictate the movements performed by the agent. Each instruction corresponds to a movement to an adjacent grid cell and the set of instructions can be a function of the initial locations of the agent and home. The challenge of our problem stems from faults in the movements made by the agent. In every step, with some constant probability $0 leq p leq 1$, the agent performs a random movement instead of following the current instruction. This paper provides two results on this problem. First, we show that for some values of $p$, there does not exist any set of instructions that guide the agent home in finite expected time. Second, we complement this impossibility result with an algorithm that, for sufficiently small values of $p$, yields a finite expected hitting time for home. In particular, we show that for any $p < 1$, our approach gives a hitting rate that decays polynomially as a function of time. In that sense, our approach is far superior to a standard random walk in terms of hitting time. The main contribution and take-home message of this paper is to show that, for some value of $0.01139dots < p < 0.6554ldots$, there exists a phase transition on the solvability of the problem.
This contribution is devoted to the study of positional numeration systems with negative base introduced by Ito and Sadahiro in 2009, called (-beta)-expansions. We give an admissibility criterion for more general case of (-beta)-expansions and discuss the properties of the set of (-beta)-integers. We give a description of distances within this set and show that this set can be coded by an infinite word over an infinite alphabet, which is a fixed point of a non-erasing non-trivial morphism.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
