Search results for "Automaton"
showing 10 items of 257 documents
Molecular Switching, Logics, and Memories
2013
The concepts of molecular switch, molecular logics and memories are intimately related. In this work a review of these three topics is given. While the main examples concern the field of inorganic chemistry, in a few cases organic systems are presented to better illustrate the concepts. The basic notions of the logics gates usually used by the nowadays computers is presented and the modus operandi to transpose these concepts to the molecular level is discussed. Examples of switches driven by external stimuli such as light-induced, metal-ion, redox, photobistable, and complexation–decomplexation are described in this chapter. The extension of switches working in solution to solid devices are…
Quantum Finite One-Counter Automata
1999
In this paper the notion of quantum finite one-counter automata (QF1CA) is introduced. Introduction of the notion is similar to that of the 2-way quantum finite state automata in [1]. The well-formedness conditions for the automata are specified ensuring unitarity of evolution. A special kind of QF1CA, called simple, that satisfies the well-formedness conditions is introduced. That allows specify rules for constructing such automata more naturally and simpler than in general case. Possible models of language recognition by QF1CA are considered. The recognition of some languages by QF1CA is shown and compared with recognition by probabilistic counterparts.
A description based on languages of the final non-deterministic automaton
2014
The study of the behaviour of non-deterministic automata has traditionally focused on the languages which can be associated to the different states. Under this interpretation, the different branches that can be taken at every step are ignored. However, we can also take into account the different decisions which can be made at every state, that is, the branches that can be taken, and these decisions might change the possible future behaviour. In this case, the behaviour of the automata can be described with the help of the concept of bisimilarity. This is the kind of description that is usually obtained when the automata are regarded as labelled transition systems or coalgebras. Contrarily t…
Complexity of operations on cofinite languages
2010
International audience; We study the worst case complexity of regular operation on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.
Real-Time Vector Automata
2013
We study the computational power of real-time finite automata that have been augmented with a vector of dimension k, and programmed to multiply this vector at each step by an appropriately selected k×k matrix. Only one entry of the vector can be tested for equality to 1 at any time. Classes of languages recognized by deterministic, nondeterministic, and "blind" versions of these machines are studied and compared with each other, and the associated classes for multicounter automata, automata with multiplication, and generalized finite automata.
Semipredictable dynamical systems
2015
A new class of deterministic dynamical systems, termed semipredictable dynamical systems, is presented. The spatiotemporal evolution of these systems have both predictable and unpredictable traits, as found in natural complex systems. We prove a general result: The dynamics of any deterministic nonlinear cellular automaton (CA) with $p$ possible dynamical states can be decomposed at each instant of time in a superposition of $N$ layers involving $p_{0}$, $p_{1}$,... $p_{N-1}$ dynamical states each, where the $p_{k\in \mathbb{N}}$, $k \in [0, N-1]$ are divisors of $p$. If the divisors coincide with the prime factors of $p$ this decomposition is unique. Conversely, we also prove that $N$ CA w…
Object Migration Automata for Non-equal Partitioning Problems with Known Partition Sizes
2021
Part 4: Automated Machine Learning; International audience; Solving partitioning problems in random environments is a classic and challenging task, and has numerous applications. The existing Object Migration Automaton (OMA) and its proposed enhancements, which include the Pursuit and Transitivity phenomena, can solve problems with equi-sized partitions. Currently, these solutions also include one where the partition sizes possess a Greatest Common Divisor (GCD). In this paper, we propose an OMA-based solution that can solve problems with both equally and non-equally-sized groups, without restrictions on their sizes. More specifically, our proposed approach, referred to as the Partition Siz…
A Bayesian Learning Automaton for Solving Two-Armed Bernoulli Bandit Problems
2008
The two-armed Bernoulli bandit (TABB) problem is a classical optimization problem where an agent sequentially pulls one of two arms attached to a gambling machine, with each pull resulting either in a reward or a penalty. The reward probabilities of each arm are unknown, and thus one must balance between exploiting existing knowledge about the arms, and obtaining new information. In the last decades, several computationally efficient algorithms for tackling this problem have emerged, with learning automata (LA) being known for their ?-optimality, and confidence interval based for logarithmically growing regret. Applications include treatment selection in clinical trials, route selection in …
Using Cellular Automata for feature construction - preliminary study
2007
When first faced with a learning task, it is often not clear what a good representation of the training data should look like. We are often forced to create some set of features that appear plausible, without any strong confidence that they will yield superior learning. Beside, we often do not have any prior knowledge of what learning method is the best to apply, and thus often try multiple methods in an attempt to find the one that performs best. This paper describes a new method and its preliminary study for constructing features based on cellular automata (CA). Our approach uses self-organisation ability of cellular automata by constructing features being most efficient for making predic…
Sur les Codes ZigZag et Leur Décidabilité
1990
AbstractThis paper deals with zigzag factorizations and zigzag codes. The language of “zigzag” over a regular language is represented by constructing a special family of two-way automata. Decidability of zigzag codes, previously shown for the finite languages, is proved here for all regular languages by the analysis of the set of “crossing sequences” produced by a two-way automation in the family. We also obtain that it is decidable whether or not a two-way automation of a certain type is non-ambiguous.RésuméDans ce papier on reprend les notions de factorisation zigzag et de code zigzag. On construit pour tout langage rationnel, une famille d'automates bilatéres lesquels reconnaissent les m…