Narrow Results

Recently, a method to decide the NL-complete problem of whether the language accepted by a given deterministic finite automaton (DFA) can also be accepted by some reversible deterministic finite automaton (REV-DFA) has been derived. Here, we show that the corresponding problem for nondeterministic finite automata (NFA) is PSPACE-complete. The recent DFA method essentially works by minimizing the DFA and inspecting it for a forbidden pattern. We here study the degree of irreversibility for a regular language, the minimal number of such forbidden patterns necessary in any DFA accepting the language, and show that the degree induces a strict infinite hierarchy of language families. We examine how the degree of irreversibility behaves under the usual language operations union, intersection, complement, concatenation, and Kleene star, showing tight bounds (some asymptotically) on the degree.

Finite automata whose computations can be reversed, at any point, by knowing the last $k$ symbols read from the input, for a fixed $k$, are considered. These devices and their accepted languages are called $k$-reversible automata and $k$-reversible languages, respectively. The existence of $k$-reversible languages which are not $(k-1)$-reversible is known, for each $k>1$. This gives an infinite hierarchy of weakly irreversible languages, i.e., languages which are $k$-reversible for some $k$. Conditions characterizing the class of $k$-reversible languages, for each fixed $k$, and the class of weakly irreversible languages are obtained. From these conditions, a procedure that given a finite automaton decides if the accepted language is weakly or strongly (i.e., not weakly) irreversible is described. Furthermore, a construction which allows to transform any finite automaton which is not $k$-reversible, but which accepts a $k$-reversible language, into an equivalent $k$-reversible finite automaton, is presented.

We give a list of equivalent conditions for reversibility of the adjoint of a unital Schwarz map, with respect to a set of quantum states. A large class of such conditions is given by preservation of distinguishability measures: F-divergences, L₁-distance, quantum Chernoff and Hoeffding distances. Here we summarize and extend the known results. Moreover, we prove a number of conditions in terms of the properties of a quantum Radon–Nikodym derivative and factorization of states in the given set. Finally, we show that reversibility is equivalent to preservation of a large class of quantum Fisher informations and χ²-divergences.

In this paper, we introduce the notions of R-reversibility and Ricci-reversibility. We prove that Randers metrics are R-reversible or Ricci-reversible if and only if they are R-quadratic or Ricci-quadratic, respectively. Besides, we discuss the properties of Ricci- or R-reversible Randers metrics which are also weakly Einsteinian, or Douglassian, or of scalar flag curvature. In particular, we determine the local structure of Randers metrics which are Ricci-reversible and locally projectively flat, and prove that an n (≥ 3)-dimensional Ricci-reversible Randers metric of non-zero scalar flag curvature is locally projectively flat.

In this paper, the reversibility problem for 150 Wolfram cellular automata is tackled for null boundary conditions. It is explicitly shown that the reversibility depends on the number of cells of the cellular automaton. The inverse cellular automaton for each case is also computed.

The characterization of the size of the cellular space of a particular type of reversible symmetric linear cellular automata is introduced in this paper. Specifically, it is shown that those symmetric linear cellular with 2k + 1 cells, and whose transition matrix is a k-diagonal square band matrix with nonzero entries equal to 1 are reversible. Furthermore, in this case the inverse cellular automata are explicitly computed. Moreover, the reversibility condition is also studied for a general number of cells.

In this paper, we study one dimensional finite linear cellular automata with reflective boundary condition by using matrix algebra built on the field ℤ_p. We present an algorithm for determining the reversibility of this family of cellular automata. We also answer the reversibility question for some special subfamilies. Finally, we present some examples of this family of cellular automata under the reflective boundary condition.

The reversibility problem for linear cellular automata with null boundary defined by a rule matrix in the form of a pentadiagonal matrix was studied over the binary field ℤ₂ by Martín del Rey et al. [Appl. Math. Comput.217, 8360 (2011)]. Recently, the reversibility problem of 1D Cellular automata with periodic boundary has been extended to ternary fields and further to finite primitive fields ℤ_p by Cinkir et al. [J. Stat. Phys.143, 807 (2011)]. In this work, we restudy some of the work done in Cinkir et al. [J. Stat. Phys.143, 807 (2011)] by using a different approach which is based on the theory of error correcting codes. While we reestablish some of the theorems already presented in Cinkir et al. [J. Stat. Phys.143, 807 (2011)], we further extend the results to more general cases. Also, a conjecture that is left open in Cinkir et al. [J. Stat. Phys.143, 807 (2011)] is also solved here. We conclude by presenting an application to Error Correcting Codes (ECCs) where reversibility of cellular automata is crucial.

The study of the reversibility of elementary cellular automata with rule number 150 over the finite state set 𝔽_p and endowed with periodic boundary conditions is done. The dynamic of such discrete dynamical systems is characterized by means of characteristic circulant matrices, and their analysis allows us to state that the reversibility depends on the number of cells of the cellular space and to explicitly compute the corresponding inverse cellular automata.

In the light of recent developments in the theory of reversibility for asynchronous cellular automata, we attempt to explore the dynamics of recurrent rules under fully asynchronous updating scheme. Depending on the reachability of the configurations for a communication class during the evolution of the system, we classify the recurrent rules into two classes — partially exposed recurrent system and fully exposed recurrent system.

This paper reports a stochastic method of synthesizing three-neighborhood two-state nonlinear non-uniform reversible cellular automata (CAs) having large cycle(s). To develop this method, we propose a parameter which measures the dependency of each cell on its neighbors. Using this parameter, we classify the possible rules of reversible CAs into four classes — completely dependent, partially dependent, weakly dependent and independent. A CA is expected to have larger cycle length if most of the rules of the CA are sensitive to their neighbors; hence, possess higher parameter value. It is shown that our synthesis algorithm, where rules are selected from the first three classes based on Gaussian distribution, can successfully generate CAs having desired length cycle. We empirically show that most of the synthesized CAs have a cycle at least as large as $2^{n-1}$, where $n$ is the lattice size. Then, as an application of such CAs, a scheme is developed to design window-based pseudo-random number generators (PRNGs) using (some of) them. These PRNGs are easily implementable on hardware and are highly portable. Finally, when compared on the same platform, our PRNGs outperform most of the well-known PRNGs existing today.

In recent years, a number of studies with different methods dedicated to structures and properties of liquid alloys revealed the occurrence of temperature-induced liquid–liquid structural transformation (TI-LLST). As yet, however, few investigations have concerned the reversibility of TI-LLST. The present paper reports a reversible TI-LLST in Pb–Sn alloys, which was observed with the electrical resistivity method during succeeding cooling and heating runs after the first heating process. The reversible TI-LLST is not the same as the TI-LLST in the first heating run, because the temperature ranges and the patterns are different from those of the latter. It is interesting that the similar phenomenon is also observed in pure tin, which suggests that the reversible TI-LLST in liquid Pb–Sn alloy is related to that in liquid Sn.

Since the discovery of the Meissner effect, the superconductor to normal (S–N) phase transition in the presence of a magnetic field is understood to be a first-order phase transformation that is reversible under ideal conditions and obeys the laws of thermodynamics. The reverse (N–S) transition is the Meissner effect. This implies in particular that the kinetic energy of the supercurrent is not dissipated as Joule heat in the process where the superconductor becomes normal and the supercurrent stops. In this paper, we analyze the entropy generation and the momentum transfer between the supercurrent and the body in the S–N transition and the N–S transition as described by the conventional theory of superconductivity. We find that it is not possible to explain the transition in a way that is consistent with the laws of thermodynamics unless the momentum transfer between the supercurrent and the body occurs with zero entropy generation, for which the conventional theory of superconductivity provides no mechanism. Instead, we point out that the alternative theory of hole superconductivity does not encounter such difficulties.

We propose a new system of generating array languages in parallel, based on a partitioned cellular automaton (PCA), a kind of cellular automaton. This system is called a PCA array generator (PCAAG). The characteristic of PCAAG is that a”reversible” version is easily defined. A reversible PCA (RPCA) is a backward deterministic PCA, and we can construct a deterministic “inverse” PCA that undoes the operations of the RPCA. Thus if an array language is generated by an RPCA, it can be parsed in parallel by a deterministic inverse PCA without backtracking. We also define two subclasses of PCAAG, and give examples of them that generate geometrical figures.

Reversible cellular automata are discrete invertible dynamical systems determined by local interactions among their components. For the one-dimensional case, there are classical references providing a complete characterization based on combinatorial properties. Using these results and the simulation of every automaton by another with neighborhood size 2, this paper describes other types of invertible behaviors embedded in these systems different from the classical one observed in the temporal evolution. In particular, spatial reversibility and diagonal surjectivity are studied, and the generation of macrocells in the evolution space is analyzed.

This paper focuses on the existence of closed orbits around a two-fold singularity of 3D discontinuous systems of the Filippov type in the presence of symmetries.

We present counterexamples illustrating that the characterization of the reversibility of linear cellular automata on finite triangular grids given by Uguz et al. [2017] and Uguz et al. [2019] is not valid, neither in the case of null boundary conditions nor in the case of periodic boundary conditions.

In this paper, we study the stability of the equilibrium point and investigate the periodicity properties of a class of difference equations $x_{n+1}=\frac{A_n{x}_n^3+B}{C{x}_{n-1}}$, $n\in \mathbb{N},$ whose parameters and initial values are positive. In particular, $A_n$ is a two-periodic coefficient with respect to n. Moreover, we depict the phase transition of orbits and analyze the deviation of the quasi-periodic orbits from some periodic orbits related to the arithmetic property of $A_n$, including Diophantine and Liouvillean numbers. We associate the response solution problem of differential equations with the fixed point problem of the area-preserving mapping related to multiperiodic difference equations, and pose some future work. The techniques are based on Moser’s twist mapping theorem, reversibility and some invariant structures embedded in the system.

It is widely understood that quantum computing — quantum gates upon qubits — is the general case, encompassing computing by classical means, viz. Boolean logic upon classical bits. It also seems reasonable that Quantum Software should encompass Classical Software. However, to accept such a statement regarding software, the feeling that it seems reasonable is not enough. One needs clear-cut definitions and formal conclusions. This is exactly the purpose of this paper. Previously, we have represented Classical Software by the Laplacian Matrix. More recently, we have shown that Quantum Software is faithfully represented by Density Matrices. It turns out that a Laplacian Matrix normalized by the Laplacian Trace easily obtains a Density Matrix. This opens the horizons for Quantum Software operations — such as unitary and reversible evolution — not naturally available with the classical Laplacian. This paper provides the necessary definitions and conclusions, illustrating the more general Quantum operations with a relevant case study, playing the double role of both classical and quantum software.

Fix a group G and let X be an algebraic variety over an algebraically closed field k of characteristic zero. We investigate the invertibility of algebraic cellular automata, namely, G-equivariant uniformly continuous self-maps whose local defining maps are induced by morphisms of algebraic varieties $X^M\to X$ where $M\subset G$ is a finite memory set. When G is locally embeddable into finite groups (LEF), we show that the inverses of reversible algebraic cellular automata are automatically algebraic cellular automata and thus computable in polynomial time. Generalizations are also obtained for finite product Hopfian pointed object alphabets in concrete categories. Moreover, we prove that for algebraic cellular automata, the notions of reversibility and injectivity are equivalent whenever G is surjunctive and the field k is, additionally, uncountable of arbitrary characteristic.