Trace nets and process automata

Trace nets are a variant of one-safe Petri nets, where input and output places may be filled as well as emptied by transitions. Those extended nets are introduced for modelling concurrency in a simple format of structural operational specifications, based on permutation of proved transitions. Trace nets are connected by an adjunction to a particular class of trace automata in the sense of Stark, namely the separated trace automata. The adjunction is based on a calculus of regions that differ significantly from the ones devised by Ehrenfeucht and Rozenberg for elementary nets, although the axioms of separation are the same.This work was partly supported by the project MASK of the E.C. Program Science.     

Syntactic monoids in the construction of systolic tree automata

The acceptance of regular languages by systolic tree automata is analyzed in more detail by investigating the structure of the individual processors needed. Since the processors essentially compute the monoid product, our investigation leads to questions concerning syntactic monoids. Hereby certain properties of monoids turn out to be important. These properties, as well as the language families induced by them, are also studied in the paper.Most of the work connected with this paper was done in 1982, while the authors were visiting the Computer Science Department of the University of Waterloo, Ontario.     

Minimization of states in automata theory based on finite lattice-ordered monoids

In this study, we consider a concept of complete L-fuzzy matrix, define complete lattice-valued finite automata (CLFAs) and study their properties. The definitions of statewise equivalence relations and automata equivalence relations of a CLFA are given, two algorithms are aimed at the minimization of states of a CLFA.     

Mathematical logic and quantum finite state automata

This paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. As is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. After a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.     

An overview of quantum computation models: quantum automata

Quantum automata, as theoretical models of quantum computers, include quantum finite automata (QFA), quantum sequential machines (QSM), quantum pushdown automata (QPDA), quantum Turing machines (QTM), quantum cellular automata (QCA), and the others, for example, automata theory based on quantum logic (orthomodular lattice-valued automata). In this paper, we try to outline a basic progress in the research on these models, focusing on QFA, QSM, QPDA, QTM, and orthomodular lattice-valued automata. Also, other models closely relative to them are mentioned. In particular, based on the existing results in the literature, we finally address a number of problems to be studied in future.     

Simulation of quantum key expansion using quantum cellular automata

Quantum cryptography has become reality nowadays and quantum key distribution systems are already in use. In classical cryptography, key expansion schemes are used to strengthen security. In this paper we present a quantum key expansion scheme, in which the key is expanded using a quantum cellular automaton. We also present the simulation of quantum key expansion using a quantum computer simulator. Using this scheme a 6-qubit key transmitted from the sender to the receiver, using one of the quantum key distribution protocols, can be expanded to a 24-qubit key without any further communication between them.     

Intrinsically universal n-dimensional quantum cellular automata

Several non-axiomatic approaches have been taken to define Quantum Cellular Automata (QCA); Partitioned QCA (PQCA) are the most canonical. Here we show any QCA can be put into PQCA form. Our construction reconciles the non-axiomatic definitions of QCA, showing that they can all simulate one another, thus they are all equivalent to the axiomatic definition. A simple n-dimensional QCA capable of simulating all others to arbitrary precision is described, where the initial configuration and the evolution of any QCA can be encoded within the initial configuration of the intrinsically universal QCA. Several steps then correspond to one step of the simulated QCA, achieved via a non-trivial reduction of the problem to universality in quantum circuits. Results are formalised by defining generalised n-dimensional intrinsic simulation, preserving topology in that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. Implications are discussed.     

An overview of quantum cellular automata

Quantum cellular automata are arrays of identical finite-dimensional quantum systems, evolving in discrete-time steps by iterating a unitary operator G. Moreover the global evolution G is required to be causal (it propagates information at a bounded speed) and translation-invariant (it acts everywhere the same). Quantum cellular automata provide a model/architecture for distributed quantum computation. More generally, they encompass most of discrete-space discrete-time quantum theory. We give an overview of their theory, with particular focus on structure results; computability and universality results; and quantum simulation results.

     

Finite automata based on quantum logic and monadic second-order quantum logic

We introduce monadic second-order quantum logic and prove that the behaviors of finite automata based on quantum logic are precisely the quantum languages definable with sentences of our monadic secondorder quantum logic. This generalizes Büchi’s and Elgot’s fundamental theorems to quantum logic setting. We also consider first-order quantum logic and show that star-free quantum languages and aperiodic quantum languages introduced here coincide with the first-order quantum definable ones. This generalizes Sc...     

Unary probabilistic and quantum automata on promise problems

