Origami fold as algebraic graph rewriting

We formalize paper fold (origami) by graph rewriting. Origami construction is abstractly described by a rewriting system (O,?)$(\mathbb{O},?)$, where O$\mathbb{O}$ is the set of abstract origamis and ?$?$ is a binary relation on O$\mathbb{O}$, that models fold  . An abstract origami is a structure (Π,∽,?)$(\Pi ,\backsim ,?)$, where Π$\Pi$ is a set of faces constituting an origami, and ∽$\backsim$ and ?$?$ are binary relations on Π$\Pi$, each representing adjacency and superposition relations between the faces.     

Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

Algorithms for a class of infinite permutation groups

Motivated by the famous 3n+1$3n+1$ conjecture, we call a mapping from Z$\mathbb{Z}$ to Z$\mathbb{Z}$residue-class-wise affine   if there is a positive integer m$m$ such that it is affine on residue classes (mod m$m$). This article describes a collection of algorithms and methods for computation in permutation groups and monoids formed by residue-class-wise affine mappings.     

Rational two-parameter families of spheres and rational offset surfaces

The present paper investigates two-parameter families of spheres in R³${\mathbb{R}}^3$ and their corresponding two-dimensional surfaces Φ$\Phi$ in R⁴${\mathbb{R}}^4$. Considering a rational surface Φ$\Phi$ in R⁴${\mathbb{R}}^4$, the envelope surface Ψ$\Psi$ of the corresponding family of spheres in R³${\mathbb{R}}^3$ is typically non-rational. Using a classical sphere-geometric approach, we prove that the envelope surface Ψ$\Psi$ and its offset surfaces admit rational parameterizations if and only if Φ$\Phi$ is a rational sub-variety of a rational isotropic hyper-surface in R⁴${\mathbb{R}}^4$. The close relation between the envelope surfaces Ψ$\Psi$ and rational offset surfaces in R³${\mathbb{R}}^3$ is elaborated in detail. This connection leads to explicit rational parameterizations for all rational surfaces Φ$\Phi$ in R⁴${\mathbb{R}}^4$ whose corresponding two-parameter families of spheres possess envelope surfaces admitting rational parameterizations. Finally we discuss several classes of surfaces sharing this property.     

Modular Las Vegas algorithms for polynomial absolute factorization

Let f(X,Y)∈Z[X,Y]$f(X,Y)\in \mathbb{Z}[X,Y]$ be an irreducible polynomial over Q$\mathbb{Q}$. We give a Las Vegas absolute irreducibility test based on a property of the Newton polytope of f$f$, or more precisely, of f$f$ modulo some prime integer p$p$. The same idea of choosing a p$p$ satisfying some prescribed properties together with LLL$LLL$ is used to provide a new strategy for absolute factorization of f(X,Y)$f(X,Y)$. We present our approach in the bivariate case but the techniques extend to the multivariate case. Maple computations show that it is efficient and promising as we are able to construct the algebraic extension containing one absolute factor of a polynomial of degree up to 400.     

Adaptive timeliness of consensus in presence of crash and timing faults

The Δ$\mathrm{\Delta }$-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Δ$\mathrm{\Delta }$ (Δ$\mathrm{\Delta }$-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Δ$\mathrm{\Delta }$-timed uniform consensus problem in presence of _fc$f_{\mathrm{c}}$ crash processes and _ft$f_{\mathrm{t}}$ timing-faulty processes, and propose a Δ$\mathrm{\Delta }$-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Δ$\mathrm{\Delta }$-timed uniform consensus when at least _ft+1$f_{\mathrm{t}}+1$ correct processes exist in the system. If the system has less than _ft+1$f_{\mathrm{t}}+1$ correct processes, the algorithm cannot solve the Δ$\mathrm{\Delta }$-timed uniform consensus. However, as long as _ft+1$f_{\mathrm{t}}+1$ processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ$\mathrm{\Delta }$-timed uniform consensus algorithm tolerating up to _ft$f_{\mathrm{t}}$ timing-faulty processes requires that the system has at least _ft+1$f_{\mathrm{t}}+1$ correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any Δ$\mathrm{\Delta }$-timed uniform consensus algorithm tolerating up to _ft$f_{\mathrm{t}}$ timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than _ft+1$f_{\mathrm{t}}+1$ non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness.     

A generalization of Cobham’s theorem to automata over real numbers

This article studies the expressive power of finite-state automata recognizing sets of real numbers encoded positionally. It is known that the sets that are definable in the first-order additive theory of real and integer variables 〈R,Z,+,<〉$〈\mathbb{R},\mathbb{Z},+,<〉$ can all be recognized by weak deterministic Büchi automata, regardless of the encoding base r>1$r>1$. In this article, we prove the reciprocal property, i.e., a subset of R$\mathbb{R}$ that is recognizable by weak deterministic automata in every base r>1$r>1$ is necessarily definable in 〈R,Z,+,<〉$〈\mathbb{R},\mathbb{Z},+,<〉$. This result generalizes to real numbers the well-known Cobham’s theorem on the finite-state recognizability of sets of integers. Our proof gives interesting insight into the internal structure of automata recognizing sets of real numbers, which may lead to efficient data structures for handling these sets.     

The number of roots of a lacunary bivariate polynomial on a line

We prove that a polynomial f∈R[x,y]$f\in \mathbb{R}[x,y]$ with t$t$ non-zero terms, restricted to a real line y=ax+b$y=ax+b$, either has at most 6t−4$6t-4$ zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial y−ax−b∈K[x,y]$y-ax-b\in K[x,y]$ divides a lacunary polynomial f∈K[x,y]$f\in K[x,y]$, where K$K$ is a real number field. The number of bit operations performed by the algorithm is polynomial in the number of non-zero terms of f$f$, in the logarithm of the degree of f$f$, in the degree of the extension K/Q$K/\mathbb{Q}$ and in the logarithmic height of a$a$, b$b$ and f$f$.     

Compatibility of unrooted phylogenetic trees is FPT

A collection of _T1,_T2,…,_Tk$T_1,T_2,\dots ,T_k$ of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible   if there exists a tree T$T$ such that each tree _Ti$T_i$ can be obtained from T$T$ by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(n^k)$\mathrm{\Omega }(n^k)$ time, n$n$ being the number of leaves. Here, we present an O(nf(k))$\mathrm{O}(\mathit{nf}(k))$ algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable   (FPT) with respect to the number k$k$ of trees.