Approaching Arithmetic Theories with Finite-State Automata
Ontology highlight
ABSTRACT:
SUBMITTER: Leporati A
PROVIDER: S-EPMC7206625 | biostudies-literature | 2020 Jan
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:Biomolecular logic devices can be applied for sensing and nano-medicine. We built three DNA tweezers that are activated by the inputs H(+)/OH(-); ; nucleic acid linker/complementary antilinker to yield a 16-states finite-state automaton. The outputs of the automata are the configuration of the respective tweezers (opened or closed) determined by observing fluorescence from a fluorophore/quencher pair at the end of the arms of the tweezers. The system exhibits a memory because each current state and output depend not only on the source configuration but also on past states and inputs.
| S-EPMC3009826 | biostudies-literature
Project description:Finite-state automata (FSA) are simple computational devices that can nevertheless illustrate interesting behaviours. We propose that FSA can be employed as control circuits for engineered stochastic biological and biomolecular systems. We present an implementation of FSA using counts of chemical species in the range of hundreds to thousands, which is relevant for the counts of many key molecules such as mRNAs in prokaryotic cells. The challenge here is to ensure a robust representation of the current state in the face of stochastic noise. We achieve this by using a multistable approximate majority algorithm to stabilize and store the current state of the system. Arbitrary finite state machines can thus be compiled into robust stochastic chemical automata. We present two variants: one that consumes its input signals to initiate state transitions and one that does not. We characterize the state change dynamics of these systems and demonstrate their application to solve the four-bit binary square root problem. Our work lays the foundation for the use of chemical automata as control circuits in bioengineered systems and biorobotics.
| S-EPMC8692961 | biostudies-literature
Project description:Every problem in computing can be cast as decision problems of whether strings are in a language or not. Computations and language recognition are carried out by three classes of automata, the most complex of which is the Turing machine. Living systems compute using biochemistry; in the artificial, computation today is mostly electronic. Thinking of chemical reactions as molecular recognition machines, and without using biochemistry, we realize one automaton in each class by means of one-pot, table top chemical reactors: from the simplest, Finite automata, to the most complex, Turing machines. Language acceptance/rejection criteria by automata can be formulated using energy considerations. Our Turing machine uses the Belousov-Zhabotinsky chemical reaction and checks the same symbol in an Avogadro's number of processors. Our findings have implications for chemical and general computing, artificial intelligence, bioengineering, the study of the origin and presence of life on other planets, and for artificial biology.
| S-EPMC6710637 | biostudies-literature
Project description:Obtaining a minimal automaton is a fundamental issue in the theory and practical implementation of deterministic finite automatons (DFAs). A minimization algorithm is presented in this paper that consists of two main phases. In the first phase, the backward depth information is built, and the state set of the DFA is partitioned into many blocks. In the second phase, the state set is refined using a hash table. The minimization algorithm has a lower time complexity O(n) than a naive comparison of transitions O(n2). Few states need to be refined by the hash table, because most states have been partitioned by the backward depth information in the coarse partition. This method achieves greater generality than previous methods because building the backward depth information is independent of the topological complexity of the DFA. The proposed algorithm can be applied not only to the minimization of acyclic automata or simple cyclic automata, but also to automata with high topological complexity. Overall, the proposal has three advantages: lower time complexity, greater generality, and scalability. A comparison to Hopcroft's algorithm demonstrates experimentally that the algorithm runs faster than traditional algorithms.
| S-EPMC5091862 | biostudies-literature
Project description:A Galois field GF(pn) with p?2 a prime number and n?1 is a mathematical structure widely used in Cryptography and Error Correcting Codes Theory. In this paper, we propose a novel DNA-based model for arithmetic over GF(pn) . Our model has three main advantages over other previously described models. First, it has a flexible implementation in the laboratory that allows the realization arithmetic calculations in parallel for p?2 , while the tile assembly and the sticker models are limited to p=2 . Second, the proposed model is less prone to error, because it is grounded on conventional Polymerase Chain Reaction (PCR) amplification and gel electrophoresis techniques. Hence, the problems associated to models such as tile-assembly and stickers, that arise when using more complex molecular techniques, such as hybridization and denaturation, are avoided. Third, it is simple to implement and requires 50 ng/?L per DNA double fragment used to develop the calculations, since the only feature of interest is the size of the DNA double strand fragments. The efficiency of our model has execution times of order O(1) and O(n) , for the addition and multiplication over GF(pn) , respectively. Furthermore, this paper provides one of the few experimental evidences of arithmetic calculations for molecular computing and validates the technical applicability of the proposed model to perform arithmetic operations over GF(pn) .
| S-EPMC6926258 | biostudies-literature
Project description:This study is based on the processing of computed microtomography images of rock samples. In this study, a finite automation is constructed using the grey value, red-green-blue (RGB) value and Euler number of polarized images of carbonate rocks from the Jingfengqiao-Baidiao area. The finite automaton is used to perform black and white binary processing of the polarized images of the carbonate rocks. The porosity of the carbonate rock is calculated based on the black and white binarization processing results of the polarized images of the carbonate rocks. The obtained porosity is compared with the carbonate porosity obtained by use of the traditional carbonate research method. When the two porosities are close, the image processing threshold of the finite automata is considered to be credible. Based on the finite automata established using the image processing threshold, the black and white binary images of the polarized images of the carbonate rocks are used to establish a rock pore image using ImageJ2X. The polarized images of the carbonate rocks are classified according to their RGB values using the finite automata for the porosity classification, and the obtained images are used as textures to paste onto a cube to construct a three-dimensional data model of the carbonate rocks. This study also uses 16S rDNA analysis to verify the formation mechanism of the carbonate pores in the Jingfengqiao-Baidiao area. The results of the 16S rDNA analysis show that the pores in the carbonate rocks in the Jingfengqiao-Baidiao area are closely related to microorganisms, represented by denitrifying bacteria.
| S-EPMC8753174 | biostudies-literature
Project description:Background: This paper presents an efficient two-dimensional (2-D) finite impulse response (FIR) filter using block processing for two different symmetries. Architectures for a general filter (without symmetry) and two symmetrical filters (diagonal and quadrantal symmetry) are implemented. The proposed architectures need fewer multipliers because of the symmetry of the filter coefficients. Methods: A distributed arithmetic (DA)- based multiplication method is used in the proposed architecture. A dual-port memory-based lookup table (DP-MLUT) is used in the multiplication instead of lookup-table (LUT) to reduce the area and power of the FIR filter. The filter's throughput is increased by using block processing. Memory reuse and memory sharing methods are introduced, which reduces the need for many registers and hence the circuit complexity. The architectures are written in Verilog Hardware Description Language and synthesized using Genus Synthesis tool-19.1 in 45nm technology with a generic library of Cadence vendor constraints. The synthesis tool generates the area, delay, and power reports. Power consumption of architectures is calculated with an image size of 64 X 64 and at 20 MHz frequency. Results: Compared to existing architectures, the synthesis results show improvements in power, area, area delay product (ADP), and power delay product (PDP). The proposed MLUT-based 2-D block Quadrantal Symmetry Filter (QSF) for length 8 with block size 4 consumes 58.94% less power, occupies 59.5% less area, 48.44% less ADP and 47.78% less PDP compared to best existing methods. Conclusions: A novel DA-based 2-D block FIR filter architecture with various symmetries is realized. Symmetry is incorporated into the filter coefficients to minimize the number of multipliers. The LUT size is optimized by odd multiples or even multiples storage techniques. Also, the overall area of the architecture is decreased by DP-LUT-based multipliers. The proposed filter architecture is area-power-efficient. It is best suited for applications that have fixed coefficients.
| S-EPMC10911408 | biostudies-literature
Project description:Endowing materials with the ability to sense, adapt, and respond to stimuli holds the key to a progress leap in autonomous systems. In spite of the growing success of macroscopic soft robotic devices, transferring these concepts to the microscale presents several challenges connected to the lack of suitable fabrication and design techniques and of internal response schemes that connect the materials' properties to the function of the active units. Here, we realize self-propelling colloidal clusters which possess a finite number of internal states, which define their motility and which are connected by reversible transitions. We produce these units via capillary assembly combining hard polystyrene colloids with two different types of thermoresponsive microgels. The clusters, actuated by spatially uniform AC electric fields, adapt their shape and dielectric properties, and consequently their propulsion, via reversible temperature-induced transitions controlled by light. The different transition temperatures for the two microgels enable three distinct dynamical states corresponding to three illumination intensity levels. The sequential reconfiguration of the microgels affects the velocity and shape of the active trajectories according to a pathway defined by tailoring the clusters' geometry during assembly. The demonstration of these simple systems indicates an exciting route toward building more complex units with broader reconfiguration schemes and multiple responses as a step forward in the pursuit of adaptive autonomous systems at the colloidal scale.
| S-EPMC10089169 | biostudies-literature
Project description:Magnetic noise of atomic nuclear spins is a major source of decoherence in solid-state spin qubits. In theory, near-unity nuclear spin polarization can eliminate decoherence of the electron spin qubit, while turning the nuclei into a useful quantum information resource. However, achieving sufficiently high nuclear polarizations has remained an evasive goal. Here we implement a nuclear spin polarization protocol which combines strong optical pumping and fast electron tunneling. Nuclear polarizations well above 95% are generated in GaAs semiconductor quantum dots on a timescale of 1 minute. The technique is compatible with standard quantum dot device designs, where highly-polarized nuclear spins can simplify implementations of qubits and quantum memories, as well as offer a testbed for studies of many-body quantum dynamics and magnetism.
| S-EPMC10837425 | biostudies-literature
Project description:The present study investigates the relation between resting-state functional connectivity (rsFC) of cytoarchitectonically defined subdivisions of the parietal cortex at the end of 1st grade and arithmetic performance at the end of 2nd grade. Results revealed a dissociable pattern of relations between rsFC and arithmetic competence among subdivisions of intraparietal sulcus (IPS) and angular gyrus (AG). rsFC between right hemisphere IPS subdivisions and contralateral IPS subdivisions positively correlated with arithmetic competence. In contrast, rsFC between the left hIP1 and the right medial temporal lobe, and rsFC between the left AG and left superior frontal gyrus, were negatively correlated with arithmetic competence. These results suggest that strong inter-hemispheric IPS connectivity is important for math development, reflecting either neurocognitive mechanisms specific to arithmetic processing, domain-general mechanisms that are particularly relevant to arithmetic competence, or structural 'cortical maturity'. Stronger connectivity between IPS, and AG, subdivisions and frontal and temporal cortices, however, appears to be negatively associated with math development, possibly reflecting the ability to disengage suboptimal problem-solving strategies during mathematical processing, or to flexibly reorient task-based networks. Importantly, the reported results pertain even when controlling for reading, spatial attention, and working memory, suggesting that the observed rsFC-behavior relations are specific to arithmetic competence.
| S-EPMC5568461 | biostudies-literature