We continue the systematic investigation of probabilistic and quantum finite automata (PFAs and QFAs) on promise problems by focusing on unary languages. We show that bounded-error unary QFAs are more powerful than bounded-error unary PFAs, and, contrary to the binary language case, the computational power of Las-Vegas QFAs and bounded-error PFAs is equivalent to the computational power of deterministic finite automata (DFAs). Then, we present a new family of unary promise problems defined with two parameters such that when fixing one parameter QFAs can be exponentially more succinct than PFAs and when fixing the other parameter PFAs can be exponentially more succinct than DFAs.     

A quantum model for autonomous learning automata

The idea of information encoding on quantum bearers and its quantum-mechanical processing has revolutionized our world and brought mankind on the verge of enigmatic era of quantum technologies. Inspired by this idea, in present paper, we search for advantages of quantum information processing in the field of machine learning. Exploiting only basic properties of the Hilbert space, superposition principle of quantum mechanics and quantum measurements, we construct a quantum analog for Rosenblatt’s perceptron, which is the simplest learning machine. We demonstrate that the quantum perceptron is superior to its classical counterpart in learning capabilities. In particular, we show that the quantum perceptron is able to learn an arbitrary (Boolean) logical function, perform the classification on previously unseen classes and even recognize the superpositions of learned classes—the task of high importance in applied medical engineering.     

Partitioned quantum cellular automata are intrinsically universal

There have been several non-axiomatic approaches taken to define quantum cellular automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. This is achieved by defining generalised n-dimensional intrinsic simulation, which brings the computer science based concepts of simulation and universality closer to theoretical physics. The result is not only an important simplification of the QCA model, it also plays a key role in the identification of a minimal n-dimensional intrinsically universal QCA.     

Improved constructions of mixed state quantum automata

Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A. Ambainis and R. Freivalds that quantum finite automata with pure states can have an exponentially smaller number of states than deterministic finite automata recognizing the same language. There was an unpublished “folk theorem” proving that quantum finite automata with mixed states are no more super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable.     

XOR transform with actin quantum automata for better security against cryptanalysis

XOR is a basic cryptographic transform, used as a one way function inside of complex cryptosystems. In this paper we propose first of a kind design of the XOR transform with a universal logic designing paradigm. The system offers enhanced security to the transform by propagating randomly generated information along with the XOR output over the unsecured channel. This additional security is a inherent attribute of the actin automata and is exploited in this paper. The system can be enacted on a Partitioned one-Dimensional Quantum Cellular Automata. A simulation of the proposed system is illustrated with Simulink tool in MATLAB. Based on the work done by Adamatzky et al. we observe that the actin automata is capable of operating on quantum input bits and can generate appropriate results when required. In this paper, the actin automata is simulated with classical bits instead of quantum bits for designing the transform. We have also tried to establish the proposed system by means of low power consumption verified with NI Multisim and comparison with cryptographic complexity with traditional XOR transform. Additionally, we have analyzed the system for enhanced cryptanalytic complexity against various attacks.

     

Comparison between cellular automata and linear feedback shift registers based pseudo-random number generators

A detailed comparison between pseudo-random number generators (PRNGs) based on cellular automata (CA) and linear feedback shift registers (LFSRs) is presented in this paper. Various statistical tests have been applied in order to reveal the advantages and disadvantages of both approaches. Both LFSRs and hybrid additive cellular automata (HACA) produce satisfactory PRNGs. HACA operate at higher speeds than LFSRs with the same characteristic polynomials. Regarding the silicon area, direct comparisons between the two approaches cannot be made since it depends on the PRNG length. However, the inherent modularity of HACA reduces the silicon area occupied by them and, when long feedback paths are used, the silicon area occupied by LFSRs increases.     

Reversible binary subtractor design using quantum dot-cellular automata

In the field of nanotechnology, quantum dot-cellular automata (QCA) is the promising archetype that can provide an alternative solution to conventional complementary metal oxide semiconductor (CMOS) circuit. QCA has high device density, high operating speed, and extremely low power consumption. Reversible logic has widespread applications in QCA. Researchers have explored several designs of QCA-based reversible logic circuits, but still not much work has been reported on QCA-based reversible binary subtractors. The low power dissipation and high circuit density of QCA pledge the energy-efficient design of logic circuit at a nano-scale level. However, the necessity of too many logic gates and detrimental garbage outputs may limit the functionality of a QCA-based logic circuit. In this paper we describe the design and implementation of a DG gate in QCA. The universal nature of the DG gate has been established. The QCA building block of the DG gate is used to achieve new reversible binary subtractors. The proposed reversible subtractors have low quantum cost and garbage outputs compared to the existing reversible subtractors. The proposed circuits are designed and simulated using QCA Designer-2.0.3.