Search results for "AUTOMATA"
showing 10 items of 453 documents
The complexity of graph languages generated by hyperedge replacement
1990
Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.
Can the Double Exchange Cause Antiferromagnetic Spin Alignment?
2020
The effect of the double exchange in a square-planar mixed-valence dn+1&minus
Resetting of a planar superconducting quantum memory
2009
We consider and analyze a scheme for the reset of a M × N planar array of inductively coupled Josephson flux qubits. We prove that it is possible to minimize the resetting time of an arbitrary chosen row of qubits by properly switching on and off the coupling between pairs of qubits belonging to the same column. In addition, the analysis of the time evolution of the array allows us to single out the class of generalized W states which can be successfully reset.
Cellular automaton for chimera states
2016
A minimalistic model for chimera states is presented. The model is a cellular automaton (CA) which depends on only one adjustable parameter, the range of the nonlocal coupling, and is built from elementary cellular automata and the majority (voting) rule. This suggests the universality of chimera-like behavior from a new point of view: Already simple CA rules based on the majority rule exhibit this behavior. After a short transient, we find chimera states for arbitrary initial conditions, the system spontaneously splitting into stable domains separated by static boundaries, ones synchronously oscillating and the others incoherent. When the coupling range is local, nontrivial coherent struct…
Relative importance of second-order terms in relativistic dissipative fluid dynamics
2013
In Denicol et al., Phys. Rev. D 85, 114047 (2012), the equations of motion of relativistic dissipative fluid dynamics were derived from the relativistic Boltzmann equation. These equations contain a multitude of terms of second order in Knudsen number, in inverse Reynolds number, or their product. Terms of second order in Knudsen number give rise to non-hyperbolic (and thus acausal) behavior and must be neglected in (numerical) solutions of relativistic dissipative fluid dynamics. The coefficients of the terms which are of the order of the product of Knudsen and inverse Reynolds numbers have been explicitly computed in the above reference, in the limit of a massless Boltzmann gas. Terms of …
Implementing Quantum Finite Automata Algorithms on Noisy Devices
2021
Quantum finite automata (QFAs) literature offers an alternative mathematical model for studying quantum systems with finite memory. As a superiority of quantum computing, QFAs have been shown exponentially more succinct on certain problems such as recognizing the language \(\mathtt {MOD}_\mathrm{p}= \{{a^{j}} \mid {j \equiv 0 \mod p}\} \) with bounded error, where p is a prime number. In this paper we present improved circuit based implementations for QFA algorithms recognizing the \(\mathtt {MOD}_\mathrm{p}\) problem using the Qiskit framework. We focus on the case \(p=11\) and provide a 3 qubit implementation for the \(\mathtt {MOD}_\mathrm{11}\) problem reducing the total number of requi…
Mixed-Valence Magnetic Molecular Cell for Quantum Cellular Automata: Prospects of Designing Multifunctional Devices through Exploration of Double Exc…
2020
In this article, we propose to use multielectron square-planar mixed-valence (MV) molecules as molecular cells for quantum cellular automata (QCA) devices. As distinguished from previous proposals ...
Kinetic model for steady heat flow
1986
We construct a consistent solution of the Bhatnagar-Gross-Krook (BGK) model kinetic equation describing a system in a steady state with constant pressure and nonuniform temperature. The thermal profile is not linear and depends on the interaction potential. All the moments of the distribution function are given as polynomials in the local thermal gradient. In particular, the heat flux always obeys the (linear) Fourier law.
Relative importance of second-order terms in relativistic dissipative fluid dynamics
2014
[Introduction] In Denicol et al. [Phys. Rev. D 85 , 114047 (2012)], the equations of motion of relativistic dissipative fluid dynamics were derived from the relativistic Boltzmann equation. These equations contain a multitude of terms of second order in the Knudsen number, in the inverse Reynolds number, or their product. Terms of second order in the Knudsen number give rise to nonhyperbolic (and thus acausal) behavior and must be neglected in (numerical) solutions of relativistic dissipative fluid dynamics. The coefficients of the terms which are of the order of the product of Knudsen and inverse Reynolds numbers have been explicitly computed in the above reference, in the limit of a massl…
Minimal Absent Words in Rooted and Unrooted Trees
2019
We extend the theory of minimal absent words to (rooted and unrooted) trees, having edges labeled by letters from an alphabet \(\varSigma \) of cardinality \(\sigma \). We show that the set \(\text {MAW}(T)\) of minimal absent words of a rooted (resp. unrooted) tree T with n nodes has cardinality \(O(n\sigma )\) (resp. \(O(n^{2}\sigma )\)), and we show that these bounds are realized. Then, we exhibit algorithms to compute all minimal absent words in a rooted (resp. unrooted) tree in output-sensitive time \(O(n+|\text {MAW}(T)|)\) (resp. \(O(n^{2}+|\text {MAW}(T)|)\) assuming an integer alphabet of size polynomial in n.