We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t2(n) is a time-constructible function and t2(n) grows faster than t1(n+1), then there exists a language which can be accepted by a t2(n)-time nondeterministic cellular automaton but not by any t1(n)-time nondeterministic cellular automaton.

Two-state number-conserving cellular automaton (NCCA) is a cellular automaton of which cell states are 0 or 1, and the total sum of all the states of cells is kept for any time step. It is a kind of particle-based modeling of physical systems. We introduce a new structure of its value-1 patterns, which we call a “bundle pair” and a “bundle quad”. By employing this structure, we show a relation between the neighborhood size n and n - 2 NCCAs.

A number-conserving cellular automaton (NCCA) is a cellular automaton (CA) such that all states of cells are represented by integers and the sum of the cell states is conserved throughout its computing process. It can be thought of as a kind of modelization of the physical conservation law of mass or energy. It is known that the local function of a two-dimensional 45-degree reflection-symmetric von Neumann neighbor NCCA can be represented by linear combinations of a binary function. In spite of the number-conserving constraints, it is possible to design an NCCA with complex rules by employing this representation. In this paper, we study the case in which the binary function depends only on the difference of two cell states, i.e., the case in which the function can be regarded as a unary one and its circuit for applying rules to a cell only need adders and a single value table look up module. Even under this constraint, it is possible to construct a logically universal NCCA.

As one of privacy-enhancing authentications suitable for decentralized environments, ring signatures have intensively been researched. In ring signatures, each user can choose any ad-hoc set of users (specified by public keys) called a ring, and anonymously sign a message as one of the users. However, in applications of anonymous authentications, users may misbehave the service due to the anonymity, and thus a mechanism to exclude the anonymous misbehaving users is required. However, in the existing ring signature scheme, a trusted entity to open the identity of the user is needed, but it is not suitable for the decentralized environments. On the other hand, as another type of anonymous authentications, a decentralized blacklistable anonymous credential system is proposed, where anonymous misbehaving users can be detected and excluded by a blacklist. However, the DL-based instantiation needs O(N) proof size for the ring size N. In the research line of the DL-based ring signatures, an efficient scheme with O(log N) signature size, called DualRing, is proposed. In this paper, we propose a DL-based blacklistable ring signature scheme extended from DualRing, where in addition to the short O(log N) signature size for N, the blacklisting mechanism is realized to exclude misbehaving users. Since the blacklisting mechanism causes additional costs in our scheme, the signature size is O(log N+l), where l is the blacklist size.

This paper investigates prefix computations on Iterative Arrays (IAs) with sequential input/output mode. We show that, for any language L accepted by a linear-time IA, there is an IA which, given an infinite string a1a2 ai, generates the values of χL(a1),χL(a1a2),,χL(a1a2 ai), at steps 4,16,,4i2,, respectively. Here, χL:Σ*{0,1} is the characteristic function of the language L Σ*, defined as χL(w) = 1 iff w L. We also construct 2i3-time and i4-time prefix algorithms for languages accepted by quadratic-time and cubic-time IAs, respectively.

A number-conserving cellular automaton (NCCA) is a cellular automaton such that all states of cells are represented by integers and the total number of its configuration is conserved throughout its computing process. In constrast to normal cellular automata, there are infinitely many assignments of states for NCCAs with a constant state number. As for von Neumann neighbor(radius one) NCCAs with rotation-symmetry, a local function can be represented by summation of four binary functions. In this paper, we show that the minimum size of state set of rotation-symmetric von Neumann neighbor NCCA is 5 by using this representation